7. Grafos

#estructuraDeDatos #universidad

a. Definición

Un grafo es una estructura de datos compuesta por un conjunto de nodos (o vértices) y un conjunto de aristas que conectan pares de nodos. Los grafos son utilizados para representar relaciones y conexiones entre objetos, siendo ampliamente aplicados en áreas como redes de computadoras, rutas de transporte, redes sociales, entre otros.

Terminología Básica:

• Vértice (Nodo): Entidad fundamental del grafo.
• Arista (Arco): Conexión entre dos vértices.
• Grafo Dirigido: Las aristas tienen una dirección específica (de un nodo a otro).
• Grafo No Dirigido: Las aristas no tienen dirección; la conexión es bidireccional.
• Peso (Costo): Valor asociado a una arista que puede representar distancia, tiempo, etc.
• Camino: Secuencia de vértices conectados por aristas.
• Ciclo: Camino que comienza y termina en el mismo vértice.
• Conectividad: Un grafo es conectado si existe al menos un camino entre cualquier par de vértices.

b. Tipos de Grafos

1. Grafos Dirigidos y No Dirigidos:

   • Dirigidos (Digrafos): Las aristas tienen una dirección específica.
     • Ejemplo: Redes de tráfico donde una calle puede ser de un solo sentido.
   • No Dirigidos: Las aristas no tienen dirección.
     • Ejemplo: Redes de amistad en redes sociales.

2. Grafos Ponderados y No Ponderados:

   • Ponderados: Las aristas tienen un peso o costo asociado.
     • Ejemplo: Distancias entre ciudades en un mapa.
   • No Ponderados: Las aristas no tienen peso.
     • Ejemplo: Relaciones de amistad sin prioridad.

3. Grafos Cíclicos y Acíclicos:

   • Cíclicos: Contienen al menos un ciclo.
   • Acíclicos: No contienen ciclos.
     • Ejemplo: Árboles son grafos acíclicos.

4. Grafos Conectados y Desconectados:

   • Conectados: Existe al menos un camino entre cualquier par de vértices.
   • Desconectados: Al menos un par de vértices no están conectados por ningún camino.

5. Grafos Completos:

   • Cada par de vértices está conectado por una única arista.

6. Grafos Bipartitos:

   • Los vértices pueden dividirse en dos conjuntos disjuntos donde cada arista conecta un vértice de un conjunto con uno del otro.

c. Representación de los Grafos

Existen varias formas de representar grafos en memoria, siendo las más comunes:

1. Lista de Adyacencia:

   • Para cada vértice, se mantiene una lista de los vértices adyacentes.
   • Ventajas: Eficiente en espacio para grafos dispersos.
   • Desventajas: Acceso menos rápido comparado con la matriz de adyacencia.

Ejemplo de Representación en C:

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

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

typedef struct {
    Nodo** listaAdyacencia;
    int numVertices;
} Grafo;

// Crear un nuevo nodo
Nodo* crearNodo(int vertice) {
    Nodo* nuevo = (Nodo*)malloc(sizeof(Nodo));
    nuevo->vertice = vertice;
    nuevo->siguiente = NULL;
    return nuevo;
}

// Crear un grafo
Grafo* crearGrafo(int vertices) {
    Grafo* grafo = (Grafo*)malloc(sizeof(Grafo));
    grafo->numVertices = vertices;

    grafo->listaAdyacencia = (Nodo**)malloc(vertices * sizeof(Nodo*));

    for (int i = 0; i < vertices; i++) {
        grafo->listaAdyacencia[i] = NULL;
    }

    return grafo;
}

// Agregar una arista
void agregarArista(Grafo* grafo, int origen, int destino) {
    // Agregar destino a la lista de origen
    Nodo* nuevo = crearNodo(destino);
    nuevo->siguiente = grafo->listaAdyacencia[origen];
    grafo->listaAdyacencia[origen] = nuevo;

    // Si el grafo es no dirigido, agregar origen a la lista de destino
    // Para grafo dirigido, comentar la siguiente parte
    nuevo = crearNodo(origen);
    nuevo->siguiente = grafo->listaAdyacencia[destino];
    grafo->listaAdyacencia[destino] = nuevo;
}

