[알고리즘] DFS(깊이 우선 탐색) - 코딩 밥상

깊이 우선 탐색(Depth First Search)이란?

'더 나아갈 길이 보이지 않을 때까지 깊이 들어간다'는 원칙으로 그래프 내의 정점을 방문하는 알고리즘입니다.

이 알고리즘은 길이 나오지 않을 때까지 그래프의 정점을 타고 깊이 들어가다가 더 이상 방문해왔던 정점 말고는 다른 이웃을 갖고 있지 않은 정점을 만나면 뒤로 돌아와 다른 경로로 뻗어 있는 정점을 타고 방문을 재개하는 방식으로 동작합니다.

대표적인 이용 방법은 그래프 정렬이나 미로 찾기 문제에서 사용됩니다.

 

알고리즘의 동작 방식을 구체적으로 설명하자면,

1. 시작 정점을 밟은 후 이 정점을 '방문했음'으로 표시합니다.
2. 이 정점과 이웃 정점(인접 정점) 중에 아직 방문하지 않은 곳을 선택하여 이를 시작 정점으로 삼고 다시 깊이 우선 탐색을 사직합니다.
3. 더 이상 방문하지 않은 이웃 정점이 없으면 이전 정점으로 돌아가 앞 과정을 반복합니다.
4. 이전 정점으로 돌아가도 더 이상 방문할 이웃 정점이 없다면 그래프의 모든 정점을 방문했다는 뜻이므로 탐색을 종료합니다.

출처: 위키백과

---

코드 구현

void DFS(Vertex* V){
    Edge* E = NULL;
    
    cout<<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;
    }
}