너비 우선 탐색(BFS)
너비 우선 탐색은 그래프 탐색 알고리즘으로 같은 깊이에 해당하는
정점부터 탐색하는 알고리즘 입니다.
특징
큐를 이용하여 구현할 수 있다.시작 지점에서가까운 정점부터 탐색한다.- 정점의 수
V, 간선의 수E일때 BFS의 시간복잡도는O(V + E)이다. 최단 경로를 찾아줌
개념
다음과 같은 그래프에서 너비 우선 탐색이 어떻게 실행 되는지 알아봅시다.
- 먼저 큐에 시작 노드를 삽입합니다. 이때 A를 방문 처리해줍니다.
큐: ['A']
방문: ['A']
- 큐에서 노드 하나를 꺼내 해당 노드의 간선중 방문하지 않은 노드를 방문하고 큐에 삽입합니다.
큐: ['B', 'C']
방문: ['A', 'B', 'C']
- 큐에서 B를 꺼내 연결된 노드를 방문처리하고 큐에 삽입합니다.
큐: ['C', 'D', 'E']
방문: ['A', 'B', 'C', 'D', 'E']
-
큐에서 B를 꺼내 연결된 노드를 방문처리하고 큐에 삽입합니다.
큐: ['D', 'E', 'F', 'G']
방문: ['A', 'B', 'C', 'D', 'E', 'F', 'G'] -
큐에서 D를 꺼내 연결된 노드를 방문처리하고 큐에 삽입합니다.
이때 D와 연결된 모든 노드는 방문을 마쳤기때문에 큐에넣지 않고 마칩니다. -
위를 반복하여 큐에 노드가 남지 않으면 마무리 됩니다.
방문기록을 보면 A에서부터 가까운 순서대로 탐색이 완료된 것을 볼 수 있습니다.
깊이 우선 탐색(DFS)
깊이 우선 탐색은 그래프 탐색 알고리즘으로 최대한 깊은 정점부터 탐색하는 알고리즘 입니다.
특징
스택을 이용하여 구현할 수 있다.시작 정점에서 깊은 것 부터 찾는다.- 정점의 수
V, 간선의 수E일때 DFS의 시간복잡도는O(V + E)이다. - 맹목적으로 각 노드를 탐색할 때 주로 사용된다.
개념
다음과 같은 그래프에서 깊이 우선 탐색이 어떻게 실행 되는지 알아봅시다.
- 먼저 스택에 시작 노드를 삽입합니다. 이때 A를 방문 처리해줍니다.
스택: ['A']
방문: ['A']
- 스택의 최상단 노드는 A이므로 인접한 노드중 방문하지 않은 B를 스택에 넣습니다.
스택: ['A', 'B']
방문: ['A', 'B']
- B의 인접 노드 중 방문하지 않는 노드인 D를 스택에 넣습니다.
스택: ['A', 'B', 'D']
방문: ['A', 'B', 'D']
-
D의 인접 노드 중 방문하지 않는 노드인 E를 스택에 넣습니다.
스택: ['A', 'B', 'D', 'E']
방문: ['A', 'B', 'D', 'E']
-
E의 방문하지 않은 인접 노드가 없기때문에 스택에서 E, D, B가 빠져나옵니다.
스택: ['A']
방문: ['A', 'B', 'D', 'E']
- 이후 A의 인접노드인 C가 방문되지 않았기때문에 스택에 넣습니다.
스택: ['A', 'C']
방문: ['A', 'B', 'D', 'E', 'C']
- C의 인접 노드 중 방문하지 않는 노드인 F를 스택에 넣습니다.
스택: ['A', 'C', 'F']
방문: ['A', 'B', 'D', 'E', 'C', 'F']
-
F의 인접 노드 중 방문하지 않는 노드인 G를 스택에 넣습니다.
스택: ['A', 'C', 'F', 'G']
방문: ['A', 'B', 'D', 'E', 'C', 'F', 'G']
-
모든 방문을 마쳤기때문에 스택에서 하나씩 빠져나옵니다.
스택: []
방문: ['A', 'B', 'D', 'E', 'C', 'F', 'G']