// Imprimir el grafo
void imprimirGrafo(Grafo* grafo) {
    for (int v = 0; v < grafo->numVertices; v++) {
        Nodo* temp = grafo->listaAdyacencia[v];
        printf("\n Lista de adyacencia del vertice %d\n head ", v);
        while (temp) {
            printf("-> %d", temp->vertice);
            temp = temp->siguiente;
        }
        printf("\n");
    }
}

int main() {
    int vertices = 5;
    Grafo* grafo = crearGrafo(vertices);

    agregarArista(grafo, 0, 1);
    agregarArista(grafo, 0, 4);
    agregarArista(grafo, 1, 2);
    agregarArista(grafo, 1, 3);
    agregarArista(grafo, 1, 4);
    agregarArista(grafo, 2, 3);
    agregarArista(grafo, 3, 4);

    imprimirGrafo(grafo);

    return 0;
}

Salida:

Lista de adyacencia del vertice 0
head -> 4 -> 1

Lista de adyacencia del vertice 1
head -> 4 -> 3 -> 2 -> 0

Lista de adyacencia del vertice 2
head -> 3 -> 1

Lista de adyacencia del vertice 3
head -> 4 -> 2 -> 1

Lista de adyacencia del vertice 4
head -> 3 -> 1 -> 0

2. Matriz de Adyacencia:

   • Utiliza una matriz bidimensional donde la celda [i][j] indica si existe una arista entre el vértice i y el vértice j.
   • Ventajas: Acceso rápido para verificar la existencia de una arista.
   • Desventajas: Consume más espacio, especialmente para grafos dispersos.

Ejemplo de Representación en C:

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

typedef struct {
    int numVertices;
    int** matrizAdyacencia;
} Grafo;

// Crear un grafo con matriz de adyacencia
Grafo* crearGrafo(int vertices) {
    Grafo* grafo = (Grafo*)malloc(sizeof(Grafo));
    grafo->numVertices = vertices;

    grafo->matrizAdyacencia = (int**)malloc(vertices * sizeof(int*));
    for (int i = 0; i < vertices; i++) {
        grafo->matrizAdyacencia[i] = (int*)malloc(vertices * sizeof(int));
        for (int j = 0; j < vertices; j++) {
            grafo->matrizAdyacencia[i][j] = 0;
        }
    }

    return grafo;
}

// Agregar una arista
void agregarArista(Grafo* grafo, int origen, int destino) {
    grafo->matrizAdyacencia[origen][destino] = 1;
    grafo->matrizAdyacencia[destino][origen] = 1; // Para grafo no dirigido
}

// Imprimir la matriz de adyacencia
void imprimirMatriz(Grafo* grafo) {
    printf("  ");
    for (int i = 0; i < grafo->numVertices; i++) {
        printf("%d ", i);
    }
    printf("\n");

    for (int i = 0; i < grafo->numVertices; i++) {
        printf("%d ", i);
        for (int j = 0; j < grafo->numVertices; j++) {
            printf("%d ", grafo->matrizAdyacencia[i][j]);
        }
        printf("\n");
    }
}

int main() {
    int vertices = 5;
    Grafo* grafo = crearGrafo(vertices);

    agregarArista(grafo, 0, 1);
    agregarArista(grafo, 0, 4);
    agregarArista(grafo, 1, 2);
    agregarArista(grafo, 1, 3);
    agregarArista(grafo, 1, 4);
    agregarArista(grafo, 2, 3);
    agregarArista(grafo, 3, 4);

    imprimirMatriz(grafo);

    return 0;
}

Salida:

  0 1 2 3 4 
0 0 1 0 0 1 
1 1 0 1 1 1 
2 0 1 0 1 0 
3 0 1 1 0 1 
4 1 1 0 1 0 

3. Lista de Adyacencia vs. Matriz de Adyacencia:

• Lista de Adyacencia:
  • Mejor para grafos dispersos.
  • Menor consumo de espacio.
  • Más eficiente para iterar sobre vecinos de un vértice.
• Matriz de Adyacencia:
  • Mejor para grafos densos.
  • Acceso rápido para verificar si existe una arista entre dos vértices.
  • Consume más espacio, especialmente para grafos grandes y dispersos.

