Według Lemma 22.11 z Cormen i wsp., Wstęp do algorytmów (CLRS):
Kierunkowy wykres G jest acykliczny wtedy i tylko wtedy, gdy przeszukiwanie G w pierwszej głębokości nie daje żadnych tylnych krawędzi.
Zostało to wspomniane w kilku odpowiedziach; tutaj podam również przykład kodu oparty na rozdziale 22 CLRS. Przykładowy wykres pokazano poniżej.
Pseudo-kod CLRS dla pierwszego wyszukiwania w głąb brzmi:
W przykładzie na rysunku 22.4 CLRS wykres składa się z dwóch drzew DFS: jednego składającego się z węzłów u , v , x i y , a drugiego z węzłów w i z . Każde drzewo zawiera jedną tylną krawędź: jedną od x do v, a drugą od z do z (pętla własna).
Realizacja kluczem jest to, że krawędź tylna napotkaniu gdy w DFS-VISIT
funkcji podczas iteracji nad sąsiadami v
o u
węzeł spotyka się z GRAY
kolorem.
Poniższy kod Python jest adaptacją pseudokodu CLRS z if
dodaną klauzulą wykrywającą cykle:
import collections
class Graph(object):
def __init__(self, edges):
self.edges = edges
self.adj = Graph._build_adjacency_list(edges)
@staticmethod
def _build_adjacency_list(edges):
adj = collections.defaultdict(list)
for edge in edges:
adj[edge[0]].append(edge[1])
return adj
def dfs(G):
discovered = set()
finished = set()
for u in G.adj:
if u not in discovered and u not in finished:
discovered, finished = dfs_visit(G, u, discovered, finished)
def dfs_visit(G, u, discovered, finished):
discovered.add(u)
for v in G.adj[u]:
# Detect cycles
if v in discovered:
print(f"Cycle detected: found a back edge from {u} to {v}.")
# Recurse into DFS tree
if v not in finished:
dfs_visit(G, v, discovered, finished)
discovered.remove(u)
finished.add(u)
return discovered, finished
if __name__ == "__main__":
G = Graph([
('u', 'v'),
('u', 'x'),
('v', 'y'),
('w', 'y'),
('w', 'z'),
('x', 'v'),
('y', 'x'),
('z', 'z')])
dfs(G)
Zauważ, że w tym przykładzie time
pseudokod CLRS nie jest przechwytywany, ponieważ jesteśmy zainteresowani jedynie wykrywaniem cykli. Istnieje również pewien kod do zbudowania reprezentacji wykresu sąsiedztwa na podstawie listy krawędzi.
Po uruchomieniu tego skryptu drukuje następujące dane wyjściowe:
Cycle detected: found a back edge from x to v.
Cycle detected: found a back edge from z to z.
Są to dokładnie tylne krawędzie w przykładzie na CLRS, rysunek 22.4.