El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
HOME Mis cursos Finalizados
◄ Anterior
◄

Ejercicios con Grafos

Siguiente ►
►

En esta sección, pondremos en práctica los conceptos aprendidos sobre grafos mediante una serie de ejercicios. Cada ejercicio está diseñado para reforzar tu comprensión y habilidades en la manipulación y análisis de grafos. Asegúrate de intentar resolver cada ejercicio por tu cuenta antes de consultar las soluciones proporcionadas.

Ejercicio 1: Representación de Grafos

Enunciado

Dado el siguiente grafo no dirigido, represéntalo utilizando una lista de adyacencia y una matriz de adyacencia.

Grafo:
A - B
A - C
B - C
B - D
C - D

Solución

Lista de Adyacencia

grafo_lista_adyacencia = {
    'A': ['B', 'C'],
    'B': ['A', 'C', 'D'],
    'C': ['A', 'B', 'D'],
    'D': ['B', 'C']
}

Matriz de Adyacencia

# A  B  C  D
matriz_adyacencia = [
    [0, 1, 1, 0],  # A
    [1, 0, 1, 1],  # B
    [1, 1, 0, 1],  # C
    [0, 1, 1, 0]   # D
]

Explicación

  • Lista de Adyacencia: Cada nodo tiene una lista de nodos a los que está conectado.
  • Matriz de Adyacencia: Una matriz donde matriz_adyacencia[i][j] es 1 si hay una arista entre el nodo i y el nodo j, y 0 en caso contrario.

Ejercicio 2: Implementación de BFS (Breadth-First Search)

Enunciado

Implementa el algoritmo de búsqueda en anchura (BFS) para el siguiente grafo y encuentra el recorrido BFS comenzando desde el nodo 'A'.

Grafo:
A - B
A - C
B - D
C - E
D - F
E - F

Solución

from collections import deque

def bfs(grafo, inicio):
    visitados = set()
    cola = deque([inicio])
    recorrido = []

    while cola:
        nodo = cola.popleft()
        if nodo not in visitados:
            visitados.add(nodo)
            recorrido.append(nodo)
            cola.extend(grafo[nodo])
    
    return recorrido

grafo = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['E'],
    'D': ['F'],
    'E': ['F'],
    'F': []
}

print(bfs(grafo, 'A'))

Explicación

  • Deque: Utilizamos una cola (deque) para mantener el orden de los nodos a visitar.
  • Visitados: Un conjunto para rastrear los nodos que ya hemos visitado.
  • Recorrido: Una lista para almacenar el orden en que visitamos los nodos.

Resultado

['A', 'B', 'C', 'D', 'E', 'F']

Ejercicio 3: Implementación de DFS (Depth-First Search)

Enunciado

Implementa el algoritmo de búsqueda en profundidad (DFS) para el siguiente grafo y encuentra el recorrido DFS comenzando desde el nodo 'A'.

Grafo:
A - B
A - C
B - D
C - E
D - F
E - F

Solución

def dfs(grafo, inicio, visitados=None):
    if visitados is None:
        visitados = set()
    visitados.add(inicio)
    recorrido = [inicio]

    for vecino in grafo[inicio]:
        if vecino not in visitados:
            recorrido.extend(dfs(grafo, vecino, visitados))
    
    return recorrido

grafo = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['E'],
    'D': ['F'],
    'E': ['F'],
    'F': []
}

print(dfs(grafo, 'A'))

Explicación

  • Recursión: Utilizamos la recursión para explorar cada nodo y sus vecinos.
  • Visitados: Un conjunto para rastrear los nodos que ya hemos visitado.
  • Recorrido: Una lista para almacenar el orden en que visitamos los nodos.

Resultado

['A', 'B', 'D', 'F', 'C', 'E']

Ejercicio 4: Algoritmo de Dijkstra

Enunciado

Implementa el algoritmo de Dijkstra para encontrar el camino más corto desde el nodo 'A' al nodo 'F' en el siguiente grafo ponderado.

Grafo:
A - B (1)
A - C (4)
B - C (2)
B - D (5)
C - D (1)
D - F (2)
C - E (3)
E - F (1)

Solución

import heapq

def dijkstra(grafo, inicio):
    distancias = {nodo: float('inf') for nodo in grafo}
    distancias[inicio] = 0
    cola_prioridad = [(0, inicio)]
    camino = {}

    while cola_prioridad:
        distancia_actual, nodo_actual = heapq.heappop(cola_prioridad)

        if distancia_actual > distancias[nodo_actual]:
            continue

        for vecino, peso in grafo[nodo_actual].items():
            distancia = distancia_actual + peso

            if distancia < distancias[vecino]:
                distancias[vecino] = distancia
                camino[vecino] = nodo_actual
                heapq.heappush(cola_prioridad, (distancia, vecino))
    
    return distancias, camino

grafo = {
    'A': {'B': 1, 'C': 4},
    'B': {'C': 2, 'D': 5},
    'C': {'D': 1, 'E': 3},
    'D': {'F': 2},
    'E': {'F': 1},
    'F': {}
}

distancias, camino = dijkstra(grafo, 'A')
print("Distancias:", distancias)
print("Camino:", camino)

Explicación

  • Heapq: Utilizamos una cola de prioridad (heapq) para seleccionar el nodo con la menor distancia.
  • Distancias: Un diccionario para almacenar la distancia mínima desde el nodo inicial a cada nodo.
  • Camino: Un diccionario para rastrear el camino más corto.

Resultado

Distancias: {'A': 0, 'B': 1, 'C': 3, 'D': 4, 'E': 6, 'F': 6}
Camino: {'B': 'A', 'C': 'B', 'D': 'C', 'F': 'D'}

Conclusión

En esta sección, hemos practicado la representación de grafos, así como la implementación de algoritmos fundamentales como BFS, DFS y Dijkstra. Estos ejercicios te ayudarán a consolidar tu comprensión de los grafos y sus aplicaciones en la programación. Asegúrate de revisar y entender cada solución antes de pasar al siguiente módulo.

◄ Anterior
◄
Siguiente ►
►
El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
© Copyright 2024. Todos los derechos reservados