d. Matriz de Adyacencia para los Pesos de un Grafo

Cuando las aristas tienen pesos asociados, la matriz de adyacencia puede almacenar estos valores en lugar de simples valores binarios. Si no hay conexión entre dos vértices, se puede usar un valor especial (como 0 o ∞) para indicar ausencia de arista.

Ejemplo de Matriz de Adyacencia Ponderada en C:

#include <stdio.h>
#include <stdlib.h>
#define INF 99999

typedef struct {
    int numVertices;
    int** matrizAdyacencia;
} GrafoPonderado;

// Crear un grafo ponderado con matriz de adyacencia
GrafoPonderado* crearGrafoPonderado(int vertices) {
    GrafoPonderado* grafo = (GrafoPonderado*)malloc(sizeof(GrafoPonderado));
    grafo->numVertices = vertices;

    grafo->matrizAdyacencia = (int**)malloc(vertices * sizeof(int*));
    for (int i = 0; i < vertices; i++) {
        grafo->matrizAdyacencia[i] = (int*)malloc(vertices * sizeof(int));
        for (int j = 0; j < vertices; j++) {
            if (i == j)
                grafo->matrizAdyacencia[i][j] = 0;
            else
                grafo->matrizAdyacencia[i][j] = INF;
        }
    }

    return grafo;
}

// Agregar una arista con peso
void agregarAristaPonderada(GrafoPonderado* grafo, int origen, int destino, int peso) {
    grafo->matrizAdyacencia[origen][destino] = peso;
    grafo->matrizAdyacencia[destino][origen] = peso; // Para grafo no dirigido
}

// Imprimir la matriz de adyacencia ponderada
void imprimirMatrizPonderada(GrafoPonderado* grafo) {
    printf("   ");
    for (int i = 0; i < grafo->numVertices; i++) {
        printf("%4d", i);
    }
    printf("\n");

    for (int i = 0; i < grafo->numVertices; i++) {
        printf("%2d ", i);
        for (int j = 0; j < grafo->numVertices; j++) {
            if (grafo->matrizAdyacencia[i][j] == INF)
                printf("  ∞ ");
            else
                printf("%4d", grafo->matrizAdyacencia[i][j]);
        }
        printf("\n");
    }
}

int main() {
    int vertices = 5;
    GrafoPonderado* grafo = crearGrafoPonderado(vertices);

    agregarAristaPonderada(grafo, 0, 1, 10);
    agregarAristaPonderada(grafo, 0, 4, 20);
    agregarAristaPonderada(grafo, 1, 2, 30);
    agregarAristaPonderada(grafo, 1, 3, 40);
    agregarAristaPonderada(grafo, 1, 4, 50);
    agregarAristaPonderada(grafo, 2, 3, 60);
    agregarAristaPonderada(grafo, 3, 4, 70);

    imprimirMatrizPonderada(grafo);

    return 0;
}

Salida:

      0   1   2   3   4
 0    0  10   ∞   ∞  20
 1   10    0  30  40  50
 2    ∞   30    0  60   ∞
 3    ∞   40  60    0  70
 4   20   50   ∞  70    0

Ejercicios

7. Grafos

1. Implementación de una Lista de Adyacencia para un Grafo Dirigido:

   • Implementa una lista de adyacencia en C para representar un grafo dirigido.
   • Incluye funciones para agregar aristas y mostrar la lista de adyacencia.

2. Búsqueda en Profundidad (DFS) y Búsqueda en Amplitud (BFS):

   • Implementa los algoritmos DFS y BFS para recorrer un grafo representado mediante una lista de adyacencia.
   • Realiza una búsqueda desde un vértice dado y muestra el orden de los vértices visitados.

3. Detección de Ciclos en un Grafo:

   • Escribe una función en C que detecte si un grafo no dirigido contiene algún ciclo.
   • Utiliza una técnica como DFS para la detección.

4. Matriz de Adyacencia Ponderada:

   • Crea una matriz de adyacencia ponderada para un grafo dado.
   • Implementa una función que imprima la matriz y otra que calcule la suma de todos los pesos.