[ 알고리즘 개념 ] 그래프 탐색 DFS/BFS 구현 - 파이썬(Python)

DFS / BFS

1. DFS (Depth-First Search) : 깊이 우선 탐색

 

DFS 는 그래프의 깊은 부분을 우선적으로 탐색하는 알고리즘이다.

DFS 예

위 그림을 보면 쉽게 이해할 수 있다.

(1) 탐색할 수 있는 만큼 깊이 방문

(2) 더이상 깊이 탐색할 수 없는 경우 부모노드를 방문한 후 다른 형제 노드 방문

이 두가지가 깊이 우선 탐색의 기본 과정이다.

 

보통 그래프를 구현할 때에는 보통 인접 리스트를 사용한다.

Python에서는 list 자료형이 append 메소드를 제공하므로 다른 언어 (C++, Java) 와 같이 별도의 연결 리스트 라이브러리를 사용할 필요가 없다.

따라서 다음과 같이 기본 list형의 graph를 생성한 후에 append를 활용하여 연결정보를 입력하면 된다.

# 행이 3개인 2차원 리스트
graph = [[] for _ in range(3)]

# node 0 의 연결정보 (노드, 거리)
graph[0].append((1, 7))
graph[0].append((2, 5))

# node 1 의 연결정보 (노드, 거리)
graph[1].append((0, 7))

# node 2 의 연결정보 (노드, 거리)
graph[2].append((0, 5))

 

DFS 동작 과정을 구현하기 위해서는 스택 Stack 를 활용한다.

 

(1) 탐색 시작 노드를 스택에 삽입하고 방문체크

(2) 스택의 최상단 노드에 방문하지 않은 노드가 있으면 그 인접 노드를 스택에 넣고 방문 체크. 만약 방문하지 않은 인접 노드가 없을 경우 스택에서 최상단 노드를 꺼냄

(3) 위 과정을 더 이상 수행할 수 없을 때까지 반복

 

def dfs(graph, v, visited):

    visited[v] = True # 방문 처리
    print(v, end='')
    
    # 현재 node의 인접노드를 재귀적으로 방문
    for i in graph[v]:
    	if not visited[i]: # 방문하지 않은 node일 경우
        	dfs(graph, i, visited) # 재귀 호출

graph = [...] # 2차원 list 그래프 정의
visited = [False] * 9 # node 의 수만큼 방문 정보 list 정의

dfs(graph, 1, visited) # dfs 수행

 

2. BFS (Breadth-First Search) : 너비 우선 탐색

BFS는 가까운 노드부터 우선적으로 탐색하는 알고리즘이다.

BFS 예

 

BFS 동작과정을 구현하기 위해서는 큐 Queue 를 사용한다.

Python에서는 Queue 자료구조를 표현할 때, Deque 라이브러리를 사용하는 것이 좋다.

O(N) 의 시간복잡도를 가지지만 일반적으로 DFS 보다 BFS 의 수행시간이 조금 더 좋은 편이다.

 

from collections import deque

def bfs(graph, start, visited):

# deque 라이브러리를 사용하여 queue 생성
    queue = deque([start]) # 첫 방문 노드 추가하여 초기화
    visited[start] = True
    
    # queue가 빌 때까지 반복수행
    while queue:
    	
        # 큐에서 하나의 node를 pop - popleft는 첫번째 원소를 반환하고 제거함
        v = queue.popleft()
        print(v, end='')
        
        # 해당 node의 방문하지 않은 인접 node 를 queue에 삽입
        for i in graph[v]:
        	if not visited[i]:
            	queue.append(i)
                visited[i] = True
 
 # 그래프와 visited는 dfs와 동일