Depth First Search (깊이 우선 탐색) → 그래프를 정렬하는 알고리즘으로 응용됨
Breath First Search (너비 우선 탐색) → 그래프에서 최단 경로를 찾는 알고리즘으로 응용됨
Depth First Search (깊이 우선 탐색)
더 나아갈 길이 보이지 않을 때까지 깊이 들어간다의 원칙으로 그래프 내의 정점을 방문하는 알고리즘
•
더 이상 방문했던 정점 말고는 다른 이웃을 갖고 있지 않은 정점을 만나면 뒤로 돌아와 다른 경로로 뻗어 있는 정점을 타고 방문을 재개하는 방식으로 동작한다.
•
트리의 전위탐색 방법을 그래프에 적용한 것 (preorder tree traversal)
알고리즘
1.
시작 정점을 밟은 후 이 정점을 ‘방문했음’으로 표시한다.
2.
그리고 이 정점과 이웃하고 있는 정점 (즉, 인접 정점) 중에 아직 방문하지 않은 곳을 선택하여 이를 시작 정점으로 삼아 다시 깊이 우선 탐색을 시작한다. (1단계로 돌아가 반복한다)
3.
정점에 더 이상 방문하지 않은 인접 정점이 없으면 이전 정점으로 돌아가서 단계 2를 수행한다.
4.
이전 정점으로 돌아가도 더 이상 방문할 이웃이 없다면 그래프의 모든 정점을 방문한 것으로 탐색을 종료한다.
void DFS(Vertext* V)
{
Edge* E = NULL;
printf("%d ", V->Data);
V->Visited = Visited; // 방문했음
E = V->AdjacencyList;
// 현재 정점의 모든 인접 정점에 대해 DFS를 재귀적으로 호출
while (E != NULL)
{
if (E->Target != NULL && E->Target->Visited == NotVisited)
DFS(E->Target); // 인접 정점을 시작으로 또 깊이 우선 탐색을 수행
E = E-Next;
}
}
C
Breath First Search (너비 우선 탐색)
거리가 가까운 곳부터 방문하는 탐색 방법
•
시작 정점을 지나 깊이가 1인 모든 정점을 방문하고, 깊이가 2인 모든 정점을 방문하는 식으로 한 단계씩 깊이를 더해가며 해당 깊이에 있는 모든 정점들을 방문해 나가는 방식
•
트리의 레벨 우선 탐색을 그래프에 적용한 것 (level order tree traversal)
알고리즘
1.
시작 정점을 ‘방문했음'으로 표시하고 큐에 삽입한다. (Enqueue)
2.
큐로 부터 정점을 제거한다. (Dequeue) 제거한 정점이 이웃하고 있는 인접 정점 중 아직 방문하지 않은 곳들을 ‘방문했음'으로 표시하고 큐에 삽입한다.
3.
큐가 비게 되면 탐색이 끝난 것으로 간주하며, 큐가 빌 때까지 과정 2를 반복한다.
void BFS(Vertex* V, LinkedQueue* Queue)
{
Edge* E = NULL;
printf("%d ", V->Data);
V->Visited = Visited;
LQ_Enqueue(&Queue, LQ_CreateNode(V)); // 시작 정점을 큐에 삽입
while( !LQ_IsEmpty(Queue) ) // 큐가 비게 되면 탐색이 끝난 것으로 간주
{
Node* Popped = LQ_Dequeue(&Queue); // 큐의 전단을 제거
V = Popped->Data;
E = V->AdjacencyList;
while(E != NULL) // 큐에서 꺼낸 정점에 인접 정점을 조사
{
V = E->Target;
if( V != NULL && V->Visited == NotVisited) // 미방문 정점만 방문
{
printf("%d ", V->Data);
V->Visited = Visited;
LQ_Enqueue(&Queue, LQ_CreateNode(V));
}
E = E->Next;
}
}
}
C
