그래프 탐색 알고리즘 (DFS와 BFS)

DFS (Depth First Search)

DFS는 너비우선 탐색이라고 불리며 그래프에서 가장 깊은 곳을 우선적으로 탐색하는 알고리즘이다.

스택 자료구조 혹은 재귀함수를 사용해서 구현한다. 그래프를 구성하는 방법도 두 가지가 있는데 인접 행렬과 인접 리스트로 나뉜다. 이들은 그래프를 코드상에서 표현하는 방식 중의 하나인데 나중에 시간 복잡도를 결정하는 중요한 핵심요소이기도 하다.

인접행렬

너비우선탐색 알고리즘의 그래프를 인접행렬로 나타내는 코드는 아래와 같다.

graph = [[0, 1, 1, 1],
	[1, 0, 0, 1],
    	[1, 0, 0, 1],
    	[1, 1, 1, 0]]

• 인접행렬의 각 행과 열은 노드를 의미한다.
• 즉 0번째 노드와 1번째 노드가 연결되었다면, 0행 1열에 1을 입력하고, 입력되지 않았다면 0을 입력하는 것이다.
• 무향 그래프일 경우 대각선 대칭이지만, 유향그래프일 경우에는 대각선 대칭이 아니다.
• 가중치 그래프의 경우에는 1이 아닌 다른 값을 넣음으로써 가중치를 표현할 수 있다.

인접 리스트

graph = [
    [1, 2, 3],
    [0, 3],
    [0, 3],
    [0, 1, 2]
]

• 인접리스트는 각각의 인덱스에 헤당하는 노드에 연결된 노드들을 리스트형태로 저장하는 방식이다.
• 노드를 문자열로 나타내었을 때 Dictionary를 활용할 수 있어서 편리하다.
• 가중치 그래프에서 가중치를 표현하기 위해서 연결정보에 튜플형태나 다른 방식으로 가중치를 추가적으로 입력해야 한다.

---

BFS (Breadth First Search)

너비 우선 탐색이라고 불린다. 이는 시작점인 루트 노드와 같은 거리에 있는 노드를 우선으로 방문하면서 그래프를 탐색한다.

이는 주로 큐(Queue) 자료구조를 사용해서 구현하지만 큐를 사용하지 않고도 구현할 수 있고, 이도 마찬가지로 그래프를 구성할 때 인접 행렬과 인접 리스트로 나뉜다.

큐를 파이썬으로 구현할 때 queue.pop(0)을 사용하시는 분들이 가끔 있다. 하지만 pop함수는 시간복잡도가 O(N)이라서 비효율적인 코드가 된다. 이러한 단점을 보완하기 위해서 collections 라이브러리의 deque를 사용하는 게 좋을 것 같다!

특징

• 재귀적으로 동작하지 않는다.
• 어떤 노드를 방문했었는지에 대한 여부를 반드시 검사해야한다. 검사하지 않으면 무한루프에 빠질 위험이 있다.
  
  

DFS & BFS의 시간 복잡도

인접행렬에서의 시간 복잡도

• O(V*V) = O(V^2)

인접 리스트에서의 시간 복잡도

• O(V+E)

( DFS와 BFS는 서로 시간 복잡도가 동일하다. )

 

 

GIF 출처 : https://cyc1am3n.github.io/2019/04/26/bfs_dfs_with_python.html