[파이썬(Python) 자료구조] DFS (깊이 우선 탐색) , BFS (너비 우선 탐색)

DFS(Depth-First Search; 깊이우선탐색)와 BFS(Breadth-First Search; 너비우선탐색)는 그래프의 정점을 방문하는 그래프 탐색(Graph Search or Graph traversal; 그래프 운행) 방법의 큰 갈래이다. 코딩 테스트 시에는 DFS를 좀 더 많이 활용하는 듯하다. DFS는 스택이나 재귀로, BFS는 큐로 구현한다.
python에서 그래프는 아래와 같이 보통 딕셔너리를 활용해서 인접 리스트로 구현하는 경우가 많다.

graph = {
1: [2,3,4],
2: [5],
3: [5],
4: [], 
...
}

 

---

DFS (깊이 우선 탐색)

일단 임의의 한쪽 방향으로 갈 수 있을 때까지 가다가 더 이상 갈 수 없게 되면 가장 가까운 갈림길로 돌아와서 그곳으로부터 다른 방향으로 다시 탐색을 진행하는 것을 말함. 이때, 갈림길로 돌아가기 위해서는 스택이 필요하지만 재귀 함수 호출로 묵시적인 스택 또한 이용이 가능하다.

 

DFS의 재귀 구현

DFS를 재귀로 구현하는 경우의 수도 코드는 다음과 같다. 간단하게 말하자면, 정점을 방문하되 방문되었다고 표시하고 해당 정점의 인접 간선을 모두 탐색하는 것이다. 이때, 해당 정점이 방문되지 않았다면 해당 정점에 대해서 다시 DFS를 call하는 형태이다. 즉, 정점의 인접 간선을 하나하나씩 타고 들어간 후 탐색이 불가능하면 빠져나와 다른 인접 간선을 이와 동일한 방식으로 탐색하는 형태이다.

DFS(G, v)
    visit v;
    mark v as visited;
    for all directed edges from v to w that are in G.adjacentEdges(v) do
        if vertex w is not marked as visited then
            recursively call DFS(G, w)

해당 수도코드를 python으로 구현하면 다음과 같다.

def recursive_dfs(v, visited=[]):
    visited.append(v)
    for w in graph[v]:
        if not w in visited:
            visited = recursive_dfs(w, visited)
    return visited

이때, graph는 global 변수로 작용하게 되고, visited는 함수의 인자로 계속 넣어주는 형태이기 때문에 visited를 리턴해서 계속 누적해주는 방식으로 진행을 해줘야함. (얘를 global로 하면 어떻게 될까?)

 

DFS의 스택 구현

스택을 이용하는 경우에는 반복문을 이용해서 구현할 수 있다. 스택을 이용해 모든 인접 간선을 추출하고 다시 도착점인 정점을 스택에 삽입하는 구조로 구현이 가능하다. 수도코드는 아래와 같다.

DFS_iterative(G,v)
    let S be a stack
    S.push(v)
    while S is not empty do
        v = S.pop()
        if v is not marked as visited then
            mark v as visited
            for all edges from v to w in G.adjacentEdges(v) do
                S.push(w)

스택에 한 번에 모든 인접 간선의 정점을 다 push하기 때문에 자칫 BFS로 오해하기 쉬우나, 여기서 염두해야할 점은 stack에 push될 때가 아니라 pop이 되면서 방문을 check하는 구조이기 때문에 정점 방문 순서로 본다면 확실히 depth first search가 맞다는 점이다. 스택의 LIFO 구조를 잘 활용한 것인데 개인적으로는 컨셉 자체를 이해하기엔 재귀가 더 쉬운 거 같다. python으로 구현하는 경우 다음과 같다.

def iterative_dfs(start_v):
    visited = []
    stack = [start_v]
    while stack:
        v = stack.pop()
        if v not in visited:
            visited.append(v)
            for w in graph[v]:
                stack.append(w)

return visited

 

효율성

