탐색은 원하는 데이터를 찾는 과정으로, 대표적인 그래프 탐색 알고리즘에는 DFS와 BFS가 있다.

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

DFS는 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. DFS는 스택 자료구조를 이용하며 동작과정은 다음과 같다.

① 탐색 시작 노드를 스택에 삽입하고 방문 처리 한다.

② 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드중 가장 작은 번호의 노드를 스택에 넣고 방문 처리한다. 방문하지 않은 인접노드가 없으면 스택에서 꺼낸다.

③ 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다.

예시를 통해 살펴보자. 다음과 같은 그래프에서 1번 노드를 시작으로 탐색을 진행해보자.

시작 노드인 1번 노드를 스택에 삽입하고 방문 처리한다.

스택의 최상단 노드인 1번 노드에 방문하지 않은 인접 노드 2,3,8번 노드 중 가장 작은 노드인 2를 스택에 넣고 방문 처리한다.

스택의 최상단 노드인 2번 노드에 방문하지 않은 인접 노드 7번 노드를 스택에 넣고 방문 처리한다.

스택의 최상단 노드인 7번 노드에 방문하지 않은 인접 노드 6,8번 노드 중 가장 작은 노드인 6를 스택에 넣고 방문 처리한다.

스택의 최상단 노드인 6번 노드에 방문하지 않은 인접 노드는 없다. 따라서 스택에서 6번 노드를 꺼낸다.

7번 노드는 다시 스택의 최상단 노드가 되고, 7번 노드에 방문하지 않은 인접 노드 8번 노드를 스택에 넣고 방문 처리한다.

스택의 최상단 노드인 8번 노드에 방문하지 않은 인접 노드는 없다. 따라서 스택에서 8번 노드를 꺼낸다.

7번 노드는 다시 스택의 최상단 노드가 되고, 7번 노드에 방문하지 않은 인접 노드는 없다. 따라서 스택에서 7번 노드를 꺼낸다.

스택의 최상단 노드인 2번 노드에 방문하지 않은 인접 노드는 없다. 따라서 스택에서 2번 노드를 꺼낸다.

스택의 최상단 노드인 1번 노드에 방문하지 않은 인접 노드 3번 노드를 스택에 넣고 방문 처리한다.

스택의 최상단 노드인 3번 노드에 방문하지 않은 인접 노드 4,5번 노드 중 가장 작은 노드인 4를 스택에 넣고 방문 처리한다.

스택의 최상단 노드인 4번 노드에 방문하지 않은 인접 노드 5번 노드를 스택에 넣고 방문 처리한다.

스택에 남아있는 노드중에 방문하지 않은 인접노드가 없다. 따라서 모든 노드를 차례대로 꺼내면 결과는 다음과 같다.

결과적으로 노드의 탐색 순서(스택에 들어간 순서)는 1 ➔ 2 ➔ 7 ➔ 6 ➔ 8 ➔ 3 ➔ 4 ➔ 5 가 된다.

DFS with Python - 재귀함수 사용

DFS는 스택을 이용하는 알고리즘이기 때문에 재귀 함수를 사용하면 매우 간결하게 구현할 수 있다.

def dfs(graph, v, visited):  # v가 시작노드
    visited[v] = True  # 현재 노드 방문처리
    print(v, end=' ')
    for i in graph[v]:  # 현재 노드와 연결된 다른 노드 재귀적 방문
        if not visited[i]:
            dfs(graph, i, visited)
            
# 무방향 그래프 - 번호가 낮은 인접 노드부터 방문한다고 가정
# 각 노드가 연결된 정보를 표현 (2차원 리스트)
graph = [
    [],  # 그래프 문제는 index가 1번 부터 시작하는 경우가 많기 때문에 0번 index는 비워두기
    [2,3,8], # 1번 index의 인접노드
    [1,7],  # 2번 index의 인접노드
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]

# 각 노드가 방문된 정보를 표현 (1차원 리스트)
visited = [False]*9  # 인덱스 0을 사용하지 않는 형태로

# 정의된 DFS함수 호줄
dfs(graph, 1, visited) # 시작노드는 1로 함

# 1 2 7 6 8 3 4 5 

DFS 시간 복잡도: O(N)

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

BFS는 가까운 노드부터 탐색하는 알고리즘이다. BFS는 선입선출방식인 큐 자료구조를 이용하면 된다. 인접한 노드를 반복적으로 큐에 넣으면 먼저 들어온 것이 먼저 나가게 되어 가까운 노드부터 탐색을 진행하게 된다. BFS의 동작 방식은 다음과 같다.

① 탐색 시작 노드를 큐에 삽입하고 방문 처리 한다.

② 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리한다.

③ 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다.

아래와 같은 그래프에서 bfs가 동작하는 과정을 살펴보자.

먼저 시작 노드인 1번 노드를 큐에 삽입하고 방문 처리 한다.

큐에서 1을 꺼내고 방문하지 않은 인접 노드인 2, 3, 8번 노드를 모두 큐에 삽입하고 방문처리한다.

큐에서 2를 꺼내고 방문하지 않은 인접 노드인 7번 노드를 큐에 삽입하고 방문처리한다.

큐에서 3을 꺼내고 방문하지 않은 인접 노드인 4, 5번 노드를 모두 큐에 삽입하고 방문처리한다.

큐에서 8을 꺼내고 방문하지 않은 인접 노드가 없으므로 무시한다.

큐에서 7를 꺼내고 방문하지 않은 인접 노드인 6번 노드를 큐에 삽입하고 방문처리한다.

남아 있는 노드들에 방문하지 않은 인접노드가 없으므로 모든 노드들을 차례대로 꺼내면 다음과 같다.

결과적으로 노드의 탐색 순서(큐에 들어간 순서)는 1 ➔ 2 ➔ 3 ➔ 8 ➔ 7 ➔ 4 ➔ 5 ➔ 6 가 된다.

BFS with Python - 큐 사용

BFS는 큐 자료구조에 기초하며 deque 라이브러리를 사용하면 된다.

from collections import deque

def bsf(graph, start, visited):
    q = deque()  
    q.append(start)  # 시작 노드를 큐에 넣기
    visited[start] = True  # 현재 노드 방문 처리
    while q:
        v = q.popleft()  # 큐에서 첫번째 원소를 추출
        # 아직 방문하지 않은 인접한 노드들 모두 큐에 삽입
        for i in graph[v]:
            if not visited[i]:
                q.append(i)
                visited[i] = True
                
g = [
    [],  # 그래프 문제는 index가 1번 부터 시작하는 경우가 많기 때문에 0번 index는 비워두기
    [2,3,8], # 1번 index의 인접노드
    [1,7],  # 2번 index의 인접노드
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]

visited = [False]*9 

bfs(g, 1, visited)      

# 1 2 3 8 7 4 5 6 

BFS 시간 복잡도: O(N)

일반적인 경우 실제 수행 시간은 DFS보다 좋은 편이다.

BFS는 모든 간선의 길이가 1일 때 특정 노드에서 다른 모든 노드까지의 거리를 찾기 위해 사용된다.