[Algorithm] Depth First Search & Breadth First Search

Graph Search Algorithm

Breadth First Search(BFS)

너비 우선 탐색은 깊이가 1인 노드들을 먼저 방문하고 나서, 그 다음에는 깊이가 2인 노드들, 깊이가 3인 노드들을 차례로 방문하다가 더이상 방문할 곳이 없으면 탐색을 마친다. 너비 우선 탐색은 그래프 내 모든 노드를 방문하고 싶을 때, 찾는 것을 발견할 때까지 모든 노드를 적어도 한 번은 방문하고 싶을 때 사용 하면 좋다. 시작 노드로부터 차례로 인접 노드들을 큐(queue) 에 추가하는 방식을 사용해 구현할 수 있다.

Python Implementation Code

adj_list = {'A': set(['B', 'C']),
            'B': set(['A', 'D', 'E']),
            'C': set(['A', 'F']),
            'D': set(['B']),
            'E': set(['B', 'F']),
            'F': set(['C', 'E'])}


def bfs(graph, start):
  from collections import deque
  visited = []
  queue = deque(start)

  while queue:
      n = queue.popleft()
      if n not in visited:
          visited.append(n)
          queue += graph[n] - set(visited)

  return visited

결과는 아래와 같다.

print(bfs(adj_list, 'A'))
>>> ['A', 'C', 'B', 'F', 'E', 'D']

BFS Shortest Path

위의 코드를 조금 수정하여 두 노드 간 가능한 모든 경로를 찾아보자.

Python Implementation Code

def bfs_shortest_path(graph, start, goal):
    from collections import deque
    queue = deque([(start, [start])])  # current node, current path
    result = []

    while queue:
        n, path = queue.popleft()
        if n == goal:
            result.append(path)
        else:
            for m in graph[n] - set(path):
                queue.append((m, path + [m]))

    return result

너비 우선 경로 탐색을 진행하면 가장 먼저 찾은 경로가 최단 경로가 된다.

print(bfs_shortest_path(adj_list, 'A', 'F'))
>>> [['A', 'C', 'F'], ['A', 'B', 'E', 'F']]
print(bfs_shortest_path(adj_list, 'D', 'F'))
>>> [['D', 'B', 'E', 'F'], ['D', 'B', 'A', 'C', 'F']]

Depth First Search(DFS)

깊이 우선 탐색은 이름 그대로 진행 가능한 노드가 없을 때까지 깊게 파고들며 방문하는 방식이며, 더 이상 방문 가능한 노드가 없다면 이전의 위치로 돌아와 다른 방향으로 깊게 파고들며 방문한다. 매우 큰 그래프에서, 탐색을 시작한 노드로부터 너무 멀어지게 되면 즉시 그만두고 싶을 때 사용하면 효과적이다. 트리 순회 기법은 전부 깊이 우선 탐색 이다. 시작 노드로부터 차례로 인접 노드들을 스택(stack) 에 추가하는 방식을 사용해 구현할 수 있다.

Python Implementation Code

adj_list = {'A': set(['B', 'C']),
            'B': set(['A', 'D', 'E']),
            'C': set(['A', 'F']),
            'D': set(['B']),
            'E': set(['B', 'F']),
            'F': set(['C', 'E'])}


def dfs(graph, start):
    visited = []
    stack = [start]

    while stack:
        n = stack.pop()
        if n not in visited:
            visited.append(n)
            stack += graph[n] - set(visited)

    return visited

결과는 아래와 같다.

print(dfs(adj_list, 'A'))
>>> ['A', 'B', 'D', 'E', 'F', 'C']

Reference

• http://ejklike.github.io/2018/01/05/bfs-and-dfs.html
• https://sarah950716.tistory.com/12#footnote_link_12_1
• http://eddmann.com/posts/depth-first-search-and-breadth-first-search-in-python/
• McDowell, G. L. (2016). Cracking the Coding Interview: 189 Programming Questions and Solutions. CareerCup, LLC.
• http://blog.eairship.kr/269