[Python] DFS, BFS 구현

DFS (Depth-First Search)

• DFS는 깊이 우선 탐색이라고도 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘입니다.
• DFS는 스택 자료구조(또는 재귀함수)를 이용합니다.
  1. 탐색 시작 노드를 스택에 삽입하고 방문 처리합니다.
  2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고
     방문 처리합니다. 방문하지 않은 인접 노드가 없다면 최상단 노드를 꺼냅니다.
  3. 더이상 2번의 과정을 수행할 수 없을 때까지 반복합니다.

DFS의 과정

그래프

• 그래프가 다음과 같이 주어졌을 때, 방문 기준은 번호가 낮은 인접노드 순으로 가정합니다.
• 깊이 우선 탐색이므로 가장 낮은 노드 1번 부터 시작해서 인접 노드 2,3을 확인합니다.
• 방문 기준에 따라 2번을 골라서 들어가고, 2번은 인접 노드가 7번밖에 없으니 7번으로 들어갑니다.
• 7번의 인접 노드 6번과 8번 중 방문 기준에 맞춰 6번으로 들어갑니다.
• 이런식으로 모든 노드들의 끝을 볼 때까지 깊게 들어가면서 탐색합니다.

방문 순서는 1, 2, 7, 6, 8, 3, 4, 5가 됩니다.

DFS 소스 코드

# 그래프에서 각 노드가 연결된 정보를 표현
graph = [
    [], # 0, 편의상 위 예시처럼 하기 위해 0번은 빈값으로 처리
    [2, 3, 8], # 1과 연결된 노드
    [1, 7],  # 2와 연결된 노드
    [1, 4, 5], # 3과 연결된 노드
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

visited = [False] * len(graph)    # 각 노드들의 방문 여부 리스트

def dfs(graph, v, visited):
    visited[v] = True    # 현재 노드를 방문 처리
    print(v, end = " ")

    # 현재 노드와 연결된 노드 중 방문을 하지 않은 노드인 경우
    for i in graph[v]:    
        if visited[i] is False:
            dfs(graph, i, visited)    # 재귀 호출

BFS (Breadth-First Search)

• BFS는 너비 우선 탐색이라고도 부르며, 그래프에서 가가운 노드부터 우선적으로 탐색하는 알고리즘입니다.
• BFS는 큐 자료구조를 이용합니다.
  1. 탐색 시작 노드를 큐에 삽입하고 방문 처리합니다.
  2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고
     방문 처리합니다.
  3. 더이상 2번의 과정을 수행할 수 없을 때까지 반복합니다.

BFS의 과정

그래프

• 위와 같은 그래프와 같은 방문 기준으로 가정합니다.
• 시작 노드인 1번부터 큐에 삽입하고 방문처리를 합니다.
• 큐에서 1번 노드를 꺼내 방문하지 않은 인접 노드 2, 3, 8번을 차례대로 큐에 삽입하고 방문 처리합니다.
• 큐에서 2번 노드를 꺼내 방문하지 않은 인접 노드 7을 큐에 삽입하고 방문 처리합니다.
• 3번 노드를 큐에서 꺼내 방문하지 않은 인접 노드 4, 5를 큐에 삽입하고 방문 처리합니다.
• 큐에서 노드 8을 꺼내고 방문하지 않은 인접 노드가 없으므로 무시합니다.
• 이런 식으로 전체 노드를 탐색합니다.

BFS의 과정(큐)

이후 방문하지 않은 인접 노드가 없으므로 차례대로 Dequeue가 됩니다.
방문 순서는 1 2 3 8 7 4 5 6이 됩니다.

BFS 소스 코드

from collections import deque

# 그래프에서 각 노드가 연결된 정보를 표현
graph = [
    [], # 0, 편의상 위 예시처럼 하기 위해 0번은 빈값으로 처리
    [2, 3, 8], # 1과 연결된 노드
    [1, 7],  # 2와 연결된 노드
    [1, 4, 5], # 3과 연결된 노드
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

visited = [False] * len(graph)    # 각 노드들의 방문 여부 리스트

def bfs(graph, start, visited):
    # 큐 구현을 위해 deque 라이브러리 사용
    queue = deque([start])

    visited[start] = True  # 현재 노드를 방문 처리

    while queue:  # 큐가 빌 때가지 반복
        v = queue.popleft()
        print(v, end = " ")

        for i in graph[v]:  # 아직 방문하지 않은 인접한 원소들을 큐에 삽입
            if visited[i] is False:
                queue.append(i)
                visited[i] = True

BFS는 최단 경로를 구할 때, 목적지를 찾자마자 최단경로임이 보장되어 탐색을 종료할 수 있어 DFS에 비해 빠릅니다.
보통 재귀를 통해 시스템 스택을 사용하는 DFS에 비해 queue를 사용하므로 비교적 자유롭고 힙 공간을 넓게 쓸 수 있어
좀 더 넓은 범위 탐색에 유리합니다.