Advanced Algorithm - 너비 우선 탐색(Breadth First Search)

1. 그래프 탐색 알고리즘이란?

- 그래프를 기반으로 특정 노드를 찾아가기 위한 알고리즘

- 이 그래프 알고리즘에는 2가지 대표 알고리즘이 있다.

• 너비 우선 탐색(Breadth First Search) - 정점(노드)과 같은 레벨에 있는 노드(=형제 노드)를 먼저 탐색하는 방식
• 깊이 우선 탐색(Depth First Search) - 정점(노드)의 자식노드를 먼저 탐색하는 방식 

 

 

a) 너비 우선 탐색(BFS)의 예

- 방향과 상관없이 왼쪽 또는 오른쪽 노드를 기준으로, 한 단계씩 내려가면서 해당 노드와 같은 레벨에 있는 노드(형제 노드)를 먼저 순회하는 탐색

• BFS 이동순서: A - B - C - D - G - H - I - E - F - J

 

 

 

 

b) 깊이 우선 탐색(DFS)의 예

- 방향과 상관없이 왼쪽 또는 오른쪽 노드를 기준으로 한 노드의 자식을 타고 끝까지 순회한 후, 다시 돌아와서 다른 형제들의 자식을 타고 내려가며 순회하는 탐색

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

 

---

2. 파이썬으로 그래프를 구현하는 방법 

- 파이썬에서 제공되는 딕셔너리와 리스트 자료구조를 사용하여 그래프를 표현할 수 있다. (아래 사진참고)

- 딕셔너리의 키:값 구조를 이용하고, 값 부분에는 리스트를 이용하여 노드의 인접 정점을 기입한다.

 

 

a) 그래프 구조의 코드구현

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']

 

[테스트] 

---

3. BFS 알고리즘 동작방식의 이해

- 먼저, BFS 알고리즘에서 사용하는 2가지 종류의 Queue가 있다. 이 2가지 큐를 구현해보자. 

• need-visit Queue: 방문이 필요한 노드에 대한 정보를 갖고 있는 큐
• visited Queue: 노드가 방문한 순서에 대한 정보를 갖고 있는 큐

---

4. BFS 알고리즘 코드구현

* BFS의 규칙성

- 반드시 처음 시작점이 될 노드를 알아야 한다.

- 2가지 Queue가 사용된다.(need_visit Queue & visited Queue) 

- 시작점이 되는 첫 노드는 need_visit Queue에 삽입되어 시작한다.

def bfs(graph, start_node):
    visited = list()
    need_visit = list()
    need_visit.append(start_node)
    
    while need_visit: #need_visit 큐에 저장된 데이터가 다 소모될 때까지
        node = need_visit.pop(0) 
        # pop 메소드는 index없이 사용하면 리스트의 마지막 데이터를 뽑아온다. 
        # index가 주어지면 해당 index에 위치한 데이터를 추출한다. 
        # Queue처럼 작동하게 하기위해서 0번 index를 설정한다.
        
        if node not in visited: #visited 큐에 존재하지 않는 데이터라면
            visited.append(node)
            need_visit.extend(graph[node]) #그래프의 키에 해당하는 value를 need_visit 큐에 넣는다
            # extend함수를 사용해야 여러개의 데이터를 큐에 삽입할 수 있다. 
            
    return visited

 

 

[테스트 - 그래프 생성]

 

 

[테스트 결과]

---

5. BFS의 시간복잡도

- 시간 복잡도는 반복문에 의해 결정된다. 그러므로 BFS에서는 while문이 시간복잡도를 결정하는 요인이 된다. 

- 그러므로 방문해야 하는 노드의 수(need_visit 큐의 길이)에 따라 달라지는 것이다. 

- 이를 바탕으로 노드의 수를 V(vertex), 간선의 수를 E(edge)로 표시하여 시간 복잡도를 표현한다. 

 

• BFS의 시간복잡도 = O(V+E)