Graph: caminos, redes y conexiones complejas

Lic. Carlos Enrique Loria Beeche.

Octavo artículo técnico de la saga “Estructuras de datos: cuando la memoria se convierte en inteligencia”

Este artículo forma parte de la saga que inicié con Estructuras de datos: cuando la memoria se convierte en inteligencia, donde presenté las ocho estructuras de datos fundamentales que hemos venido recorriendo paso a paso.

En las entregas anteriores estudiamos el array, el estacionamiento numerado de la memoria, la linked list, la búsqueda del tesoro en la memoria, la stack, la pila y el recuerdo del último paso, la queue, la cola y la justicia del turno, la hash table, encontrar sin buscar, el binary search tree, ordenar para encontrar mejor, y el heap, cuando la prioridad manda.

Ahora llegamos al graph, o grafo, una de las estructuras de datos más poderosas para representar relaciones.

Si el array nos habló de posiciones, la lista enlazada de enlaces, la pila de retorno, la cola de turno, la tabla hash de claves, el árbol de comparación y el heap de prioridad, el grafo nos abre una dimensión más amplia: la de las conexiones.

Un grafo nos enseña que muchos problemas no consisten en ordenar una lista, sino en descubrir relaciones, caminos y conexiones.

¿Qué es un graph?

Un graph, o grafo, es una estructura de datos formada por dos elementos principales:

Nodos, también llamados vértices.
Aristas, que representan conexiones entre los nodos.

Los nodos representan entidades. Las aristas representan relaciones.

Por ejemplo, si pensamos en ciudades conectadas por carreteras, cada ciudad puede ser un nodo y cada carretera puede ser una arista.

San José ---- Cartago
   |
   |
Alajuela ---- Heredia

En este ejemplo, las ciudades son nodos. Las conexiones entre ellas son aristas.

Un grafo permite modelar estructuras donde los elementos no están simplemente en fila, en pila, en cola o en jerarquía. Están conectados de muchas maneras posibles.

Nodos y aristas

El vocabulario básico del grafo es sencillo, pero muy importante.

Nodo o vértice

Un nodo representa un elemento del problema.

Puede ser una persona, una ciudad, una página web, una computadora, una tarea, una estación, un documento o cualquier entidad que queramos representar.

A     B     C

Aquí tenemos tres nodos: A, B y C.

Arista

Una arista representa una conexión entre dos nodos.

A ---- B

Aquí existe una conexión entre A y B.

Si agregamos más conexiones, el grafo empieza a tomar forma:

A ---- B
|      |
|      |
C ---- D

Ahora cada nodo puede conectarse con varios otros. Esa libertad hace que los grafos sean tan útiles para representar el mundo real.

El grafo no pregunta solamente “¿dónde está este dato?”, sino también “¿con quién está conectado?”

Grafos no dirigidos

Un grafo no dirigido representa conexiones en ambos sentidos.

Si A está conectado con B, entonces B también está conectado con A.

A ---- B

Un ejemplo cotidiano sería una amistad en una red social donde la relación es mutua. Si Carlos es amigo de Ana, Ana también es amiga de Carlos.

Otro ejemplo sería una carretera de doble vía entre dos ciudades.

Grafos dirigidos

Un grafo dirigido representa conexiones con dirección.

En este caso, una arista va de un nodo hacia otro.

A ----> B

Esto significa que existe una conexión desde A hacia B, pero no necesariamente desde B hacia A.

Un ejemplo claro es seguir a alguien en una red social. Yo puedo seguir a una persona, pero esa persona no necesariamente me sigue a mí.

Otro ejemplo son las dependencias entre tareas:

Instalar sistema ----> Configurar base de datos ----> Publicar aplicación

Hay un orden. Una tarea depende de otra. La dirección importa.

Grafos ponderados

Un grafo ponderado es un grafo donde las aristas tienen un valor asociado, llamado peso.

Ese peso puede representar distancia, costo, tiempo, dificultad, capacidad o cualquier medida relevante.

Por ejemplo:

San José -- 25 km -- Cartago
San José -- 20 km -- Heredia
Heredia  -- 15 km -- Alajuela

En un sistema de rutas, el peso puede ser la distancia entre ciudades. En una red de computadoras, puede ser el tiempo de respuesta. En logística, puede ser el costo de transporte.

Los grafos ponderados son fundamentales para resolver problemas de rutas, optimización y búsqueda de caminos mínimos.

