Depth First Search (DFS) สำหรับกราฟ

Depth-First Search (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