BFS (Breadth First Search)

루트 노드의 자식 노드들을 먼저 모두 차례로 방문한 후, 방문했던 자식 노드들을 기준으로 하여 다시 해당 노드의 자식 노드들을 차례로 방문하는 방식

인접한 노드들에 대해 탐색을 한 후, 차례로 다시 너비우선탐색을 진행해야 하므로, 큐가 적합함

간단한 트리에서의 BFS

from collections import deque

def bfs_tree(tree, root_node):
	queue = deque([root_node])
    result = []
    
    while queue:
    	node = queue.popleft()
        result.append(node)
        
        if node not in tree: continue
        
        for child in tree[node]:
        	queue.append(child)
    
    return result
    
tree = {
	'A': ['B', 'C', 'D'],
    'B': ['E', 'F'],
    'D': ['G', 'H', 'I']
}

root_node = 'A'

result = bfs_tree(tree, root_node)

print(' '.join(result))

BFS - 그래프

Tree BFS와 전체적으로 동일하나 방문 여부를 확인해야 한다.

그래프 BFS 코드

from collections import deque

def bfs(start):
	nodes = list(graph.keys())
    visited = [False] * len(nodes)
    queue = deque([start])
    result = []
    
    start_index = nodes.index(start)
    visited[start_index] = True
    
    while queue:
    	vertex = queue.popleft()
        result.append(vertex)
        
        for neighbor in graph[vertex]:
        	neighbor_index = nodes.index(neighbor)
            if not visited[neighbor_index]:
            	queue.append(neighbor)
                visited[neighbor_index] = True
                
	return result
    
graph = {
	'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A'],
    'D': ['B', 'F'],
    'E': ['B', 'F'],
    'F': ['D', 'E', 'G'],
    'G': ['F'],
}
nodes = list(graph.keys())
visited = [False] * len(nodes)
result = []
for node in nodes:
	if not visited[nodes.index(node)]:
    	result.extend(bfs(node))
print("그래프 탐색 경로:", result)