Un grafo es una estructura de datos que representa una colección de nodos (vértices) y las conexiones entre ellos (aristas). Los grafos son fundamentales en programación para modelar relaciones entre elementos, como redes sociales, mapas de carreteras, redes de computadoras o flujos de trabajo.

Estructura de un Grafo

Vértices (Nodos): Representan los elementos individuales, como ciudades, personas o puntos.
Aristas (Conexiones): Representan las relaciones o conexiones entre los vértices.
Dirigidas: Las conexiones tienen una dirección (por ejemplo, de A a B).
No dirigidas: Las conexiones no tienen dirección (por ejemplo, A está conectado a B y viceversa).
Pesos (Opcionales): Cada arista puede tener un peso que representa una métrica asociada, como distancia, costo o tiempo.

Tipos de Grafos

Grafo Simple: No tiene aristas múltiples ni bucles (aristas que conectan un nodo consigo mismo).
Grafo Dirigido: Las aristas tienen una dirección específica.
Grafo No Dirigido: Las conexiones no tienen dirección.
Grafo Ponderado: Cada arista tiene un peso asociado.
Grafo Completo: Cada nodo está conectado a todos los demás nodos.
Árbol: Un caso especial de grafo acíclico donde cada nodo tiene una única conexión hacia otro nodo superior.

Representación de Grafos

Los grafos se pueden representar de varias formas:

Matriz de Adyacencia: Una matriz cuadrada donde la posición (i, j) indica si hay una conexión entre el nodo i y el nodo j.
Lista de Adyacencia: Cada nodo tiene una lista de nodos conectados a él.
Lista de Aristas: Una lista de todas las conexiones con sus pesos opcionales.

Los grafos son una estructura poderosa y versátil para modelar relaciones complejas entre elementos. Dominar los grafos y sus representaciones es clave para resolver problemas en redes, optimización y diseño de algoritmos avanzados. Con diferentes lenguajes, puedes adaptarlos fácilmente a tus necesidades.

Ejemplos de Grafos en Diferentes Lenguajes

JavaScript
En JavaScript, los grafos se pueden implementar utilizando un objeto o un mapa para representar una lista de adyacencia.

class Grafo {
  constructor() {
    this.adjacencia = new Map();
  }

  agregarVertice(vertice) {
    if (!this.adjacencia.has(vertice)) {
      this.adjacencia.set(vertice, []);
    }
  }

  agregarArista(vertice1, vertice2) {
    if (this.adjacencia.has(vertice1)) {
      this.adjacencia.get(vertice1).push(vertice2);
    }
    if (this.adjacencia.has(vertice2)) {
      this.adjacencia.get(vertice2).push(vertice1); // Para grafos no dirigidos
    }
  }

  mostrar() {
    for (const [vertice, adyacentes] of this.adjacencia) {
      console.log(`${vertice} -> ${adyacentes.join(", ")}`);
    }
  }
}

const grafo = new Grafo();
grafo.agregarVertice("A");
grafo.agregarVertice("B");
grafo.agregarVertice("C");
grafo.agregarArista("A", "B");
grafo.agregarArista("A", "C");
grafo.mostrar();

// Salida:
// A -> B, C
// B -> A
// C -> A

C#
Un grafo puede representarse utilizando un diccionario de listas para la lista de adyacencia.

using System;
using System.Collections.Generic;

class Grafo {
    private Dictionary<string, List<string>> adjacencia = new Dictionary<string, List<string>>();

    public void AgregarVertice(string vertice) {
        if (!adjacencia.ContainsKey(vertice)) {
            adjacencia[vertice] = new List<string>();
        }
    }

    public void AgregarArista(string vertice1, string vertice2) {
        adjacencia[vertice1].Add(vertice2);
        adjacencia[vertice2].Add(vertice1); // Para grafos no dirigidos
    }

    public void Mostrar() {
        foreach (var vertice in adjacencia) {
            Console.WriteLine($"{vertice.Key} -> {string.Join(", ", vertice.Value)}");
        }
    }
}

