El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
HOME Els meus cursos Finalitzats
◄ Anterior
◄

Exercicis amb Grafs

Següent ►
►

En aquesta secció, treballarem amb diversos exercicis pràctics per reforçar els conceptes apresos sobre grafs. Aquests exercicis inclouen la representació de grafs, la implementació d'algoritmes de cerca i camins mínims, i l'aplicació de grafs a problemes reals.

Exercici 1: Representació de Grafs

Enunciat

Representa el següent graf no dirigit utilitzant una matriu d'adjacència i una llista d'adjacència:

A -- B
|    |
C -- D

Solució

Matriu d'Adjacència

    A B C D
  A 0 1 1 0
  B 1 0 0 1
  C 1 0 0 1
  D 0 1 1 0

Llista d'Adjacència

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

Exercici 2: Algoritme de Cerca en Ample (BFS)

Enunciat

Implementa l'algoritme de Cerca en Ample (BFS) per al graf representat en l'exercici anterior, començant pel node 'A'.

Solució

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    result = []

    while queue:
        vertex = queue.popleft()
        if vertex not in visited:
            visited.add(vertex)
            result.append(vertex)
            queue.extend([neighbor for neighbor in graph[vertex] if neighbor not in visited])

    return result

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

print(bfs(graph, 'A'))  # Output: ['A', 'B', 'C', 'D']

Exercici 3: Algoritme de Cerca en Profunditat (DFS)

Enunciat

Implementa l'algoritme de Cerca en Profunditat (DFS) per al graf representat en l'exercici 1, començant pel node 'A'.

Solució

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    result = [start]

    for neighbor in graph[start]:
        if neighbor not in visited:
            result.extend(dfs(graph, neighbor, visited))

    return result

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

print(dfs(graph, 'A'))  # Output: ['A', 'B', 'D', 'C']

Exercici 4: Algoritme de Dijkstra per a Camins Mínims

Enunciat

Implementa l'algoritme de Dijkstra per trobar el camí mínim des del node 'A' a tots els altres nodes en el següent graf ponderat:

A --1-- B
|      /|
4    2  1
|  /    |
C --3-- D

Solució

import heapq

def dijkstra(graph, start):
    queue = [(0, start)]
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    while queue:
        current_distance, current_node = heapq.heappop(queue)
        if current_distance > distances[current_node]:
            continue
        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(queue, (distance, neighbor))
    return distances

graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 1},
    'C': {'A': 4, 'B': 2, 'D': 3},
    'D': {'B': 1, 'C': 3}
}

print(dijkstra(graph, 'A'))  # Output: {'A': 0, 'B': 1, 'C': 3, 'D': 2}

Exercici 5: Aplicació de Grafs

Enunciat

Considera un sistema de rutes d'autobusos on cada parada és un node i cada ruta és una aresta amb un pes que representa el temps de viatge. Representa el següent sistema de rutes utilitzant una llista d'adjacència i implementa una funció per trobar el camí més curt des de la parada 'P1' a la parada 'P4':

P1 --10-- P2
|       / |
5     15  5
|   /     |
P3 --10-- P4

Solució

def dijkstra(graph, start, end):
    queue = [(0, start)]
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    previous_nodes = {node: None for node in graph}
    
    while queue:
        current_distance, current_node = heapq.heappop(queue)
        
        if current_distance > distances[current_node]:
            continue
        
        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                previous_nodes[neighbor] = current_node
                heapq.heappush(queue, (distance, neighbor))
    
    path = []
    current_node = end
    while previous_nodes[current_node] is not None:
        path.append(current_node)
        current_node = previous_nodes[current_node]
    path.append(start)
    path.reverse()
    
    return path, distances[end]

graph = {
    'P1': {'P2': 10, 'P3': 5},
    'P2': {'P1': 10, 'P3': 15, 'P4': 5},
    'P3': {'P1': 5, 'P2': 15, 'P4': 10},
    'P4': {'P2': 5, 'P3': 10}
}

path, distance = dijkstra(graph, 'P1', 'P4')
print(f"Camí més curt: {path}, Distància: {distance}")  # Output: Camí més curt: ['P1', 'P3', 'P4'], Distància: 15

Conclusió

En aquesta secció, hem treballat amb diversos exercicis pràctics per reforçar els conceptes de grafs, incloent la representació de grafs, la implementació d'algoritmes de cerca (BFS i DFS) i l'algoritme de Dijkstra per a camins mínims. Aquests exercicis són fonamentals per comprendre com aplicar els grafs a problemes reals i optimitzar solucions en el camp de la programació.

◄ Anterior
◄
Següent ►
►
El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
© Copyright 2024. Tots els drets reservats