การค้นหาเชิงลึกครั้งแรกหรือ DFS สำหรับกราฟ

Depth First Search (DFS) เป็นอัลกอริธึมการข้ามผ่านกราฟ ในอัลกอริธึมนี้จะมีการกำหนดจุดยอดเริ่มต้น และเมื่อพบจุดยอดที่อยู่ติดกัน มันจะเคลื่อนไปยังจุดยอดที่อยู่ติดกันนั้นก่อน และพยายามเคลื่อนที่ในลักษณะเดียวกัน

มันเคลื่อนผ่านความลึกทั้งหมด เท่าที่มันจะไปได้ หลังจากนั้นมันจะย้อนย้อนไปถึงจุดยอดก่อนหน้าเพื่อค้นหาเส้นทางใหม่

ในการใช้งาน DFS แบบวนซ้ำ เราจำเป็นต้องใช้โครงสร้างข้อมูลสแต็ก หากเราต้องการทำแบบเรียกซ้ำ ไม่จำเป็นต้องใช้สแต็กภายนอก สามารถทำสแต็กภายในสำหรับการเรียกซ้ำได้

ป้อนข้อมูล :เมทริกซ์ Adjacency ของกราฟ

  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 0 1
D 1 1 1 0 1 1
E 0 1 0 1 0 1
F 0 0 1 1 1 0

ผลผลิต :DFS Traversal:C F E B D A

อัลกอริทึม

dfs(จุดยอด, จุดเริ่มต้น)

ป้อนข้อมูล − รายการจุดยอดทั้งหมดและโหนดเริ่มต้น

ผลผลิต − สำรวจทุกโหนดในกราฟ

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