BFS(幅優先ナビゲーション)

5155 ワード
algorithm テキストリンク

BFSはBreadth-First Searchの略で、幅優先探索のアルゴリズムです.BFSはキューデータ構造を使用する.BFSはまず最初の値に隣接するノードの値をキューに入れて処理し,次に同様に次のノードをブラウズする.
Pythonの例:
from collections import deque

def bfs(graph, start, visited):
    queue = deque([start])
    visited[start] = True

    while queue:
        v = queue.popleft()
        print(v, end=' ')
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

graph = [
	[], 
    	[2, 3, 8], 
    	[1, 7], 
    	[1, 4, 5], 
    	[3, 5], 
    	[3, 4], 
    	[7], 
    	[2, 6, 8], 
    	[1, 7]
]

visited = [False] * 9

bfs(graph, 1, visited)

# ANSWER = 1 2 3 8 7 4 5 6
上記の例に示すように、BFSはCollectionsのdequeを使用する.これは時間の複雑さの効率を高めるためです.
pythonはハフマン符号化を実現
[コードテストC+]最小ヒップ