Triển khai thuật toán DFS (Tìm kiếm theo chiều sâu) trong C

DFS (Depth First Search) là thuật toán duyệt đồ thị theo chiều sâu, dùng ngăn xếp (stack). Khám phá xa nhất có thể trước khi lùi lại.

Thuật toán

1. Khởi tạo stack rỗng
2. Đẩy đỉnh xuất phát, đánh dấu đã thăm
3. Khi stack không rỗng: lấy đỉnh đỉnh stack, tìm đỉnh kề chưa thăm
4. Nếu có: đánh dấu, hiển thị, đẩy vào stack
5. Nếu không: pop khỏi stack
6. Lặp cho đến khi stack rỗng

Chương trình

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

struct Vertex { char label; bool visited; };

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

// Stack: push, pop, peek, isStackEmpty
// Graph: addVertex, addEdge, displayVertex, getAdjUnvisitedVertex
// DFS: depthFirstSearch()

int main() {
    // Khởi tạo ma trận kề 0
    // Thêm đỉnh: S(0), A(1), B(2), C(3), D(4)
    // Thêm cạnh: S-A, S-B, S-C, A-D, B-D, C-D
    // Gọi depthFirstSearch()
    return 0;
}

Kết quả

Depth First Search: S A D B C