Depth First Search (DFS) for a Graph: อัลกอริทึม, โค้ด และตัวอย่าง

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

DFS ลงลึก (Depth) มากที่สุดเท่าที่จะไปได้ แล้วค่อย Backtrack กลับมาหาเส้นทางใหม่

การ Implement แบบ Iterative ต้องใช้ Stack แบบ Recursive ไม่ต้องการ Stack ภายนอก ใช้ Internal Stack ของ Recursion Calls แทน

Input

Adjacency Matrix ของกราฟ

  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

Output

DFS Traversal: C F E B D A

Algorithm

dfs(vertices, start)

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

Output: ท่องสำรวจทุกโหนดในกราฟ

Begin
    initially make state unvisited for all nodes
    push start into stack
    while stack is not empty do
        pop element from stack, set to u
        display 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 stack
                    mark ith vertex as visited
                done
        done
End

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

#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 myStack;
    for(int i = 0; i < NODE; i++) {
        vertex[i].state = 0; // not visited
    }
    myStack.push(start);
    while(!myStack.empty()) {
        u = myStack.top(); myStack.pop();
        cout << char(u.val+'A') << " ";
        if(u.state != 1) {
            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;
}

Output

DFS Traversal: C F E B D A