[python] Graph Traversals(Search) 그래프 순회(탐색) 정리

보통 그래프 문제에는 DFS(Depth-First Search)와 BFS(Breadth-First Search)가 있다.

 

DFS는 깊이 우선 탐색이라 부르고 BFS는 너비 우선 탐색이라 부른다.

    - 컴공이라면 전공 시간에 배운다. 수리 논리, 이산수학, 계산이론 등 이러한 시간에 DFS, BFS에 대해서 배웠다.

 

 

나무 위키에 있는 것이다.. 이거를 보면 이해하기가 쉬울 것이다. 번호 순서대로 탐색을 진행한다.

 

DFS는 위 그림에서 보이듯 마지막 노드까지 깊게 탐색을 한다.

    * 1, 2, 3 ... 등 숫자가 써져있는 동그라미를 노드라고 부른다.

 

BFS는 위 그림에서 보이듯 넓게 탐색을 한다.

    - BFS는 최단경로를 알아내는데 쓰인다.

 

일반적으로 알고리즘 문제에서는 BFS 보다는 DFS를 많이 쓰이게 된다.

 

DFS는 주로 스택이나 재귀로 구현하며,  BFS는 큐로 구현을 한다.

    - DFS는 백트레킹에 뛰어난 효용을 보인다.

 

그리고 파이썬에서는 그래프를 딕셔너리 자료형으로 표현을 할 수 있다.

 

 

위의 그래프를 파이썬으로 표현을 해보자.

graph = {
    1: [5, 6], #1에는 5와 6이 연결되어 있다.
    2: [3, 4, 6], #2에는 3과 4와 6이 연결되어 있다.
    3: [2, 4, 5], #3에는 2와 4와 5가 연결되어 있다.
    4: [2, 3], #4에는 2와 3이 연결되어 있다.
    5: [1, 3, 6], #5에는 1과 3과 6이 연결되어 있다.
    6: [1, 2, 5] #6에는 1과 2와 5가 연결되어 있다.
}

 

이런 식으로 표현이 가능하다. 인접 노드들을 리스트 형태로 넣어주면 된다.

 

재귀를 이용한 Python DFS 코드는 다음과 같다.

print(recursive_dfs(1))

def recursive_dfs(v, discovered=[]):
    graph = {
        1: [5, 6], #1에는 5와 6이 연결되어 있다.
        2: [3, 4, 6], #2에는 3과 4와 6이 연결되어 있다.
        3: [2, 4, 5], #3에는 2와 4와 5가 연결되어 있다.
        4: [2, 3], #4에는 2와 3이 연결되어 있다.
        5: [1, 3, 6], #5에는 1과 3과 6이 연결되어 있다.
        6: [1, 2, 5] #6에는 1과 2와 5가 연결되어 있다.
    }
    discovered.append(v) # discovered는 탐색한 노드들을 저장한다.
    for w in graph[v]:
        if not w in discovered: # w가 탐색한 노드가 아니라면 탐색한다.
            discovered=recursive_dfs(w,discovered) 
    return discovered

 

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

 

위 코드의 결괏값은 다음과 같이 나온다.

 

스택을 이용한 Python DFS 코드는 다음과 같다.

print(iterative_dfs(1))

def iterative_dfs(start_v):
    graph = {
        1: [5, 6], #1에는 5와 6이 연결되어 있다.
        2: [3, 4, 6], #2에는 3과 4와 6이 연결되어 있다.
        3: [2, 4, 5], #3에는 2와 4와 5가 연결되어 있다.
        4: [2, 3], #4에는 2와 3이 연결되어 있다.
        5: [1, 3, 6], #5에는 1과 3과 6이 연결되어 있다.
        6: [1, 2, 5] #6에는 1과 2와 5가 연결되어 있다.
    }
    discovered = []
    stack = [start_v]
    while stack :
        v = stack.pop()
        if v not in discovered : # 노드를 탐색하지 않았다면 discovered에 추가하고 탐색한다.
            discovered.append(v) 
            for w in graph[v] :
                stack.append(w) # stack에는 탐색해야할 노드들을 추가한다.
    return discovered

 

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

 

흠.. 재귀를 이용한 DFS와 반대로 나왔다.. ㅎ

 

이유는 재귀는 사전식 순서로 방문했지만, 스택은 마지막에 삽입된 노드부터 꺼내기 때문이다.

 

 큐를 이용한 Python BFS 코드는 다음과 같다.

print(iterative_bfs(1))

def iterative_bfs(start_v):
    graph = {
        1: [5, 6], #1에는 5와 6이 연결되어 있다.
        2: [3, 4, 6], #2에는 3과 4와 6이 연결되어 있다.
        3: [2, 4, 5], #3에는 2와 4와 5가 연결되어 있다.
        4: [2, 3], #4에는 2와 3이 연결되어 있다.
        5: [1, 3, 6], #5에는 1과 3과 6이 연결되어 있다.
        6: [1, 2, 5] #6에는 1과 2와 5가 연결되어 있다.
    }
    discovered = [start_v]
    queue = [start_v]
    while queue :
        v = queue.pop(0)
        for w in graph[v] :
            if w not in discovered :
                discovered.append(w)
                queue.append(w)
    return discovered

 

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

 

DFS와는 다르게 5다음 6이 오는 것을 확인할 수 있다.

 

일반적인 그래프 문제는 DFS로 풀고 최단거리를 계산하는 문제는 BFS로 풀면 될 거 같다..

 

from collections import deque

print(iterative_bfs(1))

def iterative_bfs(start_v):
    graph = {
        1: [5, 6], #1에는 5와 6이 연결되어 있다.
        2: [3, 4, 6], #2에는 3과 4와 6이 연결되어 있다.
        3: [2, 4, 5], #3에는 2와 4와 5가 연결되어 있다.
        4: [2, 3], #4에는 2와 3이 연결되어 있다.
        5: [1, 3, 6], #5에는 1과 3과 6이 연결되어 있다.
        6: [1, 2, 5] #6에는 1과 2와 5가 연결되어 있다.
    }
    discovered = [start_v]
    queue = deque([start_v])
    while queue :
        v = queue.popleft()
        for w in graph[v] :
            if w not in discovered :
                discovered.append(w)
                queue.append(w)
    return discovered

 

시간 복잡도를 생각한다면 deque를 사용하면 된다.