그래프 순회

그래프 순회

그래프를 순회하는 방법에는 다음과 같이 크게 두가지가 있다.

1. DFS(Depth First Search): 깊이 우선 탐색 방법이다. 재귀 또는 스택으로 구현한다. 이 때, 스택으로 구현한 경우 재귀로 구현했을때의 역순으로 순회를 하게된다.
2. BFS(Breadth First Search): 너비 우선 탐색 방법이다. 큐로 구현한다.

DFS

1. 재귀

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

1. 스택

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

BFS

1. 큐

def bfs(start_v):
  discovered = []
  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