[Algorithm] BFS & DFS

그래프 탐색 알고리즘

그래프 탐색 문제는 시작 정점이 주어졌을 때, 시작 정점에서 간선을 타고 이동할 수 있는 모든 정점을 구하는 문제이다. 

 

그래프 탐색 알고리즘에는 대표적으로 너비 우선 탐색(breadth-first-search;BFS)과 깊이 우선 탐색(depth-first-search;DFS) 방식이 있다.

 

 

깊이 우선 탐색(DFS)

DFS의 경우 이름부터가 깊이 우선 탐색이기 때문에 노드의 깊이가 직접적으로 나타나지 않는 그래프보다는 트리에서 이해하기가 좋다. 

만약 다음과 같은 트리의 1번 정점에서 DFS를 진행한다고 하자. 진행 과정은 아래의 그림과 같다. 

 

먼저 현재 노드인 1번 노드를 방문 처리 한다. 이후 1번과 연결되어 있는 간선을 하나씩 조사하는데, 먼저 4번 노드와 연결된 간선을 조사한다. 

다음으로 4번 노드를 방문 처리 하고, 4번 노드와 연결되어있는 3번 노드로 이동한다. 

3번 노드에서는 더이상 이동할 곳이 없으므로 다시 4번 노드로 올라오고, 4번 노드와 연결된 또 다른 노드인 5번 노드로 이동한다. 

5번 노드에서도 더이상 이동할 곳이 없으므로 다시 4번으로 올라오고, 4번도 마찬가지로 이동할 곳이 없으므로 다시 1번 노드로 돌아간다. 1번 노드에서는 다음으로 연결된 노드인 2번 노드로 이동하고, 위와 같은 과정이 반복된다. 

 

과정을 살펴보면 트리의 순회법 중 중위 순회와 유사한 것을 볼 수 있다. DFS는 스택이나 재귀 함수를 통해 구현할 수 있으며, 인접 리스트로 구현하는 경우 시간복잡도가 O(V+E)로 계산된다. 여기서 V는 정점의 개수, E는 간선의 개수를 의미한다. 

 

DFS를 간단하게 코드로 구현하면 다음과 같이 구현할 수 있다. 

def dfs(node, graph, visited):
    for next_node in graph[node]:
        if not visited[next_node]:
            visited[next_node] = 1
            dfs(next_node, graph, visited)

트리의 경우 특정 노드로 가는 경로가 단 하나밖에 존재하지 않기 때문에 방문 처리를 했던 점을 다시 방문할 일이 없지만, 그래프의 경우 경로가 여러 개가 있을 수 있기 때문에 연결된 정점의 방문 여부를 따져봐야 한다. 따라서 코드로 구현할 때에는 위와 같이 visited라는 배열로 정점의 방문 여부를 표시해 준다.

 

 

너비 우선 탐색(BFS)

BFS는 DFS와는 달리 인접한 노드를 먼저 검사한 뒤 다음 깊이로 넘어가는 방식이다. DFS가 주로 재귀 함수를 활용하여 구현한 반면, BFS는 Queue 자료구조를 활용하여 구현한다.

 

아래의 그림과 함께 이해해 보자! 

먼저 시작 노드를 방문 처리 해주고 Queue에 시작 노드를 넣어준다. 이후에 Queue에서 원소를 하나씩 꺼내가며 검사를 진행한다. 그림에서는 방금 Queue에서 꺼낸 노드의 번호를 now로 표현하였다. 

 

이후 1번과 인접한 노드인 4번 노드와 2번 노드를 방문 처리 해준 뒤 Queue에 노드를 삽입한다. 이제 1번과 인접한 노드 중 아직 방문하지 않은 노드가 없으므로 1번 노드에 대한 검사는 종료된다. 

 

Queue에서 맨 앞에 있는 원소인 4를 꺼낸 뒤, 검사를 진행한다. 위에서 했던 방식과 같이 4와 인접한 노드인 3번과 5번을 방문 처리하고, Queue에 삽입해 준다. 이후 과정은 앞의 과정의 반복이며 Queue에 있는 원소가 빌 때까지 반복한다. 

 

이를 코드로 구현하면 다음과 같다.

from collections import deque

def bfs(start, graph, visited):
    deq = deque()
    deq.append(start)
    
    while deq:
    	now = deq.popleft()
        for next_node in graph[now]:
        	if not visited[next_node]:
            	visited[next_node] = 1
                deq.append(next_node)