[파이썬] 그래프 순회/탐색

그래프 순회/탐색

그래프의 각 정점을 방문하는 과정을 의미한다. 보통 DFS(깊이 우선 탐색), BFS(너비 우선 탐색) 두 가지로 분류하는데 DFS가 BFS보다 더 널리 쓰인다. DFS는 보통 스택 혹은 재귀로 구현하며 백트래킹에서 사용하기 좋고, BFS는 보통 큐로 구현하며 그래프 최단 경로를 구하는 문제에 용이하게 쓰인다. 

 

그래프의 표현은 인접 행렬과 인접 리스트 두 가지 방법이 있다. 인접 리스트는 출발 노드를 키로, 도착 노드를 값으로 한 딕셔너리 형태로 표현할 수 있다. 이 때 도착 노드는 여러 개가 될 수 있으니까 리스트로 나타낸다. 인접 행렬은 이차원 배열로 나타내는데 출발 노드 행과 도착 노드 열에 간선이 존재하면 1, 없으면 0의 값을 넣게 된다.

인접 행렬은 노드의 개수가 간선의 개수보다 많을수록 탐색을 위해 소요되는 시간이 증가해 비효율적이라는 단점이 있다. 이 단점은 인접 리스트로 보완이 되지만 인접 리스트의 단점도 분명히 존재하기 때문에 둘 중 하나를 효과적으로 선택해야 한다. 일단 여기서는 인접 리스트를 이용해 구현하도록 한다. 

 

아래는 딕셔너리로 나타낸 인접 리스트 예시이다.

graph = {
    1: [2, 3],
    2: [4],
    3: [4, 5],
    4: [7],
    5: [6, 7],
    6: [7],
    7: []
}

* 아래 블로그 글을 참고하면 인접 행렬과 인접 리스트에 대해 구체적으로 구현법, 장단점을 정리 해 두셨다. 

duwjdtn11.tistory.com/515

 

---

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

보통 스택으로 구현되고, 재귀를 이용하면 간단하게 구현 가능하다. 

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

위의 예시의 경우 [1->2->4->7->3->5->6]가 탐색 결과가 되겠다.

 

*위키피디아에 자세하게 pseudo code와 함께 설명되어 있다.

en.wikipedia.org/wiki/Depth-first_search

 

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

BFS는 재귀로 동작하지 않기 때문에 큐를 이용한 반복 구현만 가능하다.

모든 인접 간선을 추출하고 도착점인 정점을 큐에 삽입하는 구조로 구현된다.

def iter_bfs(start_v):
    visited = [start_v]
    queue = [start_v]
    while queue:
    	v = queue.pop(0)
        for w in graph[v]:
        	if w not in visited:
            	visited.append(w)
                queue.append(w)
    return visited

위의 예시의 경우 [1->2->3->4->5->7->6]가 탐색 결과가 되겠다.

 

*위키피디아에 자세하게 pseudo code와 함께 설명되어 있다.

en.wikipedia.org/wiki/Breadth-first_search

 

---

백트래킹

백트래킹은 해결책에 대한 후보를 만들어 나가다가 가능성이 없다고 생각되면 바로 후보를 포기하고 바로 뒤로 백트랙하면서 정답을 찾아가는 알고리즘이다. 백트래킹도 DFS와 같은 방법으로 탐색하기 때문에 재귀로 구현할 수 있다. 케이스에 따라 시행착오를 덜 거치고 정답을 도출해 낼 수 있지만 최악의 경우에는 모든 경우를 다 거쳐야 한다는 점에서 brute-force 와 비슷하지만 그래도 가능성이 없으면 후보를 포기하기 때문에 brute-force보다 더 효율적인 알고리즘일 수 있겠다. 가능성이 없는 후보를 포기하는 과정은 가지치기(pruning)이라고 하며 이를 통해 탐색을 최적화 할 수 있다.