class Program {
    static void Main() {
        Grafo grafo = new Grafo();

        grafo.AgregarVertice("A");
        grafo.AgregarVertice("B");
        grafo.AgregarVertice("C");
        grafo.AgregarArista("A", "B");
        grafo.AgregarArista("A", "C");

        grafo.Mostrar();
    }
}

// Salida:
// A -> B, C
// B -> A
// C -> A

Java
Los grafos en java se pueden implementar usando un HashMap para una lista de adyacencia.

import java.util.*;

public class Grafo {
    private Map<String, List<String>> adjacencia = new HashMap<>();

    public void agregarVertice(String vertice) {
        adjacencia.putIfAbsent(vertice, new ArrayList<>());
    }

    public void agregarArista(String vertice1, String vertice2) {
        adjacencia.get(vertice1).add(vertice2);
        adjacencia.get(vertice2).add(vertice1); // Para grafos no dirigidos
    }

    public void mostrar() {
        for (String vertice : adjacencia.keySet()) {
            System.out.println(vertice + " -> " + String.join(", ", adjacencia.get(vertice)));
        }
    }

    public static void main(String[] args) {
        Grafo grafo = new Grafo();

        grafo.agregarVertice("A");
        grafo.agregarVertice("B");
        grafo.agregarVertice("C");
        grafo.agregarArista("A", "B");
        grafo.agregarArista("A", "C");

        grafo.mostrar();
    }
}

// Salida:
// A -> B, C
// B -> A
// C -> A

C
Los grafos pueden representarse mediante listas enlazadas o matrices.

#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTICES 10

typedef struct Nodo {
    int destino;
    struct Nodo* siguiente;
} Nodo;

typedef struct Grafo {
    Nodo* listaAdyacencia[MAX_VERTICES];
} Grafo;

Grafo* crearGrafo() {
    Grafo* grafo = (Grafo*)malloc(sizeof(Grafo));
    for (int i = 0; i < MAX_VERTICES; i++) {
        grafo->listaAdyacencia[i] = NULL;
    }
    return grafo;
}

void agregarArista(Grafo* grafo, int origen, int destino) {
    Nodo* nuevoNodo = (Nodo*)malloc(sizeof(Nodo));
    nuevoNodo->destino = destino;
    nuevoNodo->siguiente = grafo->listaAdyacencia[origen];
    grafo->listaAdyacencia[origen] = nuevoNodo;
}

void mostrarGrafo(Grafo* grafo, int numVertices) {
    for (int i = 0; i < numVertices; i++) {
        printf("Vertice %d: ", i);
        Nodo* temp = grafo->listaAdyacencia[i];
        while (temp) {
            printf("%d -> ", temp->destino);
            temp = temp->siguiente;
        }
        printf("NULL\n");
    }
}

int main() {
    Grafo* grafo = crearGrafo();
    agregarArista(grafo, 0, 1);
    agregarArista(grafo, 0, 2);
    agregarArista(grafo, 1, 2);
    mostrarGrafo(grafo, 3);
    return 0;
}

// Salida:
// Vertice 0: 2 -> 1 -> NULL
// Vertice 1: 2 -> NULL
// Vertice 2: NULL

C++
Puedes usar std::unordered_map a comparación del lenguaje de programación en C, para implementar una lista de adyacencia.

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

class Grafo {
    unordered_map<string, vector<string>> adjacencia;

public:
    void agregarVertice(string vertice) {
        adjacencia[vertice];
    }

    void agregarArista(string vertice1, string vertice2) {
        adjacencia[vertice1].push_back(vertice2);
        adjacencia[vertice2].push_back(vertice1); // Para grafos no dirigidos
    }

    void mostrar() {
        for (auto& vertice : adjacencia) {
            cout << vertice.first << " -> ";
            for (auto& adyacente : vertice.second) {
                cout << adyacente << " ";
            }
            cout << endl;
        }
    }
};

int main() {
    Grafo grafo;

    grafo.agregarVertice("A");
    grafo.agregarVertice("B");
    grafo.agregarVertice("C");
    grafo.agregarArista("A", "B");
    grafo.agregarArista("A", "C");

    grafo.mostrar();
    return 0;
}

// Salida:
// A -> B C
// B -> A
// C -> A