Cuando las conexiones tienen costo, distancia o prioridad, el grafo deja de ser solo una red y se convierte en un mapa de decisiones.

Representar un grafo en memoria

Hay varias formas de representar un grafo en un programa. Dos de las más comunes son:

Matriz de adyacencia.
Lista de adyacencia.

Matriz de adyacencia

Una matriz de adyacencia usa una tabla para indicar si existe conexión entre dos nodos.

Supongamos este grafo:

A ---- B
|      |
|      |
C ---- D

Podemos representarlo con una matriz:

     A  B  C  D
A    0  1  1  0
B    1  0  0  1
C    1  0  0  1
D    0  1  1  0

Un 1 significa que existe conexión. Un 0 significa que no existe conexión.

La matriz de adyacencia es fácil de consultar. Para saber si A está conectado con B, revisamos la posición correspondiente en la tabla.

Pero tiene una desventaja: si hay muchos nodos y pocas conexiones, puede desperdiciar memoria, porque la matriz guarda espacio para todas las combinaciones posibles.

Lista de adyacencia

Una lista de adyacencia guarda, para cada nodo, la lista de nodos conectados a él.

El mismo grafo anterior podría representarse así:

A: B, C
B: A, D
C: A, D
D: B, C

Esta representación suele ser más eficiente cuando el grafo tiene muchos nodos pero relativamente pocas conexiones.

Por eso la lista de adyacencia se usa con mucha frecuencia en aplicaciones reales.

Representación	Ventaja	Limitación
Matriz de adyacencia	Permite consultar rápido si existe una conexión	Puede consumir mucha memoria
Lista de adyacencia	Usa memoria de forma más eficiente en grafos dispersos	Consultar una conexión específica puede requerir recorrer la lista

Recorrer un grafo

Una vez que tenemos un grafo, muchas veces necesitamos recorrerlo.

Dos recorridos fundamentales son:

BFS: Breadth-First Search, o búsqueda en anchura.
DFS: Depth-First Search, o búsqueda en profundidad.

BFS: búsqueda en anchura

La búsqueda en anchura explora primero los vecinos más cercanos antes de avanzar hacia niveles más lejanos.

Si empezamos en el nodo A, primero visitamos sus vecinos inmediatos. Luego visitamos los vecinos de esos vecinos.

        A
      /   \
     B     C
    /       \
   D         E

Un recorrido BFS desde A podría ser:

A, B, C, D, E

BFS suele usar una queue, o cola, porque procesa los nodos en el orden en que fueron descubiertos.

BFS explora primero lo cercano antes de avanzar hacia lo lejano.

DFS: búsqueda en profundidad

La búsqueda en profundidad explora un camino hasta donde sea posible antes de retroceder y probar otro camino.

En el mismo grafo:

        A
      /   \
     B     C
    /       \
   D         E

Un recorrido DFS desde A podría ser:

A, B, D, C, E

DFS suele usar una stack, o pila, ya sea de forma explícita o mediante recursividad.

DFS profundiza primero, retrocede después y continúa explorando caminos pendientes.

Operaciones básicas de un graph

Operación	Descripción	Costo típico
agregar nodo	Incluir una nueva entidad en el grafo	O(1)
agregar arista	Conectar dos nodos	O(1) en lista de adyacencia
eliminar nodo	Quitar un nodo y sus conexiones	Depende de la representación
eliminar arista	Quitar una conexión entre nodos	Depende de la representación
BFS	Recorrer por niveles usando cola	O(V + E)
DFS	Recorrer en profundidad usando pila o recursión	O(V + E)

En esta tabla, V representa la cantidad de vértices o nodos, y E representa la cantidad de aristas o conexiones.

Ejemplo en C++

En C++, podemos representar un grafo usando una lista de adyacencia con unordered_map y vector.

#include &lt;iostream&gt;
#include &lt;unordered_map&gt;
#include &lt;vector&gt;
#include &lt;queue&gt;
#include &lt;string&gt;
using namespace std;

class Grafo {
private:
    unordered_map&lt;string, vector&lt;string&gt;&gt; adyacencia;

public:
    void agregarArista(const string& origen, const string& destino) {
        adyacencia[origen].push_back(destino);
        adyacencia[destino].push_back(origen);
    }

    void imprimir() {
        for (const auto& par : adyacencia) {
            cout &lt;&lt; par.first &lt;&lt; ": ";

            for (const string& vecino : par.second) {
                cout &lt;&lt; vecino &lt;&lt; " ";
            }

            cout &lt;&lt; endl;
        }
    }

