[자료구조&알고리즘 | WEEK03] DFS/BFS (그래프 순회)

그래프 순회(Graph Traversal)

그래프 순회란 그래프 탐색(Search)이라고도 불리우며, 그래프의 각 정점을 방문하는 과정을 말한다.

---

그래프의 각 정점을 방문하는 그래프 순회(Graph Traversls)에는 크게 깊이 우선 탐색 DFS(Depth-First Search, DFS)과 너비 우선 탐색 BFS(Breadth-First Search, BFS) 2가지 알고리즘이 있다. 두 가지 모두 탐색 알고리즘에 해당한다.

• DFS는 주로 스택 또는 재귀로 구현한다.
• BFS는 주로 큐로 구현하며, 그래프의 최단 경로를 구하는 문제 등에 사용된다.

 

깊이 우선 탐색 - DFS(Depth-First Search, DFS)

---

깊이 우선 탐색은 탐색을 함에 있어서 보다 깊은 것을 우선적으로 하여 탐색하는 알고리즘이다. 맹목적 탐색(blind search) 방법의 하나로 탐색트리의 최근에 방문한 노드를 선택하고, 그 노드의 인접 노드들을 방문하되, 깊게 탐색하는 것이다.(트리라고 한다면 레벨을 높여가면서 내려가게 된다.) 

 

 

💡

맹목적 탐색(blind search)이란

이미 정해진 순서에 따라 상태 공간 그래프를 점차 형성해 가면서 해를 탐색하는 방법을 말한다.

 

장점과 단점

• 장점
  • 특정 원소를 찾는다고 했을 때, 목표 노드(원소)가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.
• 단점
  • 해가 없는 경로에 깊이 빠질 가능성이 있다. 따라서 실제의 경우 미리 지정한 임의의 깊이까지만 탐색하고(해가 어디있는지 가늠할 수 없을 경우), 목표노드를 발견하지 못하면 다음의 경로를 따라 탐색하는 방법이 유용할 수 있다.
  • 얻어진 해가 최단 경로가 된다는 보장이 없다. 목표에 이르는 경로가 다수인 문제에 대해 DFS는 해에 다다르면 탐색을 끝내버리므로, 이때 얻어진 해는 최적이 아닐 수도 있다. 즉, 다른 경로가 최단 경로가 될 수도 있는 것이다.
    • 대부분 최단 경로는 BFS로 구현한다고 한다.

 

DFS의 동작 방식

역시 글로만 이해하는 것 보다 시각적으로 보는게 이해하기가 더 수월한 것 같다.
아래 이미지는 깊이 우선 탐색인 DFS의 동작 방식이다.

물론 아래 이미지와 같이 무조건 일자로 내려가는건 아니고, 그래프로 주어진 데이터나, 코딩을 어떻게 하느냐에 따라 다르다.

 

DFS의 동작 방식

 

인접 리스트로 그래프를 표현한 DFS 탐색 방식(재귀적)

우선 정확한 이해를 위해 코드를 치기 전에 직접 그림을 그리면서 먼저 이해했다.

 

아래와 같은 그래프가 있다고 했을 때, 인접리스트인 graph 변수는 딕셔너리 자료형이며, 각 key/value는 특정 노드(key)에서 다른 노드(value)로 갈 수 있는 원소들을 나타낸다. 즉, key는(특정 노드는) 다른 노드로 갈 수 있는(value) 정보를 담고 있다.

 

아래 오른쪽 그래프에서 초록색으로 표시된 부분이 DFS가 재귀적으로 어떻게 탐색하는지, 어떤 순서로 진행되는지를 나타낸다. 전체 탐색 순서는 밑의 파란색으로 표시된 배열과 같다.

 

인접 리스트로 표현한 DFS 수행 과정

 

위에서 재귀적으로 표현한 DFS를 코드로 나타내면 아래와 같다.

코드를 보기 전에 먼저 의사 코드를 보자.

 

의사 코드

의사 코드에서 정점(v)의 모든 인접 유향(Directed) 간선들을 반복하라고 표기되어 있다.(방향이 있는 간선들)

procedure DFS(G, v) is
    # 첫 노드(정점) 방문 처리
    label v as discovered
    # 정점에 인접한 모든 유향 간선들을 반복
    for all directed edges from v to w that are in G.adjacentEdges(v) do
        # 방문했던 정점 방문 처리
        if vertex w is not labeled as discovered then
            recursively call DFS(G, w)

 

파이썬 코드

위의 의사 코드를 그대로 파이썬 코드로 구현하면 아래와 같다.
방문했던 정점, 즉 discovered를 계속 누적된 결과로 만들기 위해 리턴하는 형태만 받아오도록 처리했고, 나머지는 위의 의사코드와 동일하다.

• 결과는 [1,2, 5, 6, 7, 3, 4]

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


discovered = []  # 방문 노드 저장


# 재귀적으로 구현
def dfs(v, discovered):  # v = vertex(정점)
    discovered.append(v)  # 노드 방문 저장
    for w in graph[v]:
        if w not in discovered:  # 노드가 방문하지 않았다면
            discovered = dfs(w, discovered)

    return discovered

