너비 우선 탐색(BFS)

너비 우선 탐색은 그래프 탐색 알고리즘으로, 같은 깊이에 해당하는 정점부터 탐색하는 알고리즘이다.

특징

• 큐를 이용하여 구현할 수 있다.
• 시작 지점에서 가까운 정점부터 탐색한다.
• 정점의 수 V, 간선의 수 E일때 BFS의 시간복잡도는 O(V + E)이다.
• 최단 경로를 찾아줌

개념

다음과 같은 그래프에서 너비 우선 탐색이 어떻게 실행되는지 알아보자.

1. 먼저 큐에 시작 노드를 삽입합니다. 이때 A를 방문 처리해줍니다. 큐: ['A']방문: ['A']

1. 큐에서 노드 하나를 꺼내 해당 노드의 간선중 방문하지 않은 노드를 방문하고 큐에 삽입합니다.큐: ['B', 'C']방문: ['A', 'B', 'C']

1. 큐에서 B를 꺼내 연결된 노드를 방문처리하고 큐에 삽입합니다.큐: ['C', 'D', 'E']방문: ['A', 'B', 'C', 'D', 'E']

1. 큐에서 B를 꺼내 연결된 노드를 방문처리하고 큐에 삽입합니다.큐: ['D', 'E', 'F', 'G']방문: ['A', 'B', 'C', 'D', 'E', 'F', 'G']
2. 큐에서 D를 꺼내 연결된 노드를 방문처리하고 큐에 삽입합니다.이때 D와 연결된 모든 노드는 방문을 마쳤기때문에 큐에넣지 않고 마칩니다.
3. 위를 반복하여 큐에 노드가 남지 않으면 마무리 됩니다.방문기록을 보면 A에서부터 가까운 순서대로 탐색이 완료된 것을 볼 수 있습니다.

깊이 우선 탐색(DFS)

깊이 우선 탐색은 그래프 탐색 알고리즘으로, 최대한 깊은 정점부터 탐색하는 알고리즘이다.

특징

• 스택을 이용하여 구현할 수 있다.
• 시작 정점에서 깊은 것 부터 찾는다.
• 정점의 수V, 간선의 수 E일때 DFS의 시간복잡도는 O(V + E)이다.
• 맹목적으로 각 노드를 탐색할 때 주로 사용된다.

개념

다음과 같은 그래프에서 깊이 우선 탐색이 어떻게 실행 되는지 알아봅시다.

1. 먼저 스택에 시작 노드를 삽입합니다. 이때 A를 방문 처리해줍니다. 스택: ['A']방문: ['A']

1. 스택의 최상단 노드는 A이므로 인접한 노드중 방문하지 않은 B를 스택에 넣습니다. 스택: ['A', 'B']방문: ['A', 'B']

1. B의 인접 노드 중 방문하지 않는 노드인 D를 스택에 넣습니다. 스택: ['A', 'B', 'D']방문: ['A', 'B', 'D']

1. D의 인접 노드 중 방문하지 않는 노드인 E를 스택에 넣습니다. 스택: ['A', 'B', 'D', 'E']방문: ['A', 'B', 'D', 'E']
2. E의 방문하지 않은 인접 노드가 없기때문에 스택에서 E, D, B가 빠져나옵니다. 스택: ['A']방문: ['A', 'B', 'D', 'E']

1. 이후 A의 인접노드인 C가 방문되지 않았기때문에 스택에 넣습니다. 스택: ['A', 'C']방문: ['A', 'B', 'D', 'E', 'C']

1. C의 인접 노드 중 방문하지 않는 노드인 F를 스택에 넣습니다. 스택: ['A', 'C', 'F']방문: ['A', 'B', 'D', 'E', 'C', 'F']

1. F의 인접 노드 중 방문하지 않는 노드인 G를 스택에 넣습니다. 스택: ['A', 'C', 'F', 'G']방문: ['A', 'B', 'D', 'E', 'C', 'F', 'G']
2. 모든 방문을 마쳤기때문에 스택에서 하나씩 빠져나옵니다. 스택: []방문: ['A', 'B', 'D', 'E', 'C', 'F', 'G']