¿Alguna vez te has preguntado cómo funciona el GPS para encontrar la ruta más corta? ¿O cómo las redes sociales sugieren amigos? Detrás de estas aplicaciones cotidianas se esconde una poderosa estructura de datos: los grafos.
Anteriormente conociste otras estructuras de datos. En este post, explorarás qué son los grafos, sus elementos, tipos y cómo se utilizan en la programación. Y se usará python para dar los ejemplos.
¿Qué es un Grafo?
Imagina un mapa de ciudades conectadas por carreteras: las ciudades serían los nodos y las carreteras los bordes. Un grafo es un conjunto de nodos. Y cada nodo está conectado a los bordes. Los nodos se les llama vertices y a los bordes son llamado aristas.
Elementos de un Grafo
Son dos los elementos que representa a un grafo:
- Nodos (Vértices): Representan entidades o puntos de datos.
- Bordes (Aristas): Conexiones entre los nodos que representan relaciones o transiciones.
Tipos de Grafos
Existen varias formas de representar a un grafo:
- Grafos Dirigidos: Los bordes tienen una dirección específica.
- Grafos No Dirigidos: Los bordes no tienen dirección.
- Grafos Ponderados: Los bordes tienen un peso o valor asociado.
- Grafos No Ponderados: Todos los bordes tienen el mismo valor.
- Grafos Cíclicos: Contienen al menos un ciclo (camino que comienza y termina en el mismo nodo).
- Grafos Acíclicos: No contienen ciclos.
Implementación de un Grafo en Python
Veamos cómo podemos implementar un grafo simple utilizando un diccionario en Python:
class Graph:
def __init__(self):
self.graph = {}
def add_node(self, node):
if node not in self.graph:
self.graph[node] = []
def add_edge(self, node1, node2):
if node1 not in self.graph:
self.add_node(node1)
if node2 not in self.graph:
self.add_node(node2)
self.graph[node1].append(node2)
self.graph[node2].append(node1) # Para grafos no dirigidos
def display(self):
for node in self.graph:
print(f"{node}: {' '.join(map(str, self.graph[node]))}")
# Ejemplo de uso
g = Graph()
g.add_edge(1, 2)
g.add_edge(2, 3)
g.add_edge(3, 1)
g.display()
Implementación de Grafos: Matriz de Adyacencia y Lista de Adyacencia
Existen dos formas principales de implementar un grafo en programación: la matriz de adyacencia y la lista de adyacencia. Ambas tienen sus ventajas y desventajas dependiendo del tipo de grafo y las operaciones que se necesiten realizar. Veamos cada una en detalle:
1. Matriz de Adyacencia
Una matriz de adyacencia es una matriz cuadrada de tamaño V x V. Donde V es el número de vértices en el grafo. El valor en la posición (i, j) de la matriz es 1. Ojo, esto ocurre si hay una arista del vértice i al vértice j. Es 0 en caso contrario.
Ventajas:
- Acceso rápido (O(1)) para verificar si existe una arista entre dos vértices.
- Fácil de implementar y entender.
Desventajas:
- Consume mucho espacio (O(V^2)) incluso para grafos dispersos.
- Agregar o eliminar un vértice es costoso (O(V^2)).
Implementación en Python:
class GraphMatrix:
def __init__(self, vertices):
self.V = vertices
self.graph = [[0 for _ in range(vertices)] for _ in range(vertices)]
def add_edge(self, u, v):
self.graph[u][v] = 1
self.graph[v][u] = 1 # Para grafos no dirigidos
def remove_edge(self, u, v):
self.graph[u][v] = 0
self.graph[v][u] = 0 # Para grafos no dirigidos
def print_graph(self):
for row in self.graph:
print(row)
# Ejemplo de uso
g = GraphMatrix(4)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(2, 3)
g.print_graph()
2. Lista de Adyacencia
Una lista de adyacencia es una colección de listas no ordenadas o arrays. El tamaño de la colección es igual al número de vértices. Cada lista describe los vértices adyacentes a un vértice particular.
Ventajas:
- Ahorra espacio en grafos dispersos O(V+E).
- Agregar un vértice es relativamente fácil.
Desventajas:
- El recorrido es más lento cuando verifica si existe la arista. Lo cual sería el peor caso con una complejidad de O(V)
Implementación en Python:
from collections import defaultdict
class GraphList:
def __init__(self):
self.graph = defaultdict(list)
def add_edge(self, u, v):
self.graph[u].append(v)
self.graph[v].append(u) # Para grafos no dirigidos
def remove_edge(self, u, v):
self.graph[u].remove(v)
self.graph[v].remove(u) # Para grafos no dirigidos
def print_graph(self):
for vertex in self.graph:
print(f"{vertex}: {' '.join(map(str, self.graph[vertex]))}")
# Ejemplo de uso
g = GraphList()
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(2, 3)
g.print_graph()
Ambas implementaciones tienen sus usos específicos. La matriz de adyacencia es preferible cuando el grafo es denso y se necesitan operaciones rápidas de verificación de aristas.
Y la lista de adyacencia es más eficiente en términos de espacio para grafos dispersos. Además, es preferible cuando se necesita iterar sobre los vecinos de un vértice frecuentemente.
Complejidad Algorítmica de los Métodos del Grafo
Para un grafo con Matriz de Adyacencia la complejidad algoritmica de un grafo es en todos los casos: O(n^2)
Y para un grafo con Lista de Adyacencia, su complejidad es en el caso promedio O(n+m). Y en el peor caso, con un grafo completo, O(n^2)
Algoritmos Comunes en Grafos
Existen diversos algoritmos para recorrer un grafo. Algunos más optimos que otros. Estos 3 son los más comunes:
- Búsqueda en Amplitud (BFS): Con complejidad temporal O(V + E)
- Búsqueda en Profundidad (DFS): Con complejidad temporal O(V + E)
- Algoritmo de Dijkstra (camino más corto): Con complejidad temporal O((V + E) log V)
Veamos un ejemplo de implementación de BFS:
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
visited.add(start)
while queue:
vertex = queue.popleft()
print(vertex, end=" ")
for neighbour in graph[vertex]:
if neighbour not in visited:
visited.add(neighbour)
queue.append(neighbour)
# Ejemplo de uso
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
print("BFS partiendo del nodo 'A':")
bfs(graph, 'A')
Conclusión
Los grafos son una estructura de datos versátil y poderosa. Nos permite modelar una amplia gama de problemas del mundo real. Desde la optimización de rutas hasta el análisis de redes sociales, los grafos están en todas partes. Comprender sus fundamentos y cómo implementarlos es crucial para cualquier programador que busque expandir su conjunto de herramientas algorítmicas. Tambien es un plus a nivel laboral.
¿Te animas a implementar tu propio grafo y resolver problemas con él? Te invito a que lo intentes con tu lenguaje de programación favorito y lo compartas en la caja de comentarios.
Sigueme en mis redes sociales para más contenido