Laiuti otsing

Laiuti otsing (ka laiutiotsing) on graafi läbimise algoritm. Algoritm alustab etteantud tipust, läbib kõik selle tipu naabrid, siis naabrite naabrid jne. Algoritm lõpetab töö, kui kõik võimalikud teed on läbitud või kui otsitav tipp on leitud.

Laiuti otsing Pythonis

Järgnevas Pythoni koodis läbib meetod bfs graafi G alustades tipust s.

def bfs(G, s):
    queue = [s]             # tippude järjekord
    visited = set(s)        # juba külastatud tipud
    while queue:            # kuni järjekorras on tippe
        v = queue.pop(0)        # võta esimene tipp järjekorrast
        yield v                 # tagasta see
        for u in G[v]:          # iga naabertipu kohta
            if u not in visited:    # kui tippu pole külastatud
                queue.append(u)     # lisa see järjekorda
                visited.add(u)      # ja märgi külastatuks

T = {'1': ['2', '3', '4'],
     '2': ['5'],
     '3': ['6', '7'],
     '4': ['8'],
     '5': ['9'],
     '6': ['10'],
     '7': [], '8': [], '9': [], '10': []}
G = {'A': ['B', 'C','E'],
    'B': ['A','C', 'D'],
    'C': ['D'],
    'D': ['C'],
    'E': ['F','D'],
    'F': ['C']}

>>> list(bfs(T, '1'))
['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']
>>> list(bfs(G, 'A'))
['A', 'B', 'C', 'E', 'D', 'F']

Vaata ka

• Sügavuti otsing