|

  무방향 그래프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: 더 이상 방문할 정점이 존재하지 않으면 방문을 종료한다.