DFS

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

그래프 정렬 알고리즘의 기반이 된다

더 나아갈 길이 보이지 않을 때까지 깊이 들어간다

재귀를 이용

 

1. 시작 정점을 밟은 후 이 정점을 '방문했음'으로 표시

2. 이 정점과 이웃 정점 중 아직 방문하지 않은 곳을 선택하여

    이를 시작 정점으로 삼고 다시 깊이 우선 탐색

3. 더 이상 방문하지 않은 이웃 정점이 없으면 이전 정점으로 돌아가 단계 2 수행

4. 이전 정점으로 돌아가도 더 이상 방문할 이웃 정점이 없다면

    모든 정점을 방문했으므로 탐색 종료

void DFS( Vertex* V )
{
    Edge* E = NULL;
 
    printf("%d ", V->Data);
 
    V->Visited = Visited;
 
    E = V->AdjacencyList;
 
    while ( E != NULL )
    {
        if ( E->Target != NULL && E->Target->Visited == NotVisited )
            DFS( E->Target );
 
        E = E->Next;
    }
}