Developer Cafe

그래프 순회 - 하나의 정점에서 그래프에 있는 모든 정점을 한번씩 방문하는 것을 그래프 순회 또는 그래프 탐색 이라고 한다. - 그래프 탐색 방법은 깊이 우선 탐색과 너비 우선 탐색이 있다. 1. 깊이 우선 탐색 깊이 우선 탐색은 시작 정점에서 한 방향으로 갈 수 있는 가장 먼 경로까지 깊이 탐색해가다가 더 이상 갈 곳이 없으면 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아와서 다른 방향의 간선으로 탐색을 계속 함으로써 모든 정점을 방문하는 쉰회 방법이다. 스택을 사용한다. (1) 시작 정점 v를 결정하여 방문한다. (2) 정점 v에 인접한 정점 중에서 ⓐ 방문하지 않은 정점 w가 있으면 정점 v를 스택에 push하고 w를 방문한다. 그리고 w를 v로 설정하고 (2) 반복. ⓑ 방문하지 않은 ..