# 첫 번째 인자는 시작 노드를 의미함
# 그림에서 '1'부터 시작하므로
print(dfs(1, discovered))

 

인접 리스트로 그래프를 표현한 DFS 탐색 방식(비재귀적)

이번에는 비재귀적으로 DFS를 구현해본다.

 

의사 코드

• 의사코드는 스택을 이용하여 모든 인접 간선을 추출하고,
• 다시 도착점인 정점을 스택에 삽입한다.

procedure DFS_iterative(G, v) is
    let S be a stack # 'S'를 스택으로 정의
    S.push(v) # S.push(시작 정점)
    while S is not empty do # 스택이 비어 있지 않다면
        v = S.pop() # stack[-1] 팝
        if v is not labeled as discovered then # 정점이 방문했던 정점(discoverd)에 없다면
            label v as discovered # 방문했던 정점에 라벨링 해주고,
            # 모든 인접한 간선을 추출하고,
            for all edges from v to w in G.adjacentEdges(v) do  
                S.push(w) # 도착점인 정점을 스택에 삽입한다.(w)

 

파이썬 코드

위의 의사코드와 마찬가지로 파이썬를 통해 똑같이 정의했다.
하지만 아래의 코드를 돌려보면 [1, 4, 3, 5, 7, 6, 2]로 재귀적으로 DFS 로 구현했던 결과와 다르다.

재귀 DFS는 사전식 순서로 방문한 데 반해, 반복 DFS는 역순으로 방문했다.
스택으로 구현하다 보니 가장 마지막에 삽입된 노드부터 꺼내서 반복하게 되고, 이 경우 인접 노드에서 가장 최근에 담긴 노드, 즉 가장 마지막부터 방문하기 때문이다. 인접 노드를 한꺼번에 추가하는 형태이기 때문에 스택 구조상 가장 마지막을 원소를 pop하게 된다.

하지만 이 경우에도 탐색 순서가 조금 다른 것 뿐이지, 깊이 우선 탐색이 맞다. 넓이 우선 탐색(BFS)이였다면 [1,2,3..] 이 먼저 담겼어야 할 것이다.

def dfs(start_v):
    s = []
    s.append(start_v)
    while s:
        v = s.pop()
        if v not in discovered:
            discovered.append(v)
            for w in graph[v]:
                s.append(w)

    return discovered


print(dfs(1))

 

너비 우선 탐색(Breadth-First Search, BFS)

---

 

깊이 우선 탐색(DFS)와는 다르게 탐색을 할 때 너비를 우선으로 하여 탐색을 수행하는 탐색 알고리즘이다. 

DFS와 동일하게 '맹목적인 탐색'을 하고자 할 때 사용할 수 있는 탐색 기법이다. 출발 노드에서 인접한 모든 노드들을 우선 방문하는 방법이다.

DFS와 구현에서 다른 점은 DFS는 재귀와 Stack 자료구조를 사용했지만, BFS는 Queue 자료구조를 사용하여 구현한다.

(BFS는 재귀적으로 구현하는 것이 불가능함)

 

장점과 단점

• 장점
  • 출발 노드에서 목표 노드까지의 최단 길이 경로를 보장한다.
• 단점
  • 경로가 매우 길 경우에는 탐색 가지가 급격히 증가해 많은 기억 공간을 필요로 하게 된다.

 

BFS의 동작 방식

DFS와는 다르게 깊게 들어가는 것이 아닌, 현재 노드의 인접한 노들들을 먼저 탐색하면서 깊어지고 있다.

 

BFS의 동작방식

 

 

의사 코드

procedure BFS(G, root) is
      let Q be a queue
      label root as explored
      Q.enqueue(root)
      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 labeled as explored then
                  label w as explored
                  w.parent := v
                  Q.enqueue(w)

 

파이썬 코드

위의 의사 코드를 그대로 파이썬 코드로 구현하면 아래와 같다.
방문했던 정점, 즉 discovered 배열에 계속 결과를 누적해 삽입하도록 처리했고, 특정 값을 찾는 것이 아닌 탐색 방식을 보기 위함으로 중간의 return 문이 들어간 if문을 제외하였다. 나머지는 위의 의사코드와 동일하다.

• 결과는 [1, 2, 3, 4, 5, 6, 7]
• 깊이 우선 탐색과는 다르게 1번 노드부터 시작해 인접 노드들을 모두 방문 후 출력하는 결과를 얻었다.

from collections import deque


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

discovered = []


def bfs(root):
    q = deque()
    q.append(root)
    discovered.append(root)
    while q:
        v = q.popleft()
        for w in graph[v]:
            if w not in discovered:
                q.append(w)
                discovered.append(w)

    return discovered


print(bfs(1))

 

 

---

Ref

위키백과 - DFS

위키백과 - 맹목적 탐색

위키백과 - BFS

나동빈님 블로그 - 너비우선탐색

나동빈님 블로그 - 깊이우선탐색