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

Cerca en Grafs: BFS i DFS

Següent ►
►

Introducció

En aquest tema, explorarem dos dels algorismes més fonamentals per a la cerca en grafs: la Cerca en Amplada (BFS) i la Cerca en Profunditat (DFS). Aquests algorismes són essencials per a moltes aplicacions en informàtica, incloent la navegació de xarxes, la resolució de puzles i la cerca de camins en mapes.

Conceptes Clau

Graf

Un graf és una estructura composta per nodes (o vèrtexs) i arestes que connecten aquests nodes. Els grafs poden ser dirigits o no dirigits, ponderats o no ponderats.

BFS (Breadth-First Search)

La Cerca en Amplada explora els nodes d'un graf nivell per nivell. És a dir, primer visita tots els nodes a una distància de 1 del node inicial, després tots els nodes a una distància de 2, i així successivament.

DFS (Depth-First Search)

La Cerca en Profunditat explora tan profundament com sigui possible al llarg de cada branca abans de retrocedir. Això significa que segueix un camí fins arribar al final abans de tornar enrere i explorar altres camins.

Algorisme BFS

Pseudocodi

BFS(Graf G, Node inicial s):
    Crear una cua Q
    Marcar s com visitat i afegir-lo a Q
    mentre Q no estigui buida:
        u = Q.desencuar()
        per cada veí v de u:
            si v no ha estat visitat:
                marcar v com visitat
                afegir v a Q

Implementació en Python

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 neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

# Exemple de graf
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

bfs(graph, 'A')

Explicació del Codi

  1. Utilitzem una cua (deque) per mantenir els nodes a visitar.
  2. Afegim el node inicial a la cua i el marquem com visitat.
  3. Mentre la cua no estigui buida, desencuem un node, el processem i afegim els seus veïns no visitats a la cua.

Algorisme DFS

Pseudocodi

DFS(Graf G, Node inicial s):
    Crear una pila S
    Marcar s com visitat i afegir-lo a S
    mentre S no estigui buida:
        u = S.desapilar()
        per cada veí v de u:
            si v no ha estat visitat:
                marcar v com visitat
                afegir v a S

Implementació en Python

def dfs(graph, start):
    visited = set()
    stack = [start]
    
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            print(vertex, end=" ")
            visited.add(vertex)
            stack.extend(set(graph[vertex]) - visited)

# Exemple de graf
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

dfs(graph, 'A')

Explicació del Codi

  1. Utilitzem una pila per mantenir els nodes a visitar.
  2. Afegim el node inicial a la pila.
  3. Mentre la pila no estigui buida, desapilem un node, el processem i afegim els seus veïns no visitats a la pila.

Comparació entre BFS i DFS

Característica BFS DFS
Estructura de Dades Cua Pila
Estratègia Nivell per nivell Profunditat màxima primer
Ús típic Camins més curts en grafs no ponderats Exploració completa, resolució de puzles
Complexitat Temporal O(V + E) O(V + E)
Complexitat Espacial O(V) O(V)

Exercicis Pràctics

Exercici 1: Implementació de BFS

Implementa l'algorisme BFS per a un graf dirigit i troba el camí més curt des d'un node inicial a tots els altres nodes.

Exercici 2: Implementació de DFS

Implementa l'algorisme DFS per a un graf no dirigit i determina si el graf és connex.

Exercici 3: Aplicació de BFS i DFS

Utilitza BFS i DFS per trobar tots els components connexos en un graf no dirigit.

Solucions

Solució a l'Exercici 1

def bfs_shortest_path(graph, start):
    visited = {start: None}
    queue = deque([start])
    
    while queue:
        vertex = queue.popleft()
        
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited[neighbor] = vertex
                queue.append(neighbor)
    
    return visited

# Exemple de graf dirigit
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

print(bfs_shortest_path(graph, 'A'))

Solució a l'Exercici 2

def dfs_connected(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs_connected(graph, neighbor, visited)
    
    return visited

# Exemple de graf no dirigit
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

print(dfs_connected(graph, 'A'))

Solució a l'Exercici 3

def find_connected_components(graph):
    visited = set()
    components = []
    
    for vertex in graph:
        if vertex not in visited:
            component = dfs_connected(graph, vertex)
            components.append(component)
            visited.update(component)
    
    return components

# Exemple de graf no dirigit amb múltiples components
graph = {
    'A': ['B'],
    'B': ['A'],
    'C': ['D'],
    'D': ['C'],
    'E': []
}

print(find_connected_components(graph))

Resum

En aquesta secció, hem après sobre dos algorismes fonamentals per a la cerca en grafs: BFS i DFS. Hem vist com implementar-los en Python i hem explorat les seves aplicacions i diferències. Aquests algorismes són eines essencials per a molts problemes computacionals i són la base per a tècniques més avançades en el camp dels grafs.

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