• 공간 복잡도
  공간 복잡도의 경우, 그래프와 visited, 스택을 모두 고려해주어야 한다. 빅오 표기법으로 표현하는 경우 가장 높은 복잡도만 반영한다는 점을 잊지 말자.그래프의 공간복잡도는 다음과 같다. 인접 행렬로 구현하는 경우에는 하나의 정점과 모든 정점 간의 연결 관계를 다 표현해주어야 하기 때문에 $O(n^2)$ 이다. 반면, 인접 리스트의 경우에는 그래프 내 정점 개수를 n, 간선 개수를 m이라고 할 때 $O(n+m)$의 공간 복잡도를 갖는다.
  
  따라서, 결과적으로 공간복잡도는 그래프의 공간복잡도를 따라 가게 된다. 인접 행렬로 그래프를 구현할 경우 DFS 알고리즘의 공간 복잡도는 $O(n^2)$이며, 인접 리스트의 경우에는 $O(n+m)$이다.
  
  DFS의 효율성에 대해 말할 경우, 스택과 visited는 모두 $O(n)$의 공간복잡도를 가지고 있다 (정점 개수 n). 이는 그래프가 인접 행렬로 구현되어 있든 인접 리스트로 구현되어 있든 두 가지 경우 모두에 해당한다.

• 시간 복잡도
  인접 행렬로 구현되는 경우 하나의 정점 당 n번 check를 해주어야 하기 때문에 $O(n^2)$ 이다. 인접 리스트의 경우에는 정점 방문 & 해당 정점의 인접 정점 방문이므로, $O(n+m)$의 시간 복잡도를 갖는다. 시간 복잡도의 경우에는 결국엔 어떤 정점을 탐색하느냐의 문제이기 때문에 공간 복잡도와 동일하다.

 

---

BFS (너비 우선 탐색)

BFS(너비 우선 탐색)는 시작 정점으로부터 거리가 가까운 정점들을 먼저 차례로 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 운행 방법이다 (점차 영역을 넓혀나간다고 생각하면 쉽다). BFS는 DFS보다 쓰임새는 적지만, 다익스트라 알고리즘과 같이 _최단 경로 탐색 시 많이 활용_된다. BFS는 재귀로 구현되지 않고 오직 큐를 이용한 반복 구조를 통해 구현된다는 점을 명심하자. BFS 구현의 수도코드는 다음과 같다.

BFS(G, start_v)
    let Q be a queue
    mark start_v as visited
    Q.enqueue(start_v)
    while Q is not empty do
        v := Q.dequeue()
        if v is the goal then
            return v
        for all edges from v to w in G.adjacentEdges(v) do
            if w is not marked as visited then
                label w as visited
                w.parent := v
                Q.euqueue(w)

수도코드를 살펴보면 하나의 정점에 대한 인접 간선을 모두 추출하고 도착점인 정점을 큐에 삽입하는 방식으로 동작한다. 코드의 전개는 앞의 DFS 스택 구현과 크게 다르지 않다. 다만, 여기서는 FIFO 구조의 큐를 활용했기 때문에 너비 우선 탐색, 즉 가까운 정점부터 모두 탐색해두고 그 다음 거리의 정점으로 탐색 범위를 넓혀나가는 운행 방식이 가능해지는 것이다.
python으로 구현한 코드는 다음과 같다.

def bfs(start_v):
    visited = [start_v]
    Q = deque([start_v])
    while Q:
        v = Q.popleft()
        for w in graph[v]:
            if w not in visited:
                visited.append(w)
                Q.append(w)

    return visited

효율성

효율성은 앞서 다루었던 DFS와 다르지 않다. 그래프 내 정점 개수를 n, 간선 개수를 m이라고 할 때 인접 행렬로 그래프를 구현할 경우 공간 복잡도와 시간 복잡도 모두 $O(n^2)$이며, 인접 리스트의 경우에는 $O(n+m)$ 이다.

 

---

정리

정리하자면, dfs는 하나 조지고 나머지 조지자! 로 정리할 수 있고 bfs는 일단 가까운 애들 여러 명 불러다가 두루두루 조져보겠다. 이거라고 볼 수 있다. 문제에 따라서 어떤 식으로 dfs, bfs가 쓰이는지는 문제 요구 사항을 잘 파악해야 한다.

 

---

reference

1. 이화여자대학교 이상호 교수님 자료구조 강의자료
2. 파이썬 알고리즘 인터뷰 (박상길 저) Ch.12 그래프