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 grafosTipos 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
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
Ejemplo: relaciones de seguimiento, enlaces web
Grafo ponderado
0
51
Las aristas llevan un peso (distancia/costo)
Ejemplo: navegación por mapas, latencia de red
Ejemplo: navegación por mapas, latencia de red
Formas de almacenamiento de grafos
Comparación de formas de almacenamientoMatriz 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;
}
#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
| Escenario | Algoritmos típicos |
|---|---|
| Camino más corto | Dijkstra, Bellman-Ford (navegación por mapas) |
| Árbol de expansión mínima | Prim, Kruskal (optimización de cableado de red) |
| Ordenamiento topológico | Algoritmo de Kahn (análisis de dependencias de tareas) |
| Análisis de redes sociales | PageRank, detección de comunidades |