DFS, BFS 개념 정리 및 구현

파이썬 알고리즘 인터뷰의 그래프 장에서의 DFS, BFS의 개념 정리 및 구현을 진행하여 그래프에 대한 전반적인 이해를 할 수 있도록 한다.

그래프 표현 방법

크게 인접 행렬(Adjacency Matrix) 방식과 인접 리스트(Adjacency List) 방식이 있는데 인접 리스트 방식으로 구현을 진행한다.

다음과 같은 graph가 있을 경우 python의 코드상의 구현은 다음과 같다.

GRAPH = {
    1: [2, 3, 4],
    2: [5],
    3: [],
    4: [],
    5: [6, 7],
    6: [],
    7: [3]
}

위와 같이 딕셔너리와 리스트의 조합으로 인접 리스트 방식 그래프를 표현할 수 있다.

DFS(Depth First Search) 

DFS는 깊이 우선 탐색으로 재귀함수 또는 스택을 사용하여 구현한다. 먼저 재귀함수로 구현하는 방법을 알아본다.

재귀함수로 구현

재귀함수를 사용한 구현의 psedo 코드는 다음과 같다.

DFS(G, v)
	label v as discovered
    for all directed edges from v to w that are in G.adjacentEdges(v) do
    	if vertex w is not labeled as discovered then
        	recursively call DFS(G, w)

 

위의 코드를 python으로 구현하면 다음과 같다.

def recursive_dfs(v, graph, discovered=[]):
    discovered.append(v)
    for w in graph[v]:
        if w not in discovered:
            recursive_dfs(w, graph, discovered)

    return discovered

 

해당 함수를 호출하면 다음과 같이 출력된다.

>>> print(recursive_dfs(1, GRAPH))

[1, 2, 5, 6, 7, 3, 4]

 

해당 로직을 그림을 통해 살펴보면 다음과 같다.

먼저 처음 시작 위치 '1' vertex를 discovered에 추가한 후 '1' vertex와 연결된 '2' vertex 리스트를 재귀함수로 호출한다.

'2' vertex도 discovered에 추가 후 동일하게 연결된 '5' vertex로 재귀함수를 호출한다. '5' vertex 역시 동일하게 discovered에 추가한 후 '6' vertex를 호출하게 된다.

'6' vertex는 연결된 vertex가 없다. discovered에 추가한 후 함수를 리턴한다. 이후 '5' vertex와 연결된 '7' vertex로 호출을 진행한다. '7' vertex와 연결된 '3' vertex도 동일하게 처리한다.

'3'->'7'->'5'->'2' vertex모두 더 이상 연결되어 있는 vertex가 없으므로 차례로 함수를 리턴을 하여 다시 '1' vertex와 연결되어 있는 '3' vertex를 처리한다. 여기서 '3' vertex는 이미 discovered에 존재하므로 추가하지 않는다.

마지막으로 '4' vertex를 재귀함수로 호출하면 모든 그래프를 순회하게 된다.

해당 그래프에서 빨간 실선과 회색 점선을 순서대로 따라가보면 다음과 같이 vertex를 1->2->5->6으로 탐색한 후 되돌아간 후 7->3까지 진행한다. 이후 다시 되돌아간 후 4를 탐색하고 종료하는데, 이는 [1, 2, 5, 6, 7, 3, 4] 결과와 동일하다.

재귀함수 DFS 진행 순서

스택을 통한 반복 구조로 구현

스택을 사용한 구현의 psedo 코드는 다음과 같다.

DFS-iterative(G, v)
	let S be a stack
    S.push(v)
    while S is not empty do
    	v = S.pop()
        if v is not labeled as discovered then
        	label v as discovered
            for all edges from v to w in G.adjacentEdges(v) do
            	S.push(w)

 

이를 python으로 구현하면 다음과 같다.

def stack_dfs(start_v, graph):
    stack = [start_v]
    discovered = []
    while stack:
        v = stack.pop()
        if v not in discovered:
            discovered.append(v)
            for w in graph[v]:
                stack.append(w)

    return discovered

 

해당 함수를 호출 시 다음과 같이 출력된다.

>>> print(stack_dfs(1, GRAPH))

[1, 4, 3, 2, 5, 7, 6]

 

재귀 구조와는 다른 순서로 값을 출력한다. 이를 확인하기 위해 코드의 분석을 진행한다.

먼저 stack에 시작 vertex '1'값을 push한 후 loop를 진행한다. loop에서는 stack을 pop한 후 '1' vertex를 discovered에 추가한 후 '1' vertex와 연결되어 있는 '2', '3', '4' vertex를 stack에 push 한다.

 

위와 동일하게 stack을 pop한 후 discovered에 추가한 후 연결된 vertex를 stack에 추가한다. 여기서 '4'는 더이상 연결된 vertex가 없기에 다음 '3' vertex로 넘어간다. '3' vertex 역시 연결된 노드가 없기에 '2' vertex로 이동한다.

'2' vertex는 연결된 '5' vertex가 존재 하므로 discovered에 추가 후 '5'를 stack에 push한다. '5' vertex는 '6', '7' vertex와 연결되어 있으므로 해당 vertex를 stack에 push 한다.

 

이어서 '7' vertex는 '3'과 연결되어 있지만 '3'은 이미 discovered되어 있기에 pass 한다.

 

마지막으로 '6' 을 discovered에 추가하면 그래프 순회가 끝난다

이처럼 stack을 사용한 구현은 연결된 vertex를 stack에 push한 후 pop하여 순회하기 때문에 재귀 구조와는 반대 순서로 순회하는 특성이 있다. 

 

두가지 구현 모두 진행 순서가 연결되어 있는 아래쪽 방향으로, 즉 깊이 방향을 우선으로 진행됨을 알 수가 있다.

구현별 DFS 진행 방향

 

BFS(Breadth First Search) 

DFS가 아래쪽 방향을 우선으로 진행된다면 BFS는 가로로 방향을 우선으로 진행된다. psedo 코드는 다음과 같다.

큐를 이용한 반복구조로 구현

BFS(G, start_v)
	let Q be a queue
    label start_v as discovered
    Q.enqueue(start_v)
    while Q is not empty do
    	v := Q.dequeue()
        for all edges from v to w in G.adjacentEdges(v) do
        	if w is not labeled as discovered then
            	label w as discovered
                Q.enqueue(w)

 

python으로는 다음과 같이 구현한다.

def queue_bfs(start_v, graph):
    q = collections.deque()
    discovered = [start_v]
    q.append(start_v)

    while q:
        v = q.popleft()
        for w in graph[v]:
            if w not in discovered:
                discovered.append(w)
                q.append(w)

    return discovered

해당 코드의 진행 순서를 보면 다음과 같다.

먼저 discovered와 queue에 시작 vertex로 초기화한 후 loop를 진행한다. queue에서 '1' vertex를 deque한 후 연결된 vertex를 queue에 enque한다.

이후 queue에서 vertex를 뺀 후 discovered에 추가한 후 해당 vertex가 연결된 vertex가 있으면 queue에 추가하고 없으면 pass한다. '2'의 경우에는 '5'와 연결되어 있어 '5'를 enque했고, '3', '4'는 pass하였다.

'5'역시 동일한 방식으로 연결된 '6', '7'을 추가한다. '7'의 경우엔 연결된 '3'이 discovered에 존재하기 때문에 pass한다.

이 처럼 연결된 노드가 왼쪽에서 오른쪽 방향으로 순회하는 것을 확인할 수 있다.