그래프에서의 DFS

깊이 우선 순회 (DFS)

1) 출발점 s에서 시작한다.

2) 현재 노드를 visited로 마크한 후 인접 노드들 중 unvisited 노드가 존재한다면 그 노드로 이동한다. (노드는 임의로 결정.)

3) 2번 작업을 반복한다.

4) 만약 unvisited인 이웃 노드가 존재하지 않는다면 발견할때까지 직전에 방문했었던 노드를 따라 되돌아간다.

5) unvisited 노드를 발견하게 된다면 2번 작업을 다시 반복한다.

6) 시작 노드 s로 돌아온 후 더 이상 갈 곳이 없다면 순회 작업을 종료한다.

  

 

 

- 다른 예시

- 슈도 코드

DFS (G, v)

visited[v] <- true;

for each node u adjacent to v

if visited[u] == false

DFA (G, u);

- 그래프가 disconnected하거나(그래프가 여러개) 방향 그래프라면 DFS에 의해서 모든 노드가 방문되지 않을 수 있다.

- DFS를 반복하여 이 문제를 해결하면 된다.

DFS-ALL (G) {

for each v ∈ V

visited[v] <- false;

for each v ∈ V

if (visited[v] == no)

DFS (G, v);

}

-> 이 작업의 시간 복잡도는 O(n + m)이 된다. 시간 복잡도는 Recursion이 얼마나 많이 실행되느냐에 의해 결정된다.

-> n : 노드의 개수