[파이썬 알고리즘] DFS와 BFS를 이용한 그래프 탐색

1. 그래프란?

• 연결된 객체 간의 관계를 표현하는 자료구조
• 그래프 G(V, E)는 어떤 자료나 개념을 포함하는 정점의 집합 V(vertex)와 이를 연결하는 간선의 집합 E(edge)로 구성된다.
• 정점(node, vertex): 여러 가지 특성을 가질 수 있는 객체
• 간선(Edge): 정점 사이의 관계

그래프 예시

2. 그래프의 표현 방식

1) 인접 리스트: 딕셔너리를 이용해 출발 노드를 키로, 도착 노드를 값으로 저장하는 방식

• 실제 연결된 노드에 대한 정보만 저장하기 때문에 공간을 덜 차지한다.
• 특정 두 노드를 연결하는 간선이 있는지 확인하기 위한 시간이 오래 걸린다.

2) 인접 행렬: i에서 j로 향하는 경로가 있다면 matrix[i][j] = 1, 없다면 0으로 설정하는 방식

• 많은 공간을 차지하지만, 원하는 경로가 있는지 빠르게 확인할 수 있다.
• 상대적으로 구현이 쉽다.
• 노드에 비해 간선이 많은 경우에 사용하기 좋다.

3. DFS(Depth-First Search, 깊이 우선 탐색)

 깊이 우선 탐색은 가능한 만큼 하나의 경로를 탐색하고, 다른 경로를 탐색하는 방법을 말한다. 미로찾기를 할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 가장 가까운 갈림길로 돌아와서 다른 갈림길로 돌아가는 것과 비슷하다. 

def dfs(v, discovered=[]):
    discovered.append(v)
    for w in list[v]:
        if w not in discovered:
            discovered = dfs(w, discovered)
    return discovered
    
print(f'dfs: {dfs(1)}')

>>>dfs: [1, 2, 3, 4, 5, 6, 7]

 위 코드에서는 인접 리스트 방식으로 저장된 그래프에 대해 깊이 우선 탐색을 실행하고 있다. 노드 v 근처에 있는 모든 노드 중 방문하지 않는 노드를 방문한다. 그리고 방문한 노드는 배열 discovered에 저장한다. 출력된 값은 노드의 탐색 순서이다. 탐색의 과정을 구체적으로 살펴보면 막다른 곳에 도달할 때까지 탐색이 3번 이루어졌다. 먼저 1->2->3->4까지 탐색이 실행되고, 4에서는 더 이상 탐색이 진행될 수 없어 다시 3으로 돌아갔다. 그리고 3 -> 5 ->6으로 탐색이 진행되었다. 마지막으로는 5에서 시작해 7로 탐색이 이루어졌다.

 

DFS의 특징

• BFS보다 좀 더 간단하지만, 속도는 좀 더 느리다.
• 일반적으로 BFS에 비해 널리 쓰인다.
• 자기 자신을 호출하는 재귀의 형태를 가지고 있다.

4. BFS(Breadth-First Search, 너비 우선 탐색)

 너비 우선 탐색은 인접한 노드를 먼저 탐색하는 방법을 말한다. 가까운 노드부터 탐색하기 때문에 최단 경로를 찾을 때 많이 쓰인다.

def bfs(start_v):
    discovered = [start_v]
    queue = [start_v]
    while queue:
        v = queue.pop(0)
        for w in list[v]:
            if w not in discovered:
                discovered.append(w)
                queue.append(w)
    return discovered
    

print(f'bfs: {bfs(1)}')

>>>bfs: [1, 2, 4, 3, 5, 6, 7]

 위 코드에서는 인접리스트 방식으로 저장한 그래프에 대한 너비 우선 탐색을 실행한다. 노드를 고르면 그 노드와 인접한 노드 중 탐색을 진행하지 않은 노드를 전부 큐에 넣는다. 그리고 그 큐의 앞에서부터 탐색하고, 탐색한 노드는 discovered 배열에 추가한다. 이 과정을 큐에 노드가 없어질 때까지 진행한다.

 탐색 과정을 구체적으로 살펴보면 다음과 같다. 먼저 탐색을 시작하는 노드 1과 인접한 2, 4를 탐색한다. 그러면 큐에 2, 4가 들어있고, 2를 탐색하면 큐에는 4, 3이 들어있게 된다. 4에서는 탐색을 진행할 수 없기 때문에 3->5로 탐색을 진행하고, 마지막으로 5에서 인접한 6,7 순서로 탐색을 진행한다.

 

BFS의 특징

• 방문한 노드를 순서대로 저장할 수 있는 큐를 주로 사용한다.
• 다익스트라 알고리즘과 유사하다.