[파이썬] 그래프, 그래프 탐색(BFS,DFS) 알고리즘의 기초

정점(node)과 간선(edge)으로 각 정점들의 관계를 나타낸 것을 그래프라고 한다.

만약 위와 같이 그래프가 주어진다면,

1은 2, 3, 4 와 연결되어 있고,

2는 5와 연결되어 있고,

3도 5와,

5는 6, 7과,

7은 3과 연결되어 있음을 확인할 수 있다.

파이썬에서는 그래프를 딕셔너리를 이용하여 나타낸다. 그래프의 키는 정점을, 값은 키와 연결된 정점을 나타낸다.

따라서 아래와 같이 나타낼 수 있다.

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

알고리즘 문제를 풀 때는 주로 두 정점의 연결관계를 여러줄에 걸쳐 입력받는다. 위 문제라면 

1 2 

1 3 

1 4 

...

와 같은 식으로 입력을 받는다. 입력받은 값을 리스트로 만들 때는 주로 아래와 같은 방법을 사용한다  

#만약 n개만큼의 정점이 존재하고, m개만큼의 입력을 받는다면 
graph = [[] for _ in range(n+1)] # n+1개만큼의 공간을 만들어서 graph[n]이 n번 정점을 나타내도록 해 준다 
for _ in range(m):
	x,y = map(int,input().split()) #만약 1 2를 입력받으면 
    graph[x].append(y) # 1번 정점에 2를 넣어주고 -> graph[1] = [2] 
    graph[y].append(x) # 2번 정점에 1을 넣어준다 -> graph[2] = [1]

BFS와 DFS는 위와 같은 그래프가 주어졌을 때 탐색하는 알고리즘이다

DFS(깊이 우선 탐색) 

깊이 우선 탐색은 시작점이 있으면, 해당 시작점의 자식으로, 자식의 자식으로 계속해서 깊게 들어가서 탐색하는 알고리즘이다. 만약 노드에 자식이 존재하지 않는다면 그 전의 노드로 돌아가서 다시 탐색한다.

1에서 탐색을 시작한다면, 1의 정점인 2에 방문하고, 2의 자식인 5에 방문하고, 5의 자식인 6에 방문한다.

6은 자식이 없으므로 5로 돌아가서 7에 방문한다.

5의 자식 탐색이 모두 끝났으므로 2로 돌아가고, 여기서도 탐색할 곳이 없으므로 3의 탐색을 시작한다.

3은 자식이 없으므로 다시 1로 돌아가서, 마지막으로 4를 탐색 후 종료한다.

즉, 1 -> 2-> 5 -> 6 -> 7 -> 3 -> 4 순으로 탐색하게 되는 것이다.

알고리즘을 의사코드로 나타내면 다음과 같다

def dfs(v):
    v를 이미 방문한 곳으로 처리한다 
    for 각각의 v에 연결된 모든 정점 i에 대해서:
        if i에 방문하지 않았다면:
            dfs(i)

파이썬 코드로는 다음과 같이 쓸 수 있다

def dfs(v,visited=[]):
    visited.append(v)
    for i in graph[v]:
        if not i in visited:
            visited = dfs(i,visited)
    return visited # [1,2,5,6,7,3,4]

BFS(너비 우선 탐색)

너비 우선 탐색이란 출발 노드에서 인접한 노드를 탐색하는 알고리즘이다. 한 노드의 인접 노드의 처리가 끝나면 노드의 자식으로 내려가서 탐색을 시작하고, 자식의 인접 노드의 탐색이 끝나면 그 자식으로 내려가서 탐색한다.

1에서 탐색을 시작하면 인접한 노드가 없으므로 노드의 자식으로 내려간다.

노드의 첫 번째 자식인 2와, 이에 인접한 3, 4를 탐색한다. 인접 노드의 탐색이 끝났으므로 그 자식인 5로 내려간다.

5는 인접 노드가 없으므로 자식인 6으로 내려가고, 인접 노드인 7을 탐색한 뒤 탐색이 종료된다.

즉, 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 순으로 탐색한다.

알고리즘을 의사코드로 나타내면 다음과 같다.

def bfs(v):
    큐 선언 
    v를 이미 방문한 곳으로 처리 
    v를 큐에 추가해준다 
    while 큐가 비어있지 않다면:
        큐에서 v를 pop해준다 
        for v에 연결된 각각의 정점 i에 대하여:
            if i에 아직 방문하지 않았다면:
                i를 방문한 곳으로 처리한다 
                큐에 i를 추가한다

파이썬 코드로는 다음과 같이 나타낼 수 있다.

def bfs(v): 
    visited = [v]
    que = [v]
    while que:
        v = que.pop(0)
        for i in graph[v]:
            if i not in visited:
                visited.append(i)
                que.append(i)
    return visited # [1, 2, 3, 4, 5, 6, 7]

파이썬에서는 리스트를 이용해서 큐를 충분히 구현할 수 있다. 그러나 pop(0)을 사용하면 리스트의 첫 번째 요소를 뺀 뒤 모든 요소들을 한 칸씩 앞으로 이동하기 때문에 복잡도가 증가한다. 데크를 이용하여 큐를 구현하면 간단하고 획기적으로 속도를 증가시킬 수 있다. pop(0)하는 횟수가 증가할수록 속도 차이가 커진다.

from collections import deque
que = deque()