DFS/BFS 탐색 이론

• DFS 탐색
  DFS는 Depth-First-Search, 즉 깊이 우선 탐색으로 그래프의 깊은 부분부터 우선적으로 탐색하는 알고리즘이다. 특정한 경로로 탐색할 때 그 경로에서 최대한 깊숙이 들어가서 노드를 방문한 후, 더 이상 들어갈 곳이 없다면 위의 노드로 돌아가 다른 경로로 탐색한다.
  
  

위와 같은 그래프에서 깊은 부분부터 탐색한다고 하면 1 -> 2 -> 4 -> 5 -> 3 -> 6 -> 7 순으로 탐색하게 된다. 그래프의 구현은 다음과 같이 리스트에 인접한 노드들을 저장하는 방식으로 할 수 있다.

graph = [
	[], 	# 0번 노드는 존재하지 않으므로 0번째 인덱스는 비워두기
    [2, 3], 	# 1번 노드는 2, 3번 노드와 연결되어 있으므로 1번째 인덱스에 2, 3 저장
    [1, 4, 5],	# 2번 노드는 1, 4, 5번 노드와 연결되어 있으므로 2번째 인덱스에 1, 4, 5 저장
    [1, 6, 7],  # 3번 노드는 1, 6, 7번 노드와 연결되어 있으므로 3번째 인덱스에 1, 6, 7 저장
    [2], 	# 4번 노드는 2번 노드와 연결되어 있으므로 4번째 인덱스에 2 저장
    [2], 	# 5번 노드는 2번 노드와 연결되어 있으므로 5번째 인덱스에 2 저장
    [3], 	# 6번 노드는 3번 노드와 연결되어 있으므로 6번째 인덱스에 3 저장
    [3] 	# 7번 노드는 3번 노드와 연결되어 있으므로 7번째 인덱스에 3 저장
    ]
    # 방문 유무를 표시하기 위한 방문 리스트
    visited = [False]*8

DFS는 재귀 함수를 이용하여 구현할 수 있다. 
1. 현재 노드를 방문 처리

2. 현재 노드와 연결된 노드들 중 방문 처리가 되지 않은 노드들을 재귀적으로 호출하여 방문

def dfs(graph, v, visited):
	# 현재 노드를 방문 처리
    visited[v] = True 
    print(v, end=' ')
    # 현재 노드와 연결된 노드들 중 방문하지 않은 노드들을 재귀적으로 방문
    for i in graph[v]:
    	if not visited[i]:
        	dfs(graph, i, visited)
# dfs함수 호출
dfs(graph, 1, visited)

실행 결과

 

• BFS
  BFS는 Breadth-First-Search, 즉 너비 우선 탐색으로 가까운 노드부터 탐색하는 알고리즘이다. BFS는 큐 자료구조를 이용하며 다음과 같이 구현할 수 있다.
  1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
  2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.
  3. 큐에 더 이상 원소가 남지 않게 될 때까지 위의 과정을 반복한다.
  위의 그래프에서 BFS 탐색을 한다면 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 순으로 탐색할 것이다.

# 큐를 이용하기 위해 deque 임포트하기
from collections import deque
# dfs 함수를 호출함으로써 방문처리가 된 방문 리스트를 초기화
visited = [False]*8
def bfs(graph, start, visited):
    queue = deque([start])
    # 현재 노드 방문 처리
    visited[start] = True
    # 큐에 원소가 남지 않을 때까지 반복
    while queue:
    	v = queue.popleft()
        print(v, end=' ')
        # v와 연결되고 방문하지 않은 원소들을 큐에 삽입
        for i in graph[v]:
        	if not visited[i]:
            	queue.append(i)
                visited[i] = True
bfs(graph, 1, visited)

실행 결과

1 2 3 4 5 6 7