[알고리즘] DFS

DFS 깊이 우선 순회 

1. 출발점 S에서 시작한다. 

2. 현재 노드를 Visited로 표시하고 인접한 노드들 중 Unvisited 노드가 존재하면 그 노드로 간다. 

3. 2번을 계속 반복한다. 

4. 만약 Unvisited 이웃 노드가 존재하지 않으면 직전 노드로 되돌아간다. 

5. 다시 2번을 반복한다. 

6. 시작노드 S로 돌아오고 더이상 갈 곳이 없으면 종료한다. 

DFS 수도코드 

DFS(G, v) : Graph G와 Vertex v 

    Visited[v] <- YES 

    For each node u adjacent to v do : 

    If visited[u] = NO then 

        DFS(G, u) 

  BFS와 마찬가지로 Disconnected나 방향 그래프일 경우 모든 노드를 방문하지 않을 수 있다. 

따라서 그래프를 탐색할 때는 DFS_ALL을 호출하자! DFS_ALL 은 모든 점에 대해서 visited[v] = NO일 경우 DFS 실행하면 된다. 

 

DFS를 하기 전에 알아야 하는 선행 개념: Graph, BackTracking.