Rilasciato · in miglioramento
Algorithm
La visita dei grafi raggiunge ogni vertice con BFS o DFS ed è la base di cammini minimi non pesati, componenti, rilevamento di cicli e ordinamento topologico.
La visita di un grafo consiste nel raggiungere, una sola volta ciascuno, tutti i vertici accessibili da un vertice di partenza seguendo gli archi. Le due strategie fondamentali sono la visita in ampiezza (BFS), che usa una coda per espandersi uno strato alla volta, e la visita in profondità (DFS), che usa uno stack o la ricorsione per seguire un ramo fino in fondo prima di tornare indietro. I grafi si memorizzano di solito con liste di adiacenza o matrici di adiacenza, e anche una griglia 2D come un labirinto diventa un grafo se ogni cella è considerata un vertice.
Reti stradali, social network, dipendenze tra attività e link web sono tutti grafi. La BFS trova i cammini minimi quando tutti gli archi hanno lo stesso costo, mentre la DFS è alla base delle componenti connesse, del rilevamento dei cicli e dell'ordinamento topologico. Gli strumenti di build che ordinano le attività, i garbage collector che stabiliscono cosa è ancora raggiungibile e lo strumento secchiello di un editor di immagini si basano sulla visita, ed è uno degli argomenti più frequenti nei colloqui tecnici.
Conviene iniziare disegnando un piccolo grafo e seguendo a mano come cambiano la coda della BFS e lo stack delle chiamate della DFS. Poi si implementano entrambe, facendo attenzione a quando i vertici vengono marcati come visitati e a come si registrano distanze e predecessori. Infine si passa ai cammini minimi su griglia, al conteggio delle componenti connesse e all'ordinamento topologico con l'algoritmo di Kahn.
Le liste di adiacenza usano memoria O(V + E) e si adattano ai grafi sparsi; le matrici verificano un arco in O(1) ma occupano O(V^2).
Una coda visita prima i vertici più vicini, quindi in un grafo non pesato la prima distanza assegnata è quella minima.
Ricorsione o stack scendono in profondità e tornano indietro: è la base di componenti, rilevamento dei cicli e backtracking.
In un grafo orientato aciclico, l'algoritmo di Kahn o l'ordine di fine della DFS invertito danno un ordine che rispetta le dipendenze.
Il programma costruisce un grafo non orientato di sei vertici come lista di adiacenza in un dizionario, poi stampa con una BFS basata su deque il numero minimo di archi da A a ogni vertice e con una DFS ricorsiva l'ordine di visita. Entrambe le funzioni tengono traccia dei vertici visitati per non elaborarne nessuno due volte.
graph_traversal.py
from collections import deque
graph = {
"A": ["B", "C"],
"B": ["A", "D"],
"C": ["A", "D", "E"],
"D": ["B", "C", "F"],
"E": ["C", "F"],
"F": ["D", "E"],
}
def bfs(start):
"""Shortest number of edges from start to every reachable vertex."""
dist = {start: 0}
queue = deque([start])
while queue:
node = queue.popleft()
for nxt in graph[node]:
if nxt not in dist:
dist[nxt] = dist[node] + 1
queue.append(nxt)
return dist
def dfs(start):
"""Vertices in depth-first visiting order."""
order, seen = [], set()
def visit(node):
seen.add(node)
order.append(node)
for nxt in graph[node]:
if nxt not in seen:
visit(nxt)
visit(start)
return order
print(bfs("A")) # {'A': 0, 'B': 1, 'C': 1, 'D': 2, 'E': 2, 'F': 3}
print(dfs("A")) # ['A', 'B', 'D', 'C', 'E', 'F']
python graph_traversal.pySei capitoli che ti accompagnano dall'installazione ai concetti chiave di Visita dei grafi.
Fai domande, condividi la tua esperienza e scambia opinioni su Visita dei grafi.
Ancora nessuna discussione. Avvia la prima.
0 commenti
Accedi · Accedi per lasciare un commento.
Scrivi tu il primo commento.