無向圖深度優先搜尋 (DFS) C 語言實作：鄰接表與遞迴/非遞迴詳解

編輯：關於C語言

一、圖的儲存結構：鄰接表

對於稀疏圖，鄰接表比鄰接矩陣更節省空間。每個頂點維護一條邊的鏈結串列：

// 邊節點
typedef struct ArcNode {
    int adjvex;              // 邊指向的頂點編號
    struct ArcNode *next;    // 下一條邊
    // int weight;            // 權重（可選）
} ArcNode;

// 頂點節點
typedef struct VNode {
    int data;                // 頂點資料/編號
    ArcNode *first;          // 第一條邊
} VNode;

// 圖結構
typedef struct {
    VNode *adjList;          // 頂點陣列
    int vexNum;              // 頂點數
    int arcNum;              // 邊數
} Graph;

二、DFS 核心演算法

三色標記法追蹤頂點狀態：

WHITE (-1)：未發現
GRAY (0)：已發現，正在探索其鄰接點（遞迴堆疊中）
BLACK (1)：已完成，所有鄰接點探索完畢

遞迴版本（簡潔直觀）

void DFS_Recursive(Graph *G, int v, int *color) {
    color[v] = GRAY;
    printf("%d ", v); // 前序處理：進入頂點
    
    for (ArcNode *p = G->adjList[v].first; p; p = p->next) {
        if (color[p->adjvex] == WHITE) {
            DFS_Recursive(G, p->adjvex, color);
        }
    }
    
    color[v] = BLACK; // 後序處理：離開頂點
}

// 包裝函數
void DFS_Wrapper(Graph *G, int start) {
    int *color = calloc(G->vexNum, sizeof(int));
    for (int i = 0; i < G->vexNum; i++) color[i] = WHITE;
    DFS_Recursive(G, start, color);
    free(color);
}

非遞迴版本（顯式堆疊，避免堆疊溢位）

typedef struct { int *data; int top; int cap; } Stack;

void stack_init(Stack *s, int cap) {
    s->data = malloc(cap * sizeof(int));
    s->top = -1; s->cap = cap;
}
void stack_push(Stack *s, int v) { s->data[++s->top] = v; }
int stack_pop(Stack *s) { return s->data[s->top--]; }
int stack_empty(Stack *s) { return s->top == -1; }

void DFS_Iterative(Graph *G, int start) {
    int *color = calloc(G->vexNum, sizeof(int));
    for (int i = 0; i < G->vexNum; i++) color[i] = WHITE;
    
    Stack st; stack_init(&st, G->vexNum);
    stack_push(&st, start);
    color[start] = GRAY;
    printf("%d ", start);
    
    while (!stack_empty(&st)) {
        int v = st.data[st.top]; // 查看堆疊頂但不彈出
        ArcNode *p = G->adjList[v].first;
        int found = 0;
        
        // 尋找第一個未訪問的鄰接點
        while (p) {
            if (color[p->adjvex] == WHITE) {
                color[p->adjvex] = GRAY;
                printf("%d ", p->adjvex);
                stack_push(&st, p->adjvex);
                found = 1;
                break;
            }
            p = p->next;
        }
        
        if (!found) { // 所有鄰接點已訪問，回溯
            stack_pop(&st);
            color[v] = BLACK;
        }
    }
    free(color);
    free(st.data);
}

三、完整可執行範例

#include <stdio.h>
#include <stdlib.h>

#define MAXV 100
#define WHITE -1
#define GRAY 0
#define BLACK 1

typedef struct ArcNode { int adjvex; struct ArcNode *next; } ArcNode;
typedef struct VNode { ArcNode *first; } VNode;

VNode adjList[MAXV];
int vexNum = 7;

// 建立範例圖：0-1, 0-2, 1-3, 2-3, 2-4, 3-5, 4-5, 4-6, 5-6
void buildGraph() {
    int edges[][2] = {{0,1},{0,2},{1,3},{2,3},{2,4},{3,5},{4,5},{4,6},{5,6}};
    int m = sizeof(edges)/sizeof(edges[0]);
    for (int i = 0; i < m; i++) {
        int u = edges[i][0], v = edges[i][1];
        ArcNode *n1 = malloc(sizeof(ArcNode)); n1->adjvex = v; n1->next = adjList[u].first; adjList[u].first = n1;
        ArcNode *n2 = malloc(sizeof(ArcNode)); n2->adjvex = u; n2->next = adjList[v].first; adjList[v].first = n2;
    }
}

void DFS_Recursive(int v, int *color) {
    color[v] = GRAY;
    printf("%d ", v);
    for (ArcNode *p = adjList[v].first; p; p = p->next)
        if (color[p->adjvex] == WHITE) DFS_Recursive(p->adjvex, color);
    color[v] = BLACK;
}

int main() {
    buildGraph();
    int color[MAXV];
    for (int i = 0; i < vexNum; i++) color[i] = WHITE;
    printf("DFS 遞迴 (從 2 開始): ");
    DFS_Recursive(2, color);
    printf("\n");
    // 輸出: 2 0 1 3 5 4 6
    return 0;
}