|
무방향 그래프G(V,E)를
구성하는 V(G)에 속하는 모든
정점들을 방문하는 방법을 그래프의
운행이라하며, 스택을 이용하는
깊이 우선 탐색(DFS : Depth First
Search)과 큐를 이용하는 너비
우선 검색(BFS:Breadth First
Serarch) 운행 방법이 있다.
1.
깊이 우선 검색
- 단계 1: 시작 정점 V를
결정하여 방문한다.
- 단계 2: 정점 V에 인접한
정점들 중에서 아직 방문하지
않은 정점 W를 선택하여 W를
시작 정점으로 하여 DFS
방식을 시작한다.
- 단계 3: 모든 인접 정점을
방문한 정점 V를 만나면 방문하지
않은 인접 된 정점을 가졌던
마지막 정점으로 되돌아
가서 DFS 방식을 반복하여
시작한다.
- 단계 4: 더 이상 방문할
정점이 존재하지 않으면 DFS를
종료한다.
2. 너비 우선 검색
- 단계 1: 시작 정점 V를
결정하여 방문한다.
- 단계 2: 정점 V에 인접한
정점들 중에서 아직 방문하지
않은 모든 정점들을 방문하고,
다시 이 정점에 대 하여
인접하여 방문하지 않은 모든
정점에 대해 BFS 방식으로
반복하여 방문한다.
- 단계 3: 더 이상 방문할
정점이 존재하지 않으면 방문을
종료한다.
|