Python으로 구현한 BFS

BFS 알고리즘은 Queue 자료구조를 사용한다.

그래프 노드를 순회하는데 최초 노드의 모든 자식 노드들을 먼저 탐색한다. 이후 그 자식 노드들의 자식 노드를 모두 탐색하는 과정을 반복한다.

소스코드

#!/bin/python

graph = {'A': ['B', 'C', 'D'],
        'B': ['A', 'E', 'F'],
        'C': ['A', 'G'],
        'D': ['A', 'H', 'I'],
        'E': ['B'],
        'F': ['B', 'J'],
        'G': ['C'],
        'H': ['D'],
        'I': ['D', 'K', 'L'],
        'J': ['F'],
        'K': ['I'],
        'L': ['I']}

def BFS(graph, root):
    visited = []
    queue = [root]

    while(queue):
        outputFromQueue = queue.pop(0)
        if outputFromQueue not in visited:
            visited.append(outputFromQueue)
            inputToQueue = list(set(graph[outputFromQueue]) - set(visited))
            inputToQueue.sort()
            queue.extend(inputToQueue)

    return visited

print(BFS(graph, 'A'))

수행결과

$ ./bfs.py 
['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L']