Согласно лемме 22.11 Кормен и др., Введение в алгоритмы (CLRS):
Направленный граф G является ацикличным тогда и только тогда, когда поиск в G по глубине не дает обратных ребер.
Это было упомянуто в нескольких ответах; здесь я также приведу пример кода, основанного на главе 22 CLRS. Пример графика показан ниже.
Псевдокод CLRS для поиска в глубину гласит:
В примере в CLRS на рисунке 22.4 график состоит из двух деревьев DFS: одно состоит из узлов u , v , x и y и другие узлы w и z . Каждое дерево содержит один задний край: один от x до v и другой от z до z (самоконтроль).
Ключевая реализация состоит в том, что задний фронт встречается, когда в функции DFS-VISIT при переборе соседей v из u встречается узел с цветом GRAY.
Следующий код Python является адаптацией псевдокода CLRS с добавленным предложением if, которое обнаруживает циклы:
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 discovered and 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)
Обратите внимание, что в этом примере псевдокод time в CLRS не фиксируется, поскольку мы заинтересованы только в обнаружении циклов. Существует также некоторый шаблонный код для построения представления списка смежности графа из списка ребер.
Когда этот скрипт выполняется, он печатает следующий вывод:
Cycle detected: found a back edge from x to v.
Cycle detected: found a back edge from z to z.
Это именно задние края в примере в CLRS Рисунок 22.4.