그래프 알고리즘 - 3

깊이우선순회(DFS)

1. 출발점 s에서 시작

2. 현재 노드를 visited로 mark하고 인접한 노드들 중 unvisited노드가 존재하면 그 노드로 간다

3. 2번을 반복

4. 만약 unvisited인 이웃 노드가 존재하지 않는 동안 계속해서 직전 노드로 되돌아간다.

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

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

 

수도코드

 

- 그래프가 disconnected이거나 혹은 방향 그래프라면 dfs에 의해서 모든 노드가 방문되지 않을 수도 있음

- DFS를 반복하여 모든 노드 방문

시간복잡도 : O(n+m)

 

* 위의 그림들은 "영리한 프로그래밍을 위한 알고리즘" 강좌에서 가져왔습니다.