[알고리즘] 너비 우선 탐색 BFS Breadth First Search

BFS 너비 우선 탐색

• 정점들과 같은 레벨에 있는 노드들을 먼저 탐색하는 방식
• DFS는 깊이 우선 탐색으로 정점의 자식들을 먼저 탐색하는 방식 

---

BFS 방식 : A -> B -> C -> D -> G -> H -> I -> E -> F -> J

• 한 단계식 내려하면서 같은 level의 노드를 순회함

---

구현 코드

graph = dict()

graph['A'] = ["B", "C"]
graph['B'] = ["A", "D"]
graph['C'] = ["A", "G", "H", "I"]
graph['D'] = ["B", "E", "F"]
graph["E"] = ["D"]
graph["F"] = ["D"]
graph["G"] = ["C"]
graph["H"] = ["C"]
graph["I"] = ["C", "J"]
graph["J"] = ["I"]

Need_visit Queue: 노드마다 방문해야하는 노드
Visited Queue: 방문한 노드

 

2개 전부 Queue를 사용함

def bfs(graph, start_node):
    visited = list()
    need_visit = list()
    need_visit.append(start_node)
    
    
    while need_visit:
        node = need_visit.pop(0)
        if node not in visited:
            visited.append(node)
            need_visit.extend(graph[node])

    return visited
bfs(graph, 'A')

['A', 'B', 'C', 'D', 'G', 'H', 'I', 'E', 'F', 'J']

시간복잡도

노드수와 간선의 수로 결정됨

• 노드 수: V
• 간선 수: E
• while에서 V+E 만큼 수행됨
• \( O(V+E) \)