[알고리즘] BFS, 너비 우선 탐색

그래프 탐색

하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것

-> 두 점을 연결하는 길이 있는가? 이를 확인하기 위해 하나씩 방문. (특정 도시에서 다른 도시로 갈 수 있는가? 전자 회로에서 특정 단자와 단자가 서로 연결되어 있는가?)

 

너비 우선 탐색(BFS, Breath-First Search)

루트 노드(or 임의의 노드)에서 시작해서 '인접한' 노드를 먼저 탐색하는 방법

1. 의미

• 가까운 것부터.
• 깊게(deep) 탐색하기 전에 넓게(wide) 탐색.
• (가중치가 동일할 때) 두 노드 사이의 최단 경로를 찾거나, 혹은 임의의 경로가 있는지 확인하고 싶을 때
  • 지구상 모든 친구 관계를 '그래프'로 표현한 후 A와 B 사이에 존재하는 경로를 찾는 경우
    • BFS: A와 가장 가까운 관계부터 탐색 <-> DFS: 모든 친구 관계를 다 살펴봐야 할지도...
    • 그러나 BFS가 DFS보다 좀 더 복잡한 경향 O

2. 특징

• 복잡해,, 좀 어렵지?
• 재귀적으로 동작하지 않음
• 어떤 노드를 방문했었는지 여부를 반드시 check해야 함. (그렇지 않으면 무한루프 가능 O)
  • BFS 방문 노드를 큐(Queue)에 차례로 저장, 하나씩 다시 꺼낼 수 있도록.
  • 큐는 선입선출(FIFO): 먼저 들어간 게 먼저 나온다.
• Prim, Dijkstra 알고리즘과 유사.

 

3. 과정

 

 

1) 시작 정점에서 깊이가 1인 모든 노드 방문

• 방문할 때마다 해당 원소가 enqueue
• 시작 정점은 dequeue

2) 깊이가 2인 모든 노드 방문

• 어떻게 보면, 시작 정점이 Queue의 첫번째 원소로 바뀐 셈.
• 이때 Queue에서 해당 원소가 dequeue됨. 
• 바뀐 원소에서 깊이가 1인 걸 탐색하고, 만약 Queue에 이미 저장되어 있는 원소라면 pass.

3) 깊이가 3인....

4) 더 이상 방문할 곳이 없으면(큐가 소진될 때) 탐색 종료

 

4. 구현

• deque 라이브러리를 활용, 큐.
• 시간 복잡도는 O(N) (대체로 DFS보다 BFS가 우수)

1️⃣ 탐색 시작 노드 정보를 큐에 삽입하고 *방문 처리합니다.
2️⃣ 큐에서 노드를 꺼내 방문하지 않은 인접 노드 정보를 모두 큐에 삽입하고 방문 처리합니다.
3️⃣ 2번의 과정을 더 이상 수행할 수 없을 때까지 반복합니다.

 

여기서 *방문 처리란 탐색한 노드를 재방문하지 않도록 구분하는 것입니다. 즉, 큐에 한 번이라도 삽입된 노드를 다시 삽입하지 않도록 체크하는 것이죠.

 

from collections import deque

def bfs(graph, node, visited):
	# 그래프 탐색
    # node는 시작 정점의 default
    # visited는 graph의 node 개수만큼 False로 채워진 리스트
    queue = deque([node])
    visited[node] = True #방문 node에 방문 처리
    
    while queue:
    	# 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],
    [1, 8],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7, 8],
    [6, 8],
    [2, 6, 7]
]

그래프 표현: 노드 간의 연결 정보는 위와 같이 2차원 배열을 통해 표현할 수 있습니다.

즉, 리스트 내 인덱스는 노드 번호를 의미하고 각 인덱스에 해당하는 원소에 해당 노드에 인접한 노드 번호가 담겨 있습니다.

위 graph 배열이 표현하고자 한 그래프(노드 연결)

# 노드별로 방문 정보를 리스트로 표현
visited = [False] * 9

# 정의한 BFS 메서드 호출(노드 1을 탐색 시작 노드로 설정)
bfs(graph, 1, visited)


#>>> 1 2 3 8 4 5 6 7

 

*참고 및 인용

https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html

https://heytech.tistory.com/56