Implementar la estructura de datos de graph en C
Esta publicación cubrirá estructura de datos del graph implementación en C usando una lista de adyacencia. La publicación cubrirá la implementación ponderada y no ponderada de graphs dirigidos y no dirigidos.
En la representación de la lista de adyacencia del graph, cada vértice del graph está asociado con la colección de sus vértices o aristas vecinos, es decir, cada vértice almacena una lista de vértices adyacentes.
Por ejemplo, para el graph anterior, a continuación se muestra la representación pictórica de la lista de adyacencia:
1. Implementación de graph dirigidos
A continuación se muestra la implementación en C de un graph dirigido usando una lista de adyacencia:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 |
#include <stdio.h> #include <stdlib.h> // Definir el número máximo de vértices en el graph #define N 6 // Estructura de datos para almacenar un objeto graph struct Graph { // Una array de punteros a Node para representar una lista de adyacencia struct Node* head[N]; }; // Estructura de datos para almacenar los nodos de la lista de adyacencia del graph struct Node { int dest; struct Node* next; }; // Estructura de datos para almacenar un borde de graph struct Edge { int src, dest; }; // Función para crear una lista de adyacencia desde bordes especificados struct Graph* createGraph(struct Edge edges[], int n) { // asignar almacenamiento para la estructura de datos del graph struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph)); // inicializa el puntero principal para todos los vértices for (int i = 0; i < N; i++) { graph->head[i] = NULL; } // agrega bordes al grafo dirigido uno por uno for (int i = 0; i < n; i++) { // obtener el vértice de origen y destino int src = edges[i].src; int dest = edges[i].dest; // asignar un nuevo nodo de lista de adyacencia de src a dest struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->dest = dest; // apunta el nuevo nodo al encabezado actual newNode->next = graph->head[src]; // apunta el puntero de la cabeza al nuevo nodo graph->head[src] = newNode; } return graph; } // Función para imprimir la representación de la lista de adyacencia de un graph void printGraph(struct Graph* graph) { for (int i = 0; i < N; i++) { // imprime el vértice actual y todos sus vecinos struct Node* ptr = graph->head[i]; while (ptr != NULL) { printf("(%d —> %d)\t", i, ptr->dest); ptr = ptr->next; } printf("\n"); } } // Implementación de grafos dirigidos en C int main(void) { // array de entrada que contiene los bordes del graph (según el diagrama anterior) // (x, y) par en la array representa un borde de x a y struct Edge edges[] = { {0, 1}, {1, 2}, {2, 0}, {2, 1}, {3, 2}, {4, 5}, {5, 4} }; // calcular el número total de aristas int n = sizeof(edges)/sizeof(edges[0]); // construye un grafo a partir de las aristas dadas struct Graph *graph = createGraph(edges, n); // Función para imprimir la representación de la lista de adyacencia de un graph printGraph(graph); return 0; } |
Resultado:
(0 —> 1)
(1 —> 2)
(2 —> 1) (2 —> 0)
(3 —> 2)
(4 —> 5)
(5 —> 4)
Como se desprende del código anterior, en un graph dirigido, solo creamos un borde a partir de src a dest en la lista de adyacencia. Ahora, si el graph no está dirigido, también necesitamos crear una arista a partir de dest a src en la lista de adyacencia, como se muestra a continuación:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 |
#include <stdio.h> #include <stdlib.h> // Definir el número máximo de vértices en el graph #define N 6 // Estructura de datos para almacenar un objeto graph struct Graph { // Una array de punteros a Node para representar una lista de adyacencia struct Node* head[N]; }; // Estructura de datos para almacenar los nodos de la lista de adyacencia del graph struct Node { int dest; struct Node* next; }; // Estructura de datos para almacenar un borde de graph struct Edge { int src, dest; }; // Función para crear una lista de adyacencia desde bordes especificados struct Graph* createGraph(struct Edge edges[], int n) { // asignar almacenamiento para la estructura de datos del graph struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph)); // inicializa el puntero principal para todos los vértices for (int i = 0; i < N; i++) { graph->head[i] = NULL; } // agrega bordes al grafo dirigido uno por uno for (int i = 0; i < n; i++) { // obtener el vértice de origen y destino int src = edges[i].src; int dest = edges[i].dest; // 1. asignar un nuevo nodo de lista de adyacencia de src a dest struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->dest = dest; // apunta el nuevo nodo al encabezado actual newNode->next = graph->head[src]; // apunta el puntero de la cabeza al nuevo nodo graph->head[src] = newNode; // 2. asignar un nuevo nodo de lista de adyacencia de `dest` a `src` newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->dest = src; // apunta el nuevo nodo al encabezado actual newNode->next = graph->head[dest]; // cambia el puntero principal para que apunte al nuevo nodo graph->head[dest] = newNode; } return graph; } // Función para imprimir la representación de la lista de adyacencia de un graph void printGraph(struct Graph* graph) { for (int i = 0; i < N; i++) { // imprime el vértice actual y todos sus vecinos struct Node* ptr = graph->head[i]; while (ptr != NULL) { printf("(%d —> %d)\t", i, ptr->dest); ptr = ptr->next; } printf("\n"); } } // Implementación de grafos dirigidos en C int main(void) { // array de entrada que contiene los bordes del graph (según el diagrama anterior) // (x, y) par en la array representa un borde de x a y struct Edge edges[] = { {0, 1}, {1, 2}, {2, 0}, {2, 1}, {3, 2}, {4, 5}, {5, 4} }; // calcular el número total de aristas int n = sizeof(edges)/sizeof(edges[0]); // construye un grafo a partir de las aristas dadas struct Graph *graph = createGraph(edges, n); // Función para imprimir la representación de la lista de adyacencia de un graph printGraph(graph); return 0; } |
Resultado:
(0 —> 2) (0 —> 1)
(1 —> 2) (1 —> 2) (1 —> 0)
(2 —> 3) (2 —> 1) (2 —> 0) (2 —> 1)
(3 —> 2)
(4 —> 5) (4 —> 5)
(5 —> 4) (5 —> 4)
2. Implementación de graph dirigidos ponderados
En un graph ponderado, cada borde tendrá un peso (o costo) asociado, como se muestra a continuación:
A continuación se muestra la implementación de un graph dirigido ponderado en C utilizando la lista de adyacencia. La implementación es similar a la de un graph dirigido no ponderado, excepto que también almacenamos inarray de peso junto con cada borde.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 |
#include <stdio.h> #include <stdlib.h> // Definir el número máximo de vértices en el graph #define N 6 // Estructura de datos para almacenar un objeto graph struct Graph { // Una array de punteros a Node para representar una lista de adyacencia struct Node* head[N]; }; // Estructura de datos para almacenar los nodos de la lista de adyacencia del graph struct Node { int dest, weight; struct Node* next; }; // Estructura de datos para almacenar un borde de graph struct Edge { int src, dest, weight; }; // Función para crear una lista de adyacencia desde bordes especificados struct Graph* createGraph(struct Edge edges[], int n) { // asignar almacenamiento para la estructura de datos del graph struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph)); // inicializa el puntero principal para todos los vértices for (int i = 0; i < N; i++) { graph->head[i] = NULL; } // agrega bordes al grafo dirigido uno por uno for (int i = 0; i < n; i++) { // obtener el vértice de origen y destino int src = edges[i].src; int dest = edges[i].dest; int weight = edges[i].weight; // asignar un nuevo nodo de lista de adyacencia de src a dest struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->dest = dest; newNode->weight = weight; // apunta el nuevo nodo al encabezado actual newNode->next = graph->head[src]; // apunta el puntero de la cabeza al nuevo nodo graph->head[src] = newNode; } return graph; } // Función para imprimir la representación de la lista de adyacencia de un graph void printGraph(struct Graph* graph) { for (int i = 0; i < N; i++) { // imprime el vértice actual y todos sus vecinos struct Node* ptr = graph->head[i]; while (ptr != NULL) { printf("%d —> %d (%d)\t", i, ptr->dest, ptr->weight); ptr = ptr->next; } printf("\n"); } } // Implementación de graph dirigido ponderado en C int main(void) { // array de entrada que contiene los bordes del graph (según el diagrama anterior) // (x, y, w) la tupla representa una arista de x a y con peso `w` struct Edge edges[] = { {0, 1, 6}, {1, 2, 7}, {2, 0, 5}, {2, 1, 4}, {3, 2, 10}, {4, 5, 1}, {5, 4, 3} }; // calcular el número total de aristas int n = sizeof(edges)/sizeof(edges[0]); // construye un grafo a partir de las aristas dadas struct Graph *graph = createGraph(edges, n); // Función para imprimir la representación de la lista de adyacencia de un graph printGraph(graph); return 0; } |
Resultado:
0 —> 1 (6)
1 —> 2 (7)
2 —> 1 (4) 2 —> 0 (5)
3 —> 2 (10)
4 —> 5 (1)
5 —> 4 (3)
Para graphs ponderados no dirigidos (como se vio antes para graphs no ponderados no dirigidos), cree una ruta desde dest a src también en la lista de adyacencia. La implementación completa se puede ver aquí.
Ver también: