[알고리즘 / Python] BFS , DFS 인접리스트로 구현하기 | 초코더

BFS와 DFS의 개념에 대해 알아보겠습니다.

그래프와 노드 간 연결관계를 인접 리스트를 사용해 표현하겠습니다. 표현 방법에는 인접리스트와 인접행렬이 있습니다.

# 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']]

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