การนำ DFS (Depth First Search) ไปใช้ในภาษา C

คำอธิบาย

DFS (Depth First Search) เป็นอัลกอริทึมสำรวจกราฟ/ต้นไม้ แบบลึก優先 ใช้ Stack ในการติดตามเส้นทาง สามารถหาเส้นทางระหว่างโหนดได้

อัลกอริทึม DFS

1. Stack เริ่มว่าง
2. Push โหนดเริ่มต้น เข้า Stack, ทำเครื่องหมาย Visited
3. ตรวจสอบโหนดปัจจุบัน ตรงเป้าหมายหรือไม่
4. ไปยังโหนดติดกันที่ยังไม่ Visited (เรียงลำดับสุ่มก็ได้)
5. ถ้าไม่มีโหนดติดกันที่ไม่ Visited → Pop ออกจาก Stack (Backtrack)
6. จบเมื่อ Stack ว่าง หรือเจอเป้าหมาย

โค้ดตัวอย่าง (Graph 5 โหนด)

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX 5

struct Vertex { char label; bool visited; };

int stack[MAX]; int top = -1;
struct Vertex* lstVertices[MAX];
int adjMatrix[MAX][MAX];
int vertexCount = 0;

void push(int item) { stack[++top] = item; }
int pop() { return stack[top--]; }
int peek() { return stack[top]; }
bool isStackEmpty() { return top == -1; }

void addVertex(char label) {
    struct Vertex* v = malloc(sizeof(struct Vertex));
    v->label = label; v->visited = false;
    lstVertices[vertexCount++] = v;
}

void addEdge(int start, int end) {
    adjMatrix[start][end] = 1;
    adjMatrix[end][start] = 1;
}

int getAdjUnvisitedVertex(int v) {
    for (int i = 0; i < vertexCount; i++)
        if (adjMatrix[v][i] == 1 && !lstVertices[i]->visited)
            return i;
    return -1;
}

void depthFirstSearch() {
    lstVertices[0]->visited = true;
    displayVertex(0);
    push(0);
    while (!isStackEmpty()) {
        int u = getAdjUnvisitedVertex(peek());
        if (u == -1) pop();
        else {
            lstVertices[u]->visited = true;
            displayVertex(u);
            push(u);
        }
    }
    for (int i = 0; i < vertexCount; i++) lstVertices[i]->visited = false;
}

void displayVertex(int v) { printf("%c ", lstVertices[v]->label); }

int main() {
    addVertex('S'); // 0
    addVertex('A'); // 1
    addVertex('B'); // 2
    addVertex('C'); // 3
    addVertex('D'); // 4
    addEdge(0,1); addEdge(0,2); addEdge(0,3);
    addEdge(1,4); addEdge(2,4); addEdge(3,4);
    printf("DFS: "); depthFirstSearch();
    return 0;
}

ผลลัพธ์

DFS: S A D B C