[Algorithm] 너비우선탐색 (BFS)와 깊이우선탐색 (DFS)

그래프에서 모든 정점을 방문해야 할 때가 자주 있다.

모든 정점을 방문하는 방법은 다양하지만 대표적으로 너비우선탐색(BFS)와 깊이우선탐색(DFS)이 있다.

 

BFS와 DFS 모두 일반적인 그래프를 대상으로하는 탐색이지만,

직관적인 이해를 위해 트리구조를 대상으로 루트부터 탐색하는 것으로 진행하겠음.

 

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

루트를 시작으로, 루트의 자식을 차례로 방문한다. 다음으로 루트 자식의 자식, 2개의 간선을 거쳐서 도달할 수 있는 정점을 방문한다. 이처럼 루트에서 거리 순으로 차례로 방문하게 된다.

너비우선탐색을 통한 트리구조 탐색

BFS를 코드로 구현할 때, 자료구조 큐를 사용한다. 먼저 큐에 루트 노드를 삽입하고, 큐가 비어있을 때까지 큐에서 하나를 꺼내 그 노드에 대한 자식 노드를 큐에 삽입한다. 꺼낸 노드는 탐색한 리스트에 추가한다.

from collections import deque

def bfs(graph, start, visited):
	queue = deque([start])
	visited[start] = True
	while queue:
            v = queue.popleft()
            for i in graph[v]:
                if not visited[i]:
                    queue.append(i)
                visited[i] = True

깊이우선탐색 (DFS, Depth-First Search)

루트를 시작으로 하나의 자식노드에 연결된 끝 점까지 탐색하고, 다시 위로 올라오면서 내려갈 수 있는 노드를 찾으면 다시 끝 점까지 내려간다. 

깊이우선탐색을 통한 트리구조 탐색

DFS는 재귀적으로 구현할 수 있다. 연결된 자식노드 중 방문하지 않은 자식노드를 재귀적으로 꺼내면 끝 점까지 꺼내오고 올라오면서 내려가지 않은 노드를 발견하면 다시 내려가게 된다.

def dfs(graph, v, visited):
	visitied[v] = True
	for i in graph[v]:
    	if not visited[i]:
        	dfs(graph, i, visited)