    void bfs(const string& inicio) {
        unordered_map&lt;string, bool&gt; visitado;
        queue&lt;string&gt; cola;

        visitado[inicio] = true;
        cola.push(inicio);

        while (!cola.empty()) {
            string actual = cola.front();
            cola.pop();

            cout &lt;&lt; actual &lt;&lt; " ";

            for (const string& vecino : adyacencia[actual]) {
                if (!visitado[vecino]) {
                    visitado[vecino] = true;
                    cola.push(vecino);
                }
            }
        }
    }
};

int main() {
    Grafo grafo;

    grafo.agregarArista("A", "B");
    grafo.agregarArista("A", "C");
    grafo.agregarArista("B", "D");
    grafo.agregarArista("C", "E");

    cout &lt;&lt; "Lista de adyacencia:" &lt;&lt; endl;
    grafo.imprimir();

    cout &lt;&lt; "Recorrido BFS desde A:" &lt;&lt; endl;
    grafo.bfs("A");

    return 0;
}

Este ejemplo crea un grafo no dirigido, lo imprime como lista de adyacencia y luego lo recorre usando BFS.

Ejemplo en C#

En C#, podemos representar un grafo usando un Dictionary donde cada nodo tiene una lista de vecinos.

using System;
using System.Collections.Generic;

class Grafo
{
    private Dictionary&lt;string, List&lt;string&gt;&gt; adyacencia = new Dictionary&lt;string, List&lt;string&gt;&gt;();

    public void AgregarArista(string origen, string destino)
    {
        if (!adyacencia.ContainsKey(origen))
        {
            adyacencia[origen] = new List&lt;string&gt;();
        }

        if (!adyacencia.ContainsKey(destino))
        {
            adyacencia[destino] = new List&lt;string&gt;();
        }

        adyacencia[origen].Add(destino);
        adyacencia[destino].Add(origen);
    }

    public void Imprimir()
    {
        foreach (var par in adyacencia)
        {
            Console.Write(par.Key + ": ");

            foreach (var vecino in par.Value)
            {
                Console.Write(vecino + " ");
            }

            Console.WriteLine();
        }
    }

    public void BFS(string inicio)
    {
        HashSet&lt;string&gt; visitados = new HashSet&lt;string&gt;();
        Queue&lt;string&gt; cola = new Queue&lt;string&gt;();

        visitados.Add(inicio);
        cola.Enqueue(inicio);

        while (cola.Count &gt; 0)
        {
            string actual = cola.Dequeue();
            Console.Write(actual + " ");

            foreach (string vecino in adyacencia[actual])
            {
                if (!visitados.Contains(vecino))
                {
                    visitados.Add(vecino);
                    cola.Enqueue(vecino);
                }
            }
        }
    }
}

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

        grafo.AgregarArista("A", "B");
        grafo.AgregarArista("A", "C");
        grafo.AgregarArista("B", "D");
        grafo.AgregarArista("C", "E");

        Console.WriteLine("Lista de adyacencia:");
        grafo.Imprimir();

        Console.WriteLine("Recorrido BFS desde A:");
        grafo.BFS("A");
    }
}

En este ejemplo usamos Dictionary, List, HashSet y Queue. Es interesante notar cómo varias estructuras de datos trabajan juntas para resolver el recorrido del grafo.

Ejemplo en Python

En Python podemos representar un grafo mediante un diccionario donde cada clave es un nodo y cada valor es una lista de vecinos.

from collections import deque

grafo = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A", "E"],
    "D": ["B"],
    "E": ["C"]
}

def bfs(grafo, inicio):
    visitados = set()
    cola = deque()

    visitados.add(inicio)
    cola.append(inicio)

    while cola:
        actual = cola.popleft()
        print(actual, end=" ")

        for vecino in grafo[actual]:
            if vecino not in visitados:
                visitados.add(vecino)
                cola.append(vecino)

print("Recorrido BFS desde A:")
bfs(grafo, "A")

Este ejemplo usa un dict para la lista de adyacencia, un set para recordar los nodos visitados y una deque para implementar la cola del recorrido BFS.

DFS en Python

También podemos implementar búsqueda en profundidad con recursividad:

grafo = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A", "E"],
    "D": ["B"],
    "E": ["C"]
}

