[그래프] 그래프의 탐색 7/4

 - 간선을 이용하여 그래프 상의 모든 노드를 한번식 방문하는 것

1) 깊이 우선 탐색
 - 선택된 노드와 연결될 노드 중 아직 탐색 되지 않은 노드를 먼저 선택하는 방법
 ⓐ 재귀
  깊이우선(node n){
   visit n; // n방문
   print n; // n 출력
   for(n에 연결된 모든 노드를 하나씩 선택 = u){
    if(u!=visit){ // u가 방문되지 않은 노드라면
     깊이우선(u); // u 탐색 시작
    }
   }
  ⓑ 스택이용
   깊이우선(node n){
    stack S;
    visit n; // n 방문
    push(S,n); // 스택 S에 n을 push
    while( !empty(S) ){ // S가 비어 있지 않으면 계속 실행
     u = pop(s); // S에 들어 있는 값 Pop > u에 저장
      for(u에 연결된 모든 노드를 하나씩 선택 = w){
       if(w!= visit){
        visit w;
        push(S,w);
      }
     }
    }
   }
ex)

탐색 순서 :
0 - 1 - 3 - 2 - 5

1) 넓이 우선 탐색
 - 선택된 노드의 이전 노드에 연결된 모든 노드가 탐색되는 방식
 ⓐ 큐를 이용한 구현
   넓이우선(node n){
    Queue Q;
    visit n; // n 방문
    enqueue(Q,n); // 큐 Q에 n을 enqueue
    while( !empty(Q) ){ // Q가 비어 있지 않으면 계속 실행
     u = depueue(Q); // Q에 들어 있는 값 dequeue > u에 저장
      for(u에 연결된 모든 노드를 하나씩 선택 = w){
       if(w!= visit){
        visit w;
        enqueue(S,w);
      }
     }
    }
   }
ex)

탐색 순서 :
0 - 2 - 1 - 5 - 3