BFS, DFS ve traversal invariant’ları

BFS queue ile katman katman ilerler. Ağırlıksız graf veya tüm kenarlar eşit maliyetliyse ilk keşif minimum edge sayısını verir. Visited işaretini dequeue'da değil enqueue'da koymak aynı düğümün tekrar tekrar kuyruğa girmesini önler. Parent map en kısa yolun kendisini geri kurar.

DFS stack/recursion ile bir dalı takip eder. Discovery/finish zamanları, recursion stack rengi, back edge ve topological order gibi yapıları ortaya çıkarır. Yönsüz graf cycle testinde parent edge'i geri kenar sanma; parallel edges için edge ID gerekebilir. Recursive DFS'nin derinliği V'ye ulaşabilir.

BFS ve DFS bütün grafı işlemek için her unvisited düğümden tekrar başlatılmalıdır. Komşu sırası traversal çıktısını değiştirir ama doğru BFS distance'ını değiştirmez. BFS minimum maliyet yolu ağırlıklı graf için genel olarak bulmaz; path length ile cost'u ayır.

from collections import deque

def bfs(g, start):
    distance, parent = {start: 0}, {start: None}
    q = deque([start])
    while q:
        u = q.popleft()
        for v in g[u]:
            if v not in distance:
                distance[v], parent[v] = distance[u]+1, u
                q.append(v)
    return distance, parent
assert bfs({"A":["B","C"],"B":["D"],"C":["D"],"D":[]},"A")[0]["D"] == 2