아래와 같은 그래프가 있다고 가정하자. 노드 A에서 시작하여 그래프의 모든 노드를 방문하려면 어떻게 해야 할까?

먼저, 그래프의 노드 간 연결관계를 표현해보자. 표현 방법으로는 크게 Adjacency list (인접 리스트)Adjacency matrix (인접 행렬)가 있다. 여기서는 인접 리스트를 사용해보았다.

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

노드 개수에 비해 엣지 개수가 훨씬 적은 그래프라면 인접 행렬보다는 인접 리스트를 사용하는 게 탐색에 효율적이다. 전체 노드가 아닌 연결된 노드만 살펴보면 되기 때문이다. 또한, 인접 리스트는 엣지 개수에 비례하는 메모리만 차지하는 장점이 있다. 단, 두 노드의 연결관계를 알고싶을 때는 인접 행렬이 효율적이다.

너비 우선 탐색 (Breadth-first-search, BFS)

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

아래와 같이 시작 노드로부터 차례로 인접 노드들을 큐(queue)에 추가하는 방식을 사용해 구현할 수 있다.

def bfs(graph, start):
    visited = []
    queue = [start]

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

결과는 아래와 같다.

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

두 노드 간 경로 탐색

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

def bfs_paths(graph, start, goal):
    queue = [(start, [start])]
    result = []

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

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

>> bfs_paths(graph, 'A', 'F')
[['A', 'C', 'F'], ['A', 'B', 'E', 'F']]
>> bfs_paths(graph, 'D', 'F')
[['D', 'B', 'E', 'F'], ['D', 'B', 'A', 'C', 'F']]

깊이 우선 탐색 (Depth-first-search, DFS)

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

과거 위치의 인접 노드보다 현재 위치의 인접 노드를 먼저 방문한다는 특징을 가지므로, 아래와 같이 스택(stack)을 사용해 구현할 수 있다.

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

결과는 아래와 같다.

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

두 노드 간 경로 탐색

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

def dfs_paths(graph, start, goal):
    stack = [(start, [start])]
    result = []

    while stack:
        n, path = stack.pop()
        if n == goal:
            result.append(path)
        else:
            for m in graph[n] - set(path):
                stack.append((m, path + [m]))
    return result
>> dfs_paths(graph, 'A', 'F')
[['A', 'C', 'F'], ['A', 'B', 'E', 'F']]
>> dfs_paths(graph, 'D', 'F')
[['D', 'B', 'A', 'C', 'F'], ['D', 'B', 'E', 'F']]

깊이 우선 탐색은 너비 우선 탐색과는 달리 최단 경로를 가장 먼저 찾지 못할 수도 있다.

출처