Eninə axtarış (BFS) qrafı dalğa kimi gəzir: əvvəl başlanğıc təpə, sonra onun qonşuları, sonra qonşuların qonşuları. Kəşf olunmuş təpələri növbədə (FIFO) saxlayır: əvvəldəki təpəni götürür və onun görünməmiş qonşularını sona əlavə edir. Ona görə təpələr başlanğıcdan məsafənin artması ilə işlənir və məhz buna görə BFS çəkisiz qrafda ən qısa yolları tapır. Kod DFS-dən yalnız bir yerdə fərqlənir: stekin yerinə növbə.

A-dan BFS: 0, 1, 2 məsafə qatları və növbə
A-dan BFS: 0, 1, 2 məsafə qatları və növbə

BFS: məsafələr və qatlar

dist lüğəti iki rol oynayır: məsafəni saxlayır və hansı təpələrin artıq görüldüyünü göstərir. Təpə növbəyə qoyulan kimi işarələnir. Python-un collections.deque-si hər iki ucda O(1) əməliyyat verir, bax collections modulu.

python
graph = {
    "A": ["B", "C"],
    "B": ["A", "D", "E"],
    "C": ["A", "F"],
    "D": ["B"],
    "E": ["B", "F"],
    "F": ["C", "E"],
}

from collections import deque

def bfs(graph, start):
    dist = {start: 0}                    # also serves as "visited"
    queue = deque([start])
    while queue:
        u = queue.popleft()
        for v in graph[u]:
            if v not in dist:
                dist[v] = dist[u] + 1    # one edge farther than u
                queue.append(v)
    return dist

dist = bfs(graph, "A")
print(dist)

levels = {}
for v, d in dist.items():
    levels.setdefault(d, []).append(v)
print(levels)
text
{'A': 0, 'B': 1, 'C': 1, 'D': 2, 'E': 2, 'F': 2}
{0: ['A'], 1: ['B', 'C'], 2: ['D', 'E', 'F']}