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