def dfs(grafo, actual, visitados):
    visitados.add(actual)
    print(actual, end=" ")

    for vecino in grafo[actual]:
        if vecino not in visitados:
            dfs(grafo, vecino, visitados)

print("Recorrido DFS desde A:")
dfs(grafo, "A", set())

En este caso, la recursividad funciona como una pila implícita. El algoritmo profundiza por un camino, retrocede y continúa por otros caminos pendientes.

¿Cuándo conviene usar un graph?

Un grafo conviene cuando el problema principal no es simplemente guardar datos, sino representar relaciones entre ellos.

Algunos casos típicos son:

Redes sociales.
Mapas y sistemas de rutas.
Conexiones entre computadoras.
Dependencias entre tareas.
Relaciones entre documentos.
Recomendaciones entre productos o contenidos.
Grafos de conocimiento.
Compiladores y análisis de dependencias.
Juegos y navegación de personajes.
Optimización logística.

Cuando queremos responder preguntas sobre conexiones, caminos, cercanía, dependencia o alcance, probablemente estamos ante un problema de grafos.

Aplicaciones reales

Los grafos aparecen en muchos sistemas modernos.

Redes sociales

En una red social, cada usuario puede verse como un nodo y cada relación como una arista. Seguir, ser amigo, compartir, recomendar o interactuar son formas de conexión.

Mapas y navegación

En un sistema de mapas, las intersecciones, ciudades o puntos de interés pueden representarse como nodos, y las calles o carreteras como aristas. Si las aristas tienen peso, podemos representar distancia, tiempo o costo.

Internet

Las computadoras, servidores y routers pueden verse como nodos conectados por enlaces de red.

Dependencias de software

Un proyecto puede depender de bibliotecas, módulos o servicios. Esas dependencias forman un grafo dirigido.

Recomendaciones

Un sistema puede conectar usuarios con productos, películas, canciones, libros o artículos, formando redes que ayudan a sugerir contenidos relacionados.

Comparación con estructuras anteriores

El grafo es más general que muchas estructuras anteriores.

Estructura	Idea central	Pregunta típica
Array	Posición	¿Qué hay en este índice?
Linked List	Enlace al siguiente	¿Cuál es el próximo nodo?
Stack	Retorno	¿Qué fue lo último que quedó pendiente?
Queue	Turno	¿Quién llegó primero?
Hash Table	Clave	¿Qué valor corresponde a esta clave?
Binary Search Tree	Comparación	¿Voy a la izquierda o a la derecha?
Heap	Prioridad	¿Qué elemento debe salir primero?
Graph	Conexión	¿Cómo se relacionan estos elementos?

El grafo permite modelar relaciones que no caben cómodamente en una lista, una pila, una cola o un árbol simple.

La lección del grafo

El grafo nos enseña que la realidad rara vez es una simple línea.

Muchas veces los datos se parecen más a una red: personas conectadas, ciudades comunicadas, rutas alternativas, sistemas dependientes unos de otros, ideas relacionadas, documentos vinculados y caminos posibles.

El array nos enseñó el poder del índice. La lista enlazada nos enseñó el valor del enlace. La pila nos enseñó el valor del retorno. La cola nos enseñó el valor del turno. La tabla hash nos enseñó el poder de la clave. El árbol binario de búsqueda nos enseñó el valor de comparar. El heap nos enseñó el valor de priorizar. El grafo nos enseña el valor de conectar.

El grafo nos recuerda que entender un sistema no es solo conocer sus partes, sino descubrir cómo se relacionan entre sí.

Cierre de la saga

Con el grafo llegamos al final de esta primera saga sobre estructuras de datos fundamentales.

Hemos recorrido ocho formas distintas de organizar información:

Array: memoria ordenada por posición.
Linked List: nodos conectados por referencias.
Stack: último en entrar, primero en salir.
Queue: primero en entrar, primero en salir.
Hash Table: búsqueda rápida por clave.
Binary Search Tree: comparación y orden jerárquico.
Heap: prioridad en la raíz.
Graph: relaciones, caminos y conexiones.

Cada estructura ofrece una manera distinta de pensar. Ninguna sirve para todo. Cada una tiene ventajas, costos y situaciones donde brilla especialmente.

La verdadera habilidad no está en memorizar nombres, sino en aprender a escoger. Elegir la estructura adecuada es una de las decisiones más importantes al diseñar software.

Y al final volvemos a la idea que dio origen a esta serie: la memoria, cuando se organiza bien, puede convertirse en inteligencia.