ESTRUCTURA DE DATOS Y ALGORITMOS
LABORATORIO N° 16
GRAFOS AVANZADOS
Alumno Nota
Urquizo Apaza, Josue Alessandro
Grupo D
Fecha de Entrega 08/07/2023
Docente Renato Usnayo Cáceres
DISEÑO Y DESARROLLO DE SOFTWARE
PROGRAMA DE FORMACIÓN REGULAR
Laboratorio de Estructura de Datos y Algoritmos Página | 1
OBJETIVOS:
• Conocer, comprender y aplicar el uso de grafos avanzados como una forma de almacenar datos
en la resolución de problemas de software.
SEGURIDAD:
Advertencia:
En este laboratorio está prohibida la manipulación del hardware, conexiones
eléctricas o de red; así como la ingestión de alimentos o bebidas.
FUNDAMENTO TEÓRICO:
• Revisar el texto guía que está en el campus Virtual.
NORMAS EMPLEADAS:
• No aplica
RECURSOS:
• En este laboratorio cada alumno trabajará con un equipo con Windows 10.
METODOLOGÍA PARA EL DESARROLLO DE LA TAREA:
• El desarrollo del laboratorio es individual.
PROCEDIMIENTO:
Nota:
Las secciones en cursivas son demostrativas, pero sirven para que usted pueda instalar las
herramientas de desarrollo en un equipo externo.
EJERCICIO DE APLICACIÓN
Ejemplo de cómo realizar una búsqueda en profundidad en un grafo y generar un gráfico utilizando
Python
import networkx as nx
import matplotlib.pyplot as plt
def dfs(graph, start):
visited = set() # Conjunto para almacenar los nodos visitados
stack = [start] # Pila para almacenar los nodos por visitar
DEPARTAMENTO DE TECNOLOGIA DIGITAL Y GESTION
Laboratorio de Estructura de Datos y Algoritmos Página | 2
while stack:
node = stack.pop() # Extraer el último nodo agregado a la pila
if node not in visited:
visited.add(node)
print(node) # Imprimir el nodo visitado
# Agregar los vecinos no visitados a la pila
neighbors = graph[node]
stack.extend([neighbor for neighbor in neighbors if neighbor not in visited])
def draw_graph(graph):
G = nx.Graph()
for node, neighbors in graph.items():
for neighbor in neighbors:
G.add_edge(node, neighbor)
pos = nx.spring_layout(G)
nx.draw(G, pos, with_labels=True, node_color='lightblue', node_size=500, edge_color='gray',
width=1, alpha=0.7)
plt.show()
# Grafo de ejemplo
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
# Realizar la búsqueda en profundidad desde el nodo 'A'
dfs(graph, 'A')
# Generar el gráfico del grafo
draw_graph(graph)
Explique que hace el código, Adjunte captura de ejecución y grafico mostrado
DEPARTAMENTO DE TECNOLOGIA DIGITAL Y GESTION
Laboratorio de Estructura de Datos y Algoritmos Página | 3
El código implementa la búsqueda en profundidad (DFS) en un grafo no dirigido. Utiliza una pila para
almacenar los nodos por visitar y un conjunto para registrar los nodos visitados. Comienza desde un
nodo de inicio dado y explora los nodos vecinos de forma recursiva, imprimiendo los nodos visitados.
Además, muestra una representación gráfica del grafo utilizando NetworkX y Matplotlib.
Ejemplo de cómo realizar una búsqueda en amplitud en un grafo y generar un gráfico utilizando Python
import networkx as nx
DEPARTAMENTO DE TECNOLOGIA DIGITAL Y GESTION
Laboratorio de Estructura de Datos y Algoritmos Página | 4
import matplotlib.pyplot as plt
def bfs(graph, start):
visited = set() # Conjunto para almacenar los nodos visitados
queue = [start] # Cola para almacenar los nodos por visitar
while queue:
node = queue.pop(0) # Extraer el primer nodo agregado a la cola
if node not in visited:
visited.add(node)
print(node) # Imprimir el nodo visitado
# Agregar los vecinos no visitados a la cola
neighbors = graph[node]
queue.extend([neighbor for neighbor in neighbors if neighbor not in visited])
def draw_graph(graph):
G = nx.Graph()
for node, neighbors in graph.items():
for neighbor in neighbors:
G.add_edge(node, neighbor)
pos = nx.spring_layout(G)
nx.draw(G, pos, with_labels=True, node_color='lightblue', node_size=500, edge_color='gray',
width=1, alpha=0.7)
plt.show()
# Grafo de ejemplo
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
# Realizar la búsqueda en amplitud desde el nodo 'A'
bfs(graph, 'A')
# Generar el gráfico del grafo
draw_graph(graph)
, Adjunte captura de ejecución y grafico mostrado
DEPARTAMENTO DE TECNOLOGIA DIGITAL Y GESTION
Laboratorio de Estructura de Datos y Algoritmos Página | 5
El código implementa la búsqueda en amplitud (BFS) en un grafo no dirigido. Utiliza una cola para
almacenar los nodos por visitar y un conjunto para registrar los nodos visitados. Comienza desde un
nodo de inicio dado y explora los nodos en el mismo nivel antes de pasar al siguiente nivel,
imprimiendo los nodos visitados. Además, muestra una representación gráfica del grafo utilizando
NetworkX y Matplotlib.
Ejemplo de cómo implementar el algoritmo de Dijkstra en Python
DEPARTAMENTO DE TECNOLOGIA DIGITAL Y GESTION
Laboratorio de Estructura de Datos y Algoritmos Página | 6
import networkx as nx
import matplotlib.pyplot as plt
import math
def dijkstra(graph, start):
# Inicializar las estructuras de datos
distance = {node: math.inf for node in graph}
distance[start] = 0
visited = set()
while len(visited) < len(graph):
# Encontrar el nodo con la distancia mínima
min_distance = math.inf
min_node = None
for node in graph:
if node not in visited and distance[node] < min_distance:
min_distance = distance[node]
min_node = node
if min_node is None:
break
visited.add(min_node)
# Actualizar las distancias de los nodos vecinos
for neighbor, weight in graph[min_node].items():
new_distance = distance[min_node] + weight
if new_distance < distance[neighbor]:
distance[neighbor] = new_distance
return distance
def draw_graph(graph):
G = nx.Graph()
for node, neighbors in graph.items():
for neighbor, weight in neighbors.items():
G.add_edge(node, neighbor, weight=weight)
pos = nx.spring_layout(G)
edge_labels = nx.get_edge_attributes(G, 'weight')
nx.draw(G, pos, with_labels=True, node_color='lightblue', node_size=500, edge_color='gray',
width=1, alpha=0.7)
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels)
plt.show()
# Grafo de ejemplo
graph = {
'A': {'B': 4, 'C': 2},
DEPARTAMENTO DE TECNOLOGIA DIGITAL Y GESTION
Laboratorio de Estructura de Datos y Algoritmos Página | 7
'B': {'A': 4, 'D': 5, 'E': 1},
'C': {'A': 2, 'F': 12},
'D': {'B': 5},
'E': {'B': 1, 'F': 3},
'F': {'C': 12, 'E': 3}
}
# Nodo de inicio
start_node = 'A'
# Ejecutar el algoritmo de Dijkstra
distances = dijkstra(graph, start_node)
print(distances)
# Generar el gráfico del grafo
draw_graph(graph)
Explique que hace el código, Adjunte captura de ejecución y grafico mostrado
DEPARTAMENTO DE TECNOLOGIA DIGITAL Y GESTION
Laboratorio de Estructura de Datos y Algoritmos Página | 8
Ejemplo de cómo implementar el algoritmo de Bellman-Ford en Python
import networkx as nx
import matplotlib.pyplot as plt
import math
def bellman_ford(graph, start):
# Inicializar las distancias a infinito excepto para el nodo de inicio
distance = {node: math.inf for node in graph}
distance[start] = 0
# Realizar el proceso de relajación de las aristas V-1 veces
for _ in range(len(graph) - 1):
for node in graph:
for neighbor, weight in graph[node].items():
DEPARTAMENTO DE TECNOLOGIA DIGITAL Y GESTION
Laboratorio de Estructura de Datos y Algoritmos Página | 9
new_distance = distance[node] + weight
if new_distance < distance[neighbor]:
distance[neighbor] = new_distance
# Verificar si hay ciclos de costo negativo
for node in graph:
for neighbor, weight in graph[node].items():
if distance[node] + weight < distance[neighbor]:
raise ValueError("El grafo contiene un ciclo de costo negativo")
return distance
def draw_graph(graph):
G = nx.Graph()
for node, neighbors in graph.items():
for neighbor, weight in neighbors.items():
G.add_edge(node, neighbor, weight=weight)
pos = nx.spring_layout(G)
edge_labels = nx.get_edge_attributes(G, 'weight')
nx.draw(G, pos, with_labels=True, node_color='lightblue', node_size=500, edge_color='gray',
width=1, alpha=0.7)
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels)
plt.show()
# Grafo de ejemplo
graph = {
'A': {'B': -1, 'C': 4},
'B': {'C': 3, 'D': 2, 'E': 2},
'C': {},
'D': {'B': 1, 'C': 5},
'E': {'D': -3}
}
# Nodo de inicio
start_node = 'A'
# Ejecutar el algoritmo de Bellman-Ford
distances = bellman_ford(graph, start_node)
print(distances)
# Generar el gráfico del grafo
draw_graph(graph)
Explique que hace el código, Adjunte captura de ejecución y grafico mostrado
DEPARTAMENTO DE TECNOLOGIA DIGITAL Y GESTION
Laboratorio de Estructura de Datos y Algoritmos Página | 10
El código implementa el algoritmo de Bellman-Ford para encontrar la distancia más corta desde un
nodo de inicio dado a todos los demás nodos en un grafo ponderado dirigido. Utiliza la técnica de
relajación de aristas para actualizar las distancias iterativamente. Además, verifica si hay ciclos de
costo negativo en el grafo. La función draw_graph se encarga de generar una representación gráfica
del grafo utilizando NetworkX y Matplotlib, donde los nodos se dibujan como círculos y las aristas se
etiquetan con los pesos correspondientes. Finalmente, se imprime el diccionario de distancias y se
muestra el gráfico del grafo en una ventana de visualización.
DEPARTAMENTO DE TECNOLOGIA DIGITAL Y GESTION
Laboratorio de Estructura de Datos y Algoritmos Página | 11
Tarea
Búsqueda en profundidad:
• Dado un grafo no dirigido, implementa una función que realice una búsqueda en profundidad
desde un nodo de inicio dado y devuelva la lista de nodos visitados en orden.
• Implementa una función que determine si hay un camino entre dos nodos en un grafo utilizando
la búsqueda en profundidad.
import networkx as nx
import matplotlib.pyplot as plt
def draw_graph(graph):
G = nx.Graph()
for node, neighbors in graph.items():
for neighbor in neighbors:
G.add_edge(node, neighbor)
pos = nx.spring_layout(G)
nx.draw(G, pos, with_labels=True, node_color='lightblue',
node_size=500, edge_color='gray', width=1, alpha=0.7)
plt.show()
def dfs(graph, start, end=None):
visited = []
stack = [start]
while stack:
node = stack.pop()
if node not in visited:
visited.append(node)
if node == end:
return True
neighbors = graph[node]
stack.extend([neighbor for neighbor in neighbors if neighbor
not in visited])
if end is not None:
return False
return visited
def draw_graph(graph):
DEPARTAMENTO DE TECNOLOGIA DIGITAL Y GESTION
Laboratorio de Estructura de Datos y Algoritmos Página | 12
G = nx.Graph()
for node, neighbors in graph.items():
for neighbor in neighbors:
G.add_edge(node, neighbor)
pos = nx.spring_layout(G)
nx.draw(G, pos, with_labels=True, node_color='lightblue',
node_size=500, edge_color='gray', width=1, alpha=0.7)
plt.show()
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
visited_nodes = dfs(graph, 'A')
print("Nodos visitados:", visited_nodes)
has_path = dfs(graph, 'A', 'F')
print("Hay un camino entre 'A' y 'F':", has_path)
draw_graph(graph)
DEPARTAMENTO DE TECNOLOGIA DIGITAL Y GESTION
Laboratorio de Estructura de Datos y Algoritmos Página | 13
Búsqueda en amplitud:
• Dado un grafo no dirigido, implementa una función que realice una búsqueda en amplitud
desde un nodo de inicio dado y devuelva la lista de nodos visitados en orden.
• Implementa una función que encuentre el camino más corto entre dos nodos en un grafo
utilizando la búsqueda en amplitud.
import networkx as nx
import matplotlib.pyplot as plt
from collections import deque
def bfs(graph, start, end=None):
visited = set()
queue = deque([(start, [start])])
while queue:
node, path = queue.popleft()
DEPARTAMENTO DE TECNOLOGIA DIGITAL Y GESTION
Laboratorio de Estructura de Datos y Algoritmos Página | 14
if node not in visited:
visited.add(node)
if node == end:
return path
neighbors = graph[node]
for neighbor in neighbors:
if neighbor not in visited:
queue.append((neighbor, path + [neighbor]))
return None
def draw_graph(graph):
G = nx.Graph()
for node, neighbors in graph.items():
for neighbor in neighbors:
G.add_edge(node, neighbor)
pos = nx.spring_layout(G)
nx.draw(G, pos, with_labels=True, node_color='lightblue',
node_size=500, edge_color='gray', width=1, alpha=0.7)
plt.show()
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
visited_nodes = bfs(graph, 'A')
print("Nodos visitados:", visited_nodes)
shortest_path = bfs(graph, 'A', 'F')
print("Camino más corto entre 'A' y 'F':", shortest_path)
draw_graph(graph)
DEPARTAMENTO DE TECNOLOGIA DIGITAL Y GESTION
Laboratorio de Estructura de Datos y Algoritmos Página | 15
Algoritmo de Dijkstra:
• Dado un grafo ponderado dirigido, implementa el algoritmo de Dijkstra para encontrar la
distancia más corta desde un nodo de inicio dado a todos los demás nodos. Devuelve las
distancias más cortas como un diccionario.
• Modifica la implementación de Dijkstra para que también devuelva el camino más corto desde
el nodo de inicio hasta cada uno de los otros nodos.
import networkx as nx
import matplotlib.pyplot as plt
import math
def dijkstra(graph, start):
distance = {node: math.inf for node in graph}
distance[start] = 0
visited = set()
previous = {}
DEPARTAMENTO DE TECNOLOGIA DIGITAL Y GESTION
Laboratorio de Estructura de Datos y Algoritmos Página | 16
while len(visited) < len(graph):
min_distance = math.inf
min_node = None
for node in graph:
if node not in visited and distance[node] < min_distance:
min_distance = distance[node]
min_node = node
if min_node is None:
break
visited.add(min_node)
for neighbor, weight in graph[min_node].items():
new_distance = distance[min_node] + weight
if new_distance < distance[neighbor]:
distance[neighbor] = new_distance
previous[neighbor] = min_node
return distance, previous
def shortest_path(previous, start, end):
path = [end]
while end != start:
end = previous[end]
path.append(end)
path.reverse()
return path
def draw_graph(graph):
G = nx.DiGraph()
for node, neighbors in graph.items():
for neighbor, weight in neighbors.items():
G.add_edge(node, neighbor, weight=weight)
pos = nx.spring_layout(G)
edge_labels = nx.get_edge_attributes(G, 'weight')
nx.draw(G, pos, with_labels=True, node_color='lightblue',
node_size=500, edge_color='gray', width=1, alpha=0.7)
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels)
plt.show()
graph = {
'A': {'B': 4, 'C': 2},
DEPARTAMENTO DE TECNOLOGIA DIGITAL Y GESTION
Laboratorio de Estructura de Datos y Algoritmos Página | 17
'B': {'A': 4, 'D': 5, 'E': 1},
'C': {'A': 2, 'F': 12},
'D': {'B': 5},
'E': {'B': 1, 'F': 3},
'F': {'C': 12, 'E': 3}
}
start_node = 'A'
end_node = 'F'
distances, previous_nodes = dijkstra(graph, start_node)
shortest_distance = distances[end_node]
shortest_path = shortest_path(previous_nodes, start_node, end_node)
print("Distancias más cortas:", distances)
print("Distancia más corta desde", start_node, "hasta", end_node, ":",
shortest_distance)
print("Camino más corto desde", start_node, "hasta", end_node, ":",
shortest_path)
draw_graph(graph)
DEPARTAMENTO DE TECNOLOGIA DIGITAL Y GESTION
Laboratorio de Estructura de Datos y Algoritmos Página | 18
Algoritmo de Bellman-Ford:
• Dado un grafo ponderado dirigido, implementa el algoritmo de Bellman-Ford para encontrar la
distancia más corta desde un nodo de inicio dado a todos los demás nodos. Asegúrate de
manejar correctamente los ciclos de costo negativo.
• Modifica la implementación de Bellman-Ford para que también devuelva el camino más corto
desde el nodo de inicio hasta cada uno de los otros nodos.
import networkx as nx
import matplotlib.pyplot as plt
import math
def bellman_ford(graph, start):
distance = {node: math.inf for node in graph}
distance[start] = 0
previous = {}
DEPARTAMENTO DE TECNOLOGIA DIGITAL Y GESTION
Laboratorio de Estructura de Datos y Algoritmos Página | 19
for _ in range(len(graph) - 1):
for node in graph:
for neighbor, weight in graph[node].items():
new_distance = distance[node] + weight
if new_distance < distance[neighbor]:
distance[neighbor] = new_distance
previous[neighbor] = node
for node in graph:
for neighbor, weight in graph[node].items():
if distance[node] + weight < distance[neighbor]:
raise ValueError("El grafo contiene un ciclo de costo
negativo")
return distance, previous
def shortest_path(previous, start, end):
path = [end]
while end != start:
end = previous[end]
path.append(end)
path.reverse()
return path
def draw_graph(graph):
G = nx.DiGraph()
for node, neighbors in graph.items():
for neighbor, weight in neighbors.items():
G.add_edge(node, neighbor, weight=weight)
pos = nx.spring_layout(G)
edge_labels = nx.get_edge_attributes(G, 'weight')
nx.draw(G, pos, with_labels=True, node_color='lightblue',
node_size=500, edge_color='gray', width=1, alpha=0.7)
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels)
plt.show()
graph = {
'A': {'B': -1, 'C': 4},
'B': {'C': 3, 'D': 2, 'E': 2},
'C': {},
'D': {'B': 1, 'C': 5},
'E': {'D': -3}
}
DEPARTAMENTO DE TECNOLOGIA DIGITAL Y GESTION
Laboratorio de Estructura de Datos y Algoritmos Página | 20
start_node = 'A'
distances, previous_nodes = bellman_ford(graph, start_node)
print("Distancias más cortas:", distances)
for node in graph:
if node != start_node:
path = shortest_path(previous_nodes, start_node, node)
print("Camino más corto desde", start_node, "hasta", node, ":",
path)
draw_graph(graph)
DEPARTAMENTO DE TECNOLOGIA DIGITAL Y GESTION
Laboratorio de Estructura de Datos y Algoritmos Página | 21
Adjuntar capturas importantes del código
Adjuntar capturas de la prueba del código, así como de su ejecución
Adjuntar el código en un zip, rar, Google drive o git
DEPARTAMENTO DE TECNOLOGIA DIGITAL Y GESTION
Laboratorio de Estructura de Datos y Algoritmos Página | 22
OBSERVACIONES:
1. Los grafos avanzados son una herramienta poderosa para representar y analizar relaciones
complejas entre entidades.
2. Los grafos avanzados pueden contener características adicionales, como pesos en las aristas,
direccionalidad, múltiples tipos de aristas o nodos, y atributos en los nodos y aristas.
3. Algoritmos como Dijkstra, Bellman-Ford, búsqueda en profundidad (DFS) y búsqueda en
amplitud (BFS) se utilizan comúnmente en grafos avanzados para resolver problemas de rutas
más cortas, caminos, conectividad y otros análisis de grafos.
4. Los grafos avanzados pueden ser visualizados de manera efectiva utilizando bibliotecas como
NetworkX y herramientas gráficas como Matplotlib.
5. La teoria de los grafos nos da conceptos solidos y tecnicas para el studio de grafos avanzados.
CONCLUSIONES:
1. Los grafos avanzados son una herramienta esencial en el análisis de datos y la modelización de
relaciones complejas en una amplia gama de campos.
2. Las características adicionales de los grafos avanzados permiten una representación más precisa
y detallada de las relaciones entre entidades.
3. Los algoritmos clásicos de grafos, como Dijkstra y Bellman-Ford, son fundamentales para
resolver problemas comunes en grafos avanzados, como encontrar rutas más cortas o analizar la
conectividad.
4. Cuando nos muestra los graficos, nos facilita analizar las relaciones.
5. El estudio de la teoría de grafos ofrece un marco sólido para comprender y analizar los
conceptos y propiedades de los grafos avanzados, lo que puede ser aplicado en diversos campos
y problemas del mundo real.
DEPARTAMENTO DE TECNOLOGIA DIGITAL Y GESTION
