그래프에 대한 깊이 우선 탐색(DFS)

DFS(깊이 우선 탐색)는 그래프 탐색 알고리즘입니다. 이 알고리즘은 하나의 시작 정점이 주어지고 인접 정점이 발견되면 그 인접 정점으로 먼저 이동하고 같은 방식으로 순회를 시도한다.

가능한 한 전체 깊이를 이동한 다음 역추적하여 새 경로를 찾기 위해 이전 정점에 도달합니다.

반복적인 방식으로 DFS를 구현하려면 스택 데이터 구조를 사용해야 합니다. 재귀적으로 수행하려면 외부 스택이 필요하지 않으며 재귀 호출에 대해 내부 스택을 수행할 수 있습니다.

입력 및 출력

Input:
The Adjacency matrix of a graph.
 
        A B C D E F
      A 0 1 1 1 0 0
      B 1 0 0 1 1 0
      C 1 0 0 1 1 0
      D 1 1 1 0 1 1
      E 0 1 0 1 0 1
      F 0 0 1 1 1 0

Output:
DFS Traversal: C F E B D A

알고리즘

dfs(vertices, start)

입력: 모든 정점 및 시작 노드의 목록입니다.

출력: 그래프의 모든 노드를 탐색합니다.

Begin
   initially make the state to unvisited for all nodes
   push start into the stack

   while stack is not empty, do
      pop element from stack and set to u
      display the node u

      if u is not visited, then
         mark u as visited
         for all nodes i connected to u, do
            if ith vertex is unvisited, then
               push ith vertex into the stack
               mark ith vertex as visited
         done
   done
End

예시

#include<iostream>
#include<stack>
using namespace std;
#define NODE 6

typedef struct node {
   int val;
   int state; //status
}node;

int graph[NODE][NODE] = {
   {0, 1, 1, 1, 0, 0},
   {1, 0, 0, 1, 1, 0},
   {1, 0, 0, 1, 0, 1},
   {1, 1, 1, 0, 1, 1},
   {0, 1, 0, 1, 0, 1},
   {0, 0, 1, 1, 1, 0}
};

void dfs(node *vertex, node start) {
   node u;
   stack<node> myStack;

   for(int i = 0; i<NODE; i++) {
      vertex[i].state = 0;   //not visited
   }

   myStack.push(start);
   while(!myStack.empty()) {
      //pop and print node
      u = myStack.top();
      myStack.pop();
      cout << char(u.val+'A') << " ";

      if(u.state != 1) {
         //update vertex status to visited
         u.state = 1;
         vertex[u.val].state = 1;

         for(int i = 0; i<NODE; i++) {
            if(graph[i][u.val]) {
               if(vertex[i].state == 0) {
                  myStack.push(vertex[i]);
                  vertex[i].state = 1;
               }
            }
         }
      }
   }
}

int main() {
   node vertices[NODE];
   node start;
   char s;

   for(int i = 0; i<NODE; i++) {
      vertices[i].val = i;
   }

   s = 'C';   //starting vertex C
   start.val = s-'A';
   cout << "DFS Traversal: ";
   dfs(vertices, start);
   cout << endl;
}

출력

DFS Traversal: C F E B D A