그래프(graph)란? - DFS와 BFS

비선형 자료구조

• 데이터 구조가 순차적으로 또는 선형으로 배열되지 않는 자료구조
• 순차적이지 않기 때문에 선형에 비해 구현하기도 다소 번잡한 편이지만, 메모리를 좀 더 효율적으로 활용할 수 있다는 장점이 있음
• 대표적인 비선형 자료구조 | 그래프(트리) 등

그래프 순회

• 그래프 순회란 그래프 탐색(search)라고도 불리며 그래프의 각 정점을 방문하는 과정을 말한다.
• 깊이우선탐색(DFS)과 너비우선탐색(BFS) 2가지 알고리즘이 있다. 일일반적으로 BFS에 비애 DFS가 더 널리 쓰인다.
• DFS는 주로 스택이나 재귀로 구현하며, 백트래킹을 통해 뛰어난 효용을 보인다.
• BFS는 주로 큐로 구현하며, 그래프의 최단 경로를 구하는 문제 등에 사용된다. ex) 다익스트라 알고리즘

그래프를 표현하는 방법

• 크게 인접 행렬(adjacency matrix)과 인접 리스트(adjacency list) 2가지의 방법이 있다.
• 인접 리스트
  • 출발 노드를 키로, 도착노드를 값으로 표현한다.
  • 도착 노드는 여러 개가 될 수 있으므로 리스트 형태가 된다.
  • 파이썬의 딕셔너리 자료형으로 아래와 같이 나타낼 수 있다.

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

DFS(깊이 우선탐색)

• 일반적으로 스택으로 구현하며 재귀를 이용하면 좀 더 간단하게 구현할 수 있다.
• 코딩테스트 시에도 재귀 구현이 더 선호되는 편이다.

재귀 구조로 구현

• 방문했던 정점, 즉 discoverd를 계속 누적된 결과로 만들기 위해 재귀구조를 사용한다.

# 재귀를 이용한 DFS 수도코드를 그대로 파이썬으로 옮겨봄
def recursive_dfs(v,discoverd=[]):
    discoverd.append(v)
    for w in graph(v):
        if not w in discoverd:
            discoverd = recursive_dfs(w,discoverd)
    return discoverd

결과 👁‍🗨 [1,2,5,6,7,3,4]

스택을 이용한 반복 구조로 구현

• 스택을 이용해 모든 인접 간선을 추출하고 다시 도착점인 정점을 스택에 삽입하는 구조로 구현한다.

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

결과 👁‍🗨 [1,4,3,5,7,6,2]

똑같은 DFS인데 재귀/스택 방법에 따라 결과가 다를까?

앞서 재귀 dfs는 사전식 순서로 방문한데 비해 반복 DFS는 역순으로 방문한다. 스택으로 구현하다 보니 가장 마지막에 삽입된 노드부터 꺼내서 반복하게 되고 이는 곧 가장 최근에 담긴 노드(마지막노드)부터 방문하기 때문이다.

BFS(너비우선탐색)

큐를 통한 반복구조로 구현

• dfs와 달리 bfs를 반복 구조로 구현할 때는 큐를 이용한다.
• 모든 인접 간선을 추출하고 도착점인 정점을 큐에 삽입한다.

def iterative_bfs(start_v):
    discovered = [start_v]
    queue = [start_v]
    while queue:
        v = queue.pop(0)
        # 리스트 자료형을 사용했지만 pop(0)과 같은 큐의 연산만 사용
        for w in graph[v]:
            if w not in discovered:
                discovered.append(w)
                queue.append(w)
    return discovered

백트래킹

• dfs보다 좀 더 광의의 의미를 지닌 개념(dfs는 백트래킹의 골격을 이루는 알고리즘임)
• 백트래킹은 주로 재귀로 구현한다.
• 브루트 포스와 유사하지만 한번 방문 후 가능성이 없는 경우에는 즉시 후보를 포기한다는 점(가지치기)에서 매번 같은 경로를 방문하는 브루트 포스보다는 훨씬 더 우아한 방식이다.
• 제약충족 문제(Constraint Satisfaction Problem)을 풀이하는 데 필수적인 알고리즘이다.

😍 참고

• 파이썬 알고리즘 인터뷰(책)