Estructuras de datos - Grafos

Un grafo (Graph) es una estructura de datos no lineal más general, utilizada para representar relaciones complejas de "muchos a muchos" entre elementos, compuesta por vértices y aristas que conectan los vértices.


Conceptos básicos de los grafos

Tipos de grafos

Tipos de grafos — grafo no dirigido, grafo dirigido, grafo ponderado

Grafo no dirigido

0
—
1
Las aristas no tienen dirección, la conexión es recíproca
Ejemplo: relaciones de amistad en redes sociales

Grafo dirigido

0
→
1
Las aristas tienen dirección, conexión unidireccional
Ejemplo: relaciones de seguimiento, enlaces web

Grafo ponderado

0
5
1
Las aristas llevan un peso (distancia/costo)
Ejemplo: navegación por mapas, latencia de red

Formas de almacenamiento de grafos

Comparación de formas de almacenamiento

Matriz de adyacencia vs lista de adyacencia

Matriz de adyacencia

Complejidad espacialO(V²)
Comprobar si dos vértices están conectadosO(1)
Recorrer los vértices adyacentesO(V)
Adecuado para: grafos densos · int graph[V][V]

Lista de adyacencia

Complejidad espacialO(V+E)
Comprobar si dos vértices están conectadosO(grado)
Recorrer los vértices adyacentesO(grado)
Adecuado para: grafos dispersos · arreglo de listas enlazadas

Recorrido de grafos

DFS vs BFS — recorrido desde el vértice 0

DFS: búsqueda en profundidad

0→ 1→ 3→ 4→ 2→ 5
Recorre un camino hasta el final y luego retrocede
Implementación: recursión / pila | Adecuado para búsqueda de caminos, ordenamiento topológico

BFS: búsqueda en amplitud

0→ 1→ 2→ 3→ 4→ 5
Expande por niveles, visita primero los del mismo nivel
Implementación: cola | Naturalmente adecuado para el camino más corto en grafos no ponderados

Ejemplo

#include <stdio.h>
#include <stdbool.h>

#define V 6 /* número de vértices */

/* Grafo representado por matriz de adyacencia */
int graph[V][V] = {
    {0,1,1,0,0,0},  /* Relaciones de adyacencia del vértice 0 */
    {1,0,0,1,1,0},  /* Vértice 1 */
    {1,0,0,0,1,0},  /* Vértice 2 */
    {0,1,0,0,0,1},  /* Vértice 3 */
    {0,1,1,0,0,1},  /* Vértice 4 */
    {0,0,0,1,1,0}   /* Vértice 5 */
};
bool visited[V];

/* DFS: búsqueda en profundidad, implementación recursiva
Característica: recorre un camino hasta el final y luego retrocede, adecuado para búsqueda de caminos y verificación de conectividad */

void DFS(int v) {
    visited[v] = true;
    printf("%d ", v);         /* Visitar el vértice actual */
    for (int i = 0; i < V; i++) {
        if (graph[v][i] && !visited[i]) {
            DFS(i);  /* Visitar recursivamente los vértices adyacentes no visitados */
        }
    }
}

/* BFS: búsqueda en amplitud, implementación con cola
Característica: expande por niveles, naturalmente adecuado para resolver el camino más corto */

void BFS(int start) {
    bool visited[V] = {false};
    int queue[V];
    int front = 0, rear = 0;

    visited[start] = true;
    queue[rear++] = start;  /* Encolar el vértice inicial */

    while (front < rear) {
        int v = queue[front++];  /* Desencolar */
        printf("%d ", v);

        for (int i = 0; i < V; i++) {
            if (graph[v][i] && !visited[i]) {
                visited[i] = true;
                queue[rear++] = i;  /* Encolar los vértices adyacentes */
            }
        }
    }
}

int main() {
    /* Inicializar la marca de visitado */
    for (int i = 0; i < V; i++) visited[i] = false;

    printf("DFS (desde el vértice 0): ");
    DFS(0);  /* Salida: 0 1 3 5 4 2 */
    printf("\n");

    printf("BFS (desde el vértice 0): ");
    BFS(0);  /* Salida: 0 1 2 3 4 5 */
    printf("\n");
    return 0;
}

Escenarios de aplicación de los grafos

EscenarioAlgoritmos típicos
Camino más cortoDijkstra, Bellman-Ford (navegación por mapas)
Árbol de expansión mínimaPrim, Kruskal (optimización de cableado de red)
Ordenamiento topológicoAlgoritmo de Kahn (análisis de dependencias de tareas)
Análisis de redes socialesPageRank, detección de comunidades
Otras extensiones