그래프 탐색 알고리즘: BFS, DFS

그래프 탐색 알고리즘

 

그래프 탐색은 하나의 정점으로부터 시작하여 차례대로 모든 정점을 한 번씩 방문하는 것이다.

많은 문제들이 단순히 그래프의 노드를 탐색하는 것으로 해결된다.

그래프의 탐색 방법은 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)의 두가지가 있다.

 

 

깊이 우선 탐색(DFS: depth first search)

 

그래프의 시작 정점에서 한 방향으로 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 다른 방향으로 다시 탐색을 진행한다.

 

 

 

알고리즘

자기 자신을 다시 호출하는 순환 알고리즘의 형태를 띈다.

 

1. 그래프의 시작 정점에서 출발하여 시작 정점 v를 방문하였다고 표시한다.
2. v에 인접한 정점들 중에서 아직 방문하지 않은 정점 u를 선택하여 깊이 우선 탐색을 다시 시작한다.
3. (방문하지 않은 정점이 없다면 탐색 종료)
4. 이 탐색이 끝난후, v에 인접한 정점들 중에서 아직 방문이 안되는 정점이 있다면 다시 깊이 우선탐색을 시작한다.

 

분석

정점의 수가 n이고 간선의 수가 e인 그래프일 경우,

그래프가 인접 리스트로 표현되어 있다면 시간 복잡도는 O(n+e) 이고 인접 행렬로 표현되어 있다면 O(n^2)이다.

희소 그래프인 경우 인접 리스트의 사용이 인접 행렬보다 시간적으로 유리하다.

 

 

너비 우선 탐색(BFS: breath first search)

 

시작 정점으로부터 가장 가까운 정점을 먼저 방문하고 멀리 떨어져있는 정점을 나중에 방문하는 순회 방법이다.

 

 

알고리즘

너비 우선 탐색을 위해서는 가까운 거리에 있는 정점들을 차례로 저장한 후 꺼낼 수 있는 자료구조인 큐가 필요하다.

 

1. 그래프의 시작 정점에서 출발하여 시작 정점 v를 방문하였다고 표시한다.
2. 큐에 정점 v를 삽입한다.
3. 큐에서 정점을 꺼내서 정점을 방문하고 그 정점의 인접 정점들을 큐에 추가한다.
4. 큐가 비워질때까지 3번 과정을 반복한다.

 

분석

깊이우선 탐색과 같이 그래프가 인접 리스트로 표현되어 있으면 전체 수행시간이 O(n+e)이며, 인접 행렬료 표현되어 있는 경우는 O(n^2) 시간이 걸린다.

희소 그래프를 사용할 경우 인접리스트를 사용하는 것이 효율적이다.