깊이우선탐색(DFS : Depth First Search)

1. 깊이 우선 탐색(DFS: Depth First Search)

2. 동작원리

  1) 정점 i 를 방문한다

  2) 정점 i에 인접한 정점 중에서 아직 방문하지 않은 정점이 있으면 이 정점들을 모두 스택에 저장

  3) 스택에서 정점을 삭제하여 새로운 i를 설정하고 단계1)을 수행

  4) 스택이 공백이 되면 연산을 종료한다

    
 

3. 소스

1. void DFS(int * arr, int now,int n) // arr : 스택배열, now : 처음 정점, n : 노드의 개수
2. {
3.     int a = 0;
4.    
5.     stackpush(arr,0); // 시작 노드를 스택에 push
6.  
7.     while(stackempty(top) != -1)
8.     {
9.         now = stackpop(arr);       
10.         if(visit[now] == 0)
11.         { // 아직 노드를 방문 하지 않음
12.             printf("%d ",now);
13.             visit[now] = 1;  // 방문했던 노드를 표시
14.             for(a=n;a>0;a--)
15.             {
16.                 if(visit[a] == 0 && matrix[now][a] == 1) // 인접한 노드중에 방문 안했던 노드를 push
17.                     stackpush(arr,a);
18.             }
19.         }
20.     }
21.     printf("\n");
22.  
23. }

4. 결과