Estructuras de Datos

0x0042 INICIALIZANDO...
0x7ffe-stack
*p = malloc(sizeof(Node))
0x3b2a - heap
ptr -> next = NULL
Unidad 13

Grafos

Un Grafo es un conjunto de objetos llamados vértices (o nodos) unidos por enlaces llamados aristas. A diferencia de los árboles, en un grafo no hay jerarquía estricta (padre-hijo) y se permiten ciclos (caminos cerrados). Pueden ser Dirigidos (flechas) o No Dirigidos (líneas).

Imagen 50. Elementos de un Grafo (Vértices y Aristas)

Imagen 50. Elementos de un Grafo (Vértices y Aristas)

Elementos fundamentales: Visualización de Vértices (V) conectados por Aristas (E). Diferencia visual entre un grafo dirigido (con flechas) y uno no dirigido.

13.1 Teoría de Grafos: El mundo conectado
Mirar en YouTube

No existe un tipo de dato "Grafo" nativo. Tenemos dos formas principales de representarlo: 1) Matriz de Adyacencia (tabla 2D de ceros y unos, rápida pero gasta mucha memoria) o 2) Lista de Adyacencia (array de listas enlazadas, eficiente en memoria para grafos dispersos).

13.2 Representación: Matriz vs Lista
Mirar en YouTube
Imagen 51. Matriz de Adyacencia vs Lista de Adyacencia

Imagen 51. Matriz de Adyacencia vs Lista de Adyacencia

Esquema técnico: El mismo grafo representado a la izquierda como una cuadrícula (Matriz) y a la derecha como cadenas de nodos (Listas).

Para explorar un grafo tenemos dos estrategias: BFS (Breadth First Search) que explora por "capas" o niveles usando una Cola; y DFS (Depth First Search) que se adentra lo más posible en una rama antes de retroceder, usando una Pila (o recursividad).

13.3 Recorridos: BFS vs DFS
Mirar en YouTube
Imagen 52. Comparación de rutas de recorrido BFS y DFS

Imagen 52. Comparación de rutas de recorrido BFS y DFS

Orden de visita: Diagrama numerado mostrando el orden en que se visitan los nodos. BFS prioriza vecinos cercanos, DFS prioriza caminos largos.

Implementaremos un Grafo usando Listas de Adyacencia, ya que es la forma más versátil. Usaremos un struct "Grafo" que contiene un array de punteros. Cada puntero es la cabeza de una lista enlazada que contiene los vecinos de ese vértice.

main.cpp
struct Nodo {
    int destino;
    struct Nodo* siguiente;
};

struct Grafo {
    int numVertices;
    struct Nodo** adjLists; // Array de punteros a cabezas
    int* visitado;
};

struct Grafo* crearGrafo(int vertices) {
    struct Grafo* grafo = malloc(sizeof(struct Grafo));
    grafo->numVertices = vertices;
    grafo->adjLists = malloc(vertices * sizeof(struct Nodo*));
    // Inicializar listas en NULL...
    return grafo;
}
struct Nodo {
    int destino;
    struct Nodo* siguiente;
};

struct Grafo {
    int numVertices;
    struct Nodo** adjLists; // Array de punteros a cabezas
    int* visitado;
};

struct Grafo* crearGrafo(int vertices) {
    struct Grafo* grafo = malloc(sizeof(struct Grafo));
    grafo->numVertices = vertices;
    grafo->adjLists = malloc(vertices * sizeof(struct Nodo*));
    // Inicializar listas en NULL...
    return grafo;
}
13.4 Implementación de Grafo en C
Mirar en YouTube
Imagen 53. Implementación de Lista de Adyacencia en C

Imagen 53. Implementación de Lista de Adyacencia en C

Diagrama de implementación: Muestra el "Array Principal" (índices 0 a N) donde de cada celda cuelga una lista enlazada de vecinos.

Volver al nivel