C语言DFS用栈如何实现？

这通常被称为“手动实现DFS”或“非递归DFS”，与使用函数调用栈的“递归DFS”相对。

为什么需要用栈实现DFS？

递归DFS虽然代码简洁,但存在一些潜在问题：

1. 栈溢出：如果树的深度非常大，或者图的路径非常长,递归可能会导致调用栈溢出。
2. 性能开销：函数调用本身有一定的开销，对于性能要求极高的场景,手动管理栈可能更高效。
3. 缺乏控制：在某些复杂场景下，你可能需要更精细地控制DFS的执行过程，比如在遍历的每一步都暂停并恢复,手动管理栈能更好地满足这种需求。

核心思想

DFS的核心思想是“沿着一条路走到底，走不通了再回头”,栈这种数据结构完美地模拟了这个过程：

• 栈：后进先出。
• DFS：访问一个节点，然后深入其第一个邻居，再深入邻居的第一个邻居...这个“深入”的顺序,与将节点压入栈的顺序完全一致。

实现步骤

使用栈实现DFS的通用步骤如下：

1. 创建一个栈：用于存储待访问的节点。
2. 将起始节点压入栈，并标记为“已访问”。
3. 当栈不为空时，循环执行以下操作： a. 从栈顶弹出一个节点 current_node。 b. 处理 current_node（打印它的值）。 c. 遍历 current_node 的所有未访问的邻居。 d. 将这些邻居依次压入栈，并立即将它们标记为“已访问”。

关键点：为什么要在压入栈时就标记为“已访问”？

• 防止重复入栈：一个节点可能被多个邻居指向，如果等到弹出时才标记，它可能会被多次压入栈,导致重复处理和无限循环。
• 保证效率：提前标记可以确保每个节点只被处理一次。

示例1：DFS遍历二叉树

二叉树是图的一种特例,非常适合用来演示DFS。

树结构：

      1
     / \
    2   3
   / \
  4   5

DFS遍历顺序（根-左-右）：1 -> 2 -> 4 -> 5 -> 3

C语言代码实现

#include <stdio.h>
#include <stdlib.h>
// 1. 定义栈的结构
#define MAX_SIZE 100 // 栈的最大容量
// 栈结构
typedef struct {
    int data[MAX_SIZE];
    int top; // 栈顶指针
} Stack;
// 栈的操作函数
void initStack(Stack *s) {
    s->top = -1;
}
int isEmpty(Stack *s) {
    return s->top == -1;
}
int isFull(Stack *s) {
    return s->top == MAX_SIZE - 1;
}
void push(Stack *s, int value) {
    if (isFull(s)) {
        printf("Stack is full!\n");
        return;
    }
    s->data[++s->top] = value;
}
int pop(Stack *s) {
    if (isEmpty(s)) {
        printf("Stack is empty!\n");
        return -1; // 返回一个错误值
    }
    return s->data[s->top--];
}
// 2. 定义二叉树节点的结构
typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;
// 3. 创建新节点
TreeNode* createNode(int val) {
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
    if (newNode == NULL) {
        printf("Memory allocation failed!\n");
        exit(1);
    }
    newNode->val = val;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}
// 4. 使用栈实现DFS遍历二叉树
void dfsWithStack(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    Stack s;
    initStack(&s);
    // 将根节点压入栈并标记为已访问
    // 对于树，我们通过压入栈来表示“已准备访问”
    push(&s, root->val); // 这里简化了，实际应该存节点指针
    // 为了正确演示，我们修改一下，使用指针数组来模拟栈
    // 更好的做法是栈中存放节点指针
    TreeNode* nodeStack[MAX_SIZE];
    int top = -1;
    nodeStack[++top] = root;
    // 创建一个数组来记录访问状态
    int visited[MAX_SIZE] = {0}; // 假设节点值在0-99之间
    while (top != -1) {
        TreeNode* currentNode = nodeStack[top--]; // 弹出栈顶节点
        // 处理当前节点
        printf("%d ", currentNode->val);
        visited[currentNode->val] = 1; // 标记为已访问
        // 注意：为了保证根-左-右的顺序，需要先将右子节点压栈，再左子节点
        // 因为栈是后进先出
        if (currentNode->right && !visited[currentNode->right->val]) {
            nodeStack[++top] = currentNode->right;
        }
        if (currentNode->left && !visited[currentNode->left->val]) {
            nodeStack[++top] = currentNode->left;
        }
    }
    printf("\n");
}
int main() {
    // 构建上面的二叉树
    TreeNode* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    printf("DFS traversal of the binary tree (using stack):\n");
    dfsWithStack(root);
    // 释放内存 (略)
    return 0;
}

代码解释：

1. Stack 结构体：我们实现了一个简单的基于数组的栈。
2. TreeNode 结构体：定义了二叉树的节点。
3. dfsWithStack 函数：
   • 我们使用一个指针数组 nodeStack 来模拟栈，它存放的是 TreeNode*,这比存放节点值更通用。
   • visited 数组用于记录节点是否已被访问,防止重复。
   • 循环：只要栈不空,就继续。
   • 弹出：currentNode = nodeStack[top--]。
   • 处理：打印 currentNode 的值。
   • 压入：关键步骤，为了保证“根-左-右”的顺序，我们必须先压入右子节点，再压入左子节点，这样,左子节点会先被弹出和处理。

示例2：DFS遍历图

图的DFS比树更复杂，因为图中可能存在环，必须使用 visited 数组来避免无限循环。

图结构 (邻接表表示)：

0 -- 1 -- 3
 \   /
  \ /
   2

邻接表：adj[0] = {1, 2}, adj[1] = {0, 2, 3}, adj[2] = {0, 1}, adj[3] = {1}

DFS遍历顺序（从0开始）：0 -> 2 -> 1 -> 3

C语言代码实现

#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 10
// 栈结构 (使用指针数组)
typedef struct {
    int items[MAX_VERTICES];
    int top;
} Stack;
void initStack(Stack *s) { s->top = -1; }
int isEmpty(Stack *s) { return s->top == -1; }
void push(Stack *s, int item) { s->items[++s->top] = item; }
int pop(Stack *s) { return s->items[s->top--]; }
// 图的邻接表表示
typedef struct Graph {
    int numVertices;
    int adjLists[MAX_VERTICES][MAX_VERTICES]; // 简化版邻接表，实际应使用链表
    int count[MAX_VERTICES]; // 记录每个顶点的邻居数量
} Graph;
void createGraph(Graph *g, int v) {
    g->numVertices = v;
    for (int i = 0; i < v; i++) {
        g->count[i] = 0;
    }
}
void addEdge(Graph *g, int src, int dest) {
    // 无向图，添加双向边
    g->adjLists[src][g->count[src]++] = dest;
    g->adjLists[dest][g->count[dest]++] = src;
}
// 使用栈实现DFS遍历图
void dfsGraph(Graph *g, int startVertex) {
    if (startVertex >= g->numVertices) return;
    Stack s;
    initStack(&s);
    int visited[MAX_VERTICES] = {0};
    // 将起始节点压入栈
    push(&s, startVertex);
    while (!isEmpty(&s)) {
        int currentVertex = pop(&s);
        // 如果当前节点未被访问，则处理
        if (!visited[currentVertex]) {
            printf("%d ", currentVertex);
            visited[currentVertex] = 1;
        }
        // 遍历所有邻居，并将未访问的邻居压入栈
        // 为了保证顺序，可以反向遍历邻居列表
        for (int i = g->count[currentVertex] - 1; i >= 0; i--) {
            int neighbor = g->adjLists[currentVertex][i];
            if (!visited[neighbor]) {
                push(&s, neighbor);
            }
        }
    }
    printf("\n");
}
int main() {
    Graph g;
    createGraph(&g, 4);
    addEdge(&g, 0, 1);
    addEdge(&g, 0, 2);
    addEdge(&g, 1, 2);
    addEdge(&g, 1, 3);
    printf("DFS traversal of the graph (starting from vertex 0):\n");
    dfsGraph(&g, 0);
    return 0;
}

代码解释：

1. Graph 结构体：使用邻接表表示图。adjLists 存储邻居，count 存储每个顶点的邻居数量。
2. dfsGraph 函数：
   • visited 数组是必须的,用于标记节点是否已访问。
   • 循环：只要栈不空,就继续。
   • 弹出：currentVertex = pop(&s)。
   • 处理：重要：这里有一个 if (!visited[currentVertex]) 判断，因为一个节点可能被多次压入栈（来自不同的邻居），所以只有在第一次弹出时（即第一次访问时）才处理它。
   • 压入：遍历 currentVertex 的所有邻居，如果邻居未被访问，就将其压入栈，这里我们反向遍历邻居列表，是为了让访问顺序与递归版本更接近（取决于具体实现，正向或反向都可以，只要逻辑正确）。

在C语言中，由于没有内置的栈结构，且递归调用有栈溢出的风险，使用栈手动实现DFS是一种非常重要且实用的技能，它不仅加深了对DFS和栈数据结构的理解,也提供了更健壮和可控的解决方案。