การค้นหาแบบลึก (Depth First Search - DFS) สำหรับกราฟ

บทนำ

Depth-First Search (DFS) เป็นอัลกอริทึมท่องกราฟ (Graph Traversal) เริ่มจากโหนดต้นทาง เมื่อพบโหนดติดกัน จะเดินไปยังโหนดนั้นก่อน และทำซ้ำจนลึกที่สุด (Deep) แล้วค่อย Backtrack กลับมาหาเส้นทางใหม่

การเขียนแบบ Iterative ใช้ Stack ส่วน Recursive ใช้ Stack ภายในของฟังก์ชัน

อินพุตและเอาต์พุต

Input: เมทริกซ์ติดกันของกราฟ 6 โหนด A-F
Output: DFS Traversal: C F E B D A

อัลกอริทึม

dfs(vertices, start)

Input: รายการโหนดทั้งหมด, โหนดเริ่มต้น
Output: ท่องทุกโหนดในกราฟ

Begin
    ตั้งสถานะทุกโหนดเป็น unvisited
    push start เข้า stack
    while stack ไม่ว่าง do
        pop ออกมาเป็น u
        แสดง u
        if u ยังไม่ visited then
            mark u visited
            for โหนด i ที่ติดกับ u do
                if i unvisited then push i, mark i visited
            done
        done
    done
End

ตัวอย่างโค้ด (C++)

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

typedef struct node { int val; int state; } 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

ผลลัพธ์
DFS Traversal: C F E B D A