그래프 탐색

그래프는 정점의 구성 뿐만 아니라 간선의 연결에도 규칙이 존재하지 않기 때문에 탐색이 복잡하다. 따라서 그래프의 모든 정점을 탐색하기 위한 방법은 다음의 두 가지 알고리즘을 기반으로 한다.

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

그래프 상에 존재하는 임의의 한 정점으로부터 연결되어 있는 한 정점으로만 나아간다.

DFS 에서는 자료구조로 Stack를 사용한다. 일단 연결된 정점으로 탐색하는 것이다. 연결할 수 있는 정점이 있을 때까지 계속 연결하다가 더이상 연결되지 않은 정점이 없으면 바로 그 전 단계의 정점으로 돌아가서 연결할 수 있는 정점이 있는지 살펴봐야 할 것이다. 갔던 길을 되돌아 오는 상황이 존재하는 미로찾기처럼 구성하면 되는 것이다.

즉, 넓게(wide) 탐색하기 전에 깊게(deep) 탐색하는 것이다.

재귀 함수 형태 를 가지고 있다. 전위 순회(Pre-Order Traversals)를 포함한 다른 형태의 트리 순회는 모두 DFS의 한 종류이다.

Time Complexity : O(V+E) … vertex 개수 + edge 개수

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

그래프 상에 존재하는 임의의 한 정점으로부터 연결되어 있는 모든 정점으로 나아간다. Tree 에서의 Level Order Traversal 형식으로 진행되는 것이다.

BFS 에서는 자료구조로 Queue를 사용한다. 연락을 취할 정점의 순서를 기록하기 위한 것이다. 우선, 탐색을 시작하는 정점을 Queue 에 넣는다.(enqueue) 그리고 dequeue 를 하면서 dequeue 하는 정점과 간선으로 연결되어 있는 정점들을 enqueue 한다. 즉 vertex 들을 방문한 순서대로 queue 에 저장하는 방법을 사용하는 것이다.

즉, 깊게(deep) 탐색하기 전에 넓게(wide) 탐색하는 것이다.

BFS는 재귀적으로 동작하지 않는다. ‘Prim’, ‘Dijkstra’ 알고리즘과 유사하다.

Time Complexity : O(V+E) … vertex 개수 + edge 개수 ! BFS 로 구한 경로는 최단 경로이다.

DFS vs BFS

공통점

이 알고리즘을 구현할 때 가장 큰 차이점은, 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사 해야 한다는 것이다. 이를 검사하지 않을 경우 무한루프에 빠질 위험이 있다.

차이점

깊이 우선 탐색(DFS)이 좀 더 간단하다. 단순 검색 속도 자체는 너비 우선 탐색(BFS)가 더 빠르다.

그래프의 모든 정점을 방문하는 것이 주요한 문제