C 语言实现深度优先搜索

深度优先搜索简介

深度优先搜索（Depth - First Search，DFS）是一种用于遍历或搜索图或树结构的算法。其核心思想是从起始节点开始，尽可能深入地探索每一条路径，直到无法继续或达到目标节点，然后回溯到最近的未完全探索的节点，继续探索其他路径。

深度优先搜索在图中的应用

在图结构中，DFS 可以帮助我们找到从一个节点到另一个节点的路径，判断图是否连通，甚至用于拓扑排序等。假设我们有一个简单的无向图，节点通过边相连。我们从某个起始节点出发，沿着一条边访问相邻节点，然后从这个相邻节点继续深入，直到遇到一个没有未访问相邻节点的节点，此时开始回溯。

深度优先搜索在树中的应用

对于树结构，DFS 更为直观。我们可以从根节点开始，沿着某一分支一直向下访问，直到叶子节点，然后回溯到父节点，访问其他分支。例如在二叉树中，DFS 可以有先序遍历（根 - 左 - 右）、中序遍历（左 - 根 - 右）和后序遍历（左 - 右 - 根）等不同的遍历方式，这些都是 DFS 的具体体现。

C 语言实现深度优先搜索的基本思路

数据结构准备

在 C 语言中实现 DFS，首先要确定如何表示图或树结构。

图的邻接矩阵表示

对于图，一种常见的表示方法是邻接矩阵。假设我们有一个具有 n 个节点的图，我们可以创建一个 n x n 的二维数组 adjMatrix。如果节点 i 和节点 j 之间有边相连，那么 adjMatrix[i][j] = 1，否则 adjMatrix[i][j] = 0。在无向图中，adjMatrix[i][j] = adjMatrix[j][i]。以下是创建邻接矩阵的代码示例：

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

#define MAX_VERTICES 100

void createAdjMatrix(int **adjMatrix, int vertices, int edges) {
    for (int i = 0; i < vertices; i++) {
        for (int j = 0; j < vertices; j++) {
            adjMatrix[i][j] = 0;
        }
    }
    for (int i = 0; i < edges; i++) {
        int src, dest;
        printf("Enter source and destination vertices for edge %d: ", i + 1);
        scanf("%d %d", &src, &dest);
        adjMatrix[src][dest] = 1;
        adjMatrix[dest][src] = 1;
    }
}

图的邻接表表示

邻接表也是一种常用的图表示方法。对于每个节点，我们用一个链表来存储与其相邻的节点。这种表示方法在处理稀疏图时更为高效。以下是创建邻接表的代码示例：

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

#define MAX_VERTICES 100

typedef struct Node {
    int vertex;
    struct Node *next;
} Node;

typedef struct {
    Node *head[MAX_VERTICES];
} Graph;

void addEdge(Graph *graph, int src, int dest) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->vertex = dest;
    newNode->next = graph->head[src];
    graph->head[src] = newNode;

    newNode = (Node *)malloc(sizeof(Node));
    newNode->vertex = src;
    newNode->next = graph->head[dest];
    graph->head[dest] = newNode;
}

树的表示

对于树，我们可以用结构体来表示节点。以二叉树为例，每个节点包含数据、左子节点指针和右子节点指针。以下是二叉树节点的定义：

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

typedef struct TreeNode {
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

TreeNode* createTreeNode(int data) {
    TreeNode *newNode = (TreeNode *)malloc(sizeof(TreeNode));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

递归实现深度优先搜索

图的递归 DFS

基于邻接矩阵的图的递归 DFS 实现如下：

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

#define MAX_VERTICES 100
int visited[MAX_VERTICES] = {0};

void DFS(int **adjMatrix, int vertex, int vertices) {
    visited[vertex] = 1;
    printf("%d ", vertex);
    for (int i = 0; i < vertices; i++) {
        if (adjMatrix[vertex][i] &&!visited[i]) {
            DFS(adjMatrix, i, vertices);
        }
    }
}

基于邻接表的图的递归 DFS 实现如下：

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

#define MAX_VERTICES 100
int visited[MAX_VERTICES] = {0};

typedef struct Node {
    int vertex;
    struct Node *next;
} Node;

typedef struct {
    Node *head[MAX_VERTICES];
} Graph;

void DFS(Graph *graph, int vertex) {
    visited[vertex] = 1;
    printf("%d ", vertex);
    Node *temp = graph->head[vertex];
    while (temp) {
        if (!visited[temp->vertex]) {
            DFS(graph, temp->vertex);
        }
        temp = temp->next;
    }
}

二叉树的递归 DFS

先序遍历（根 - 左 - 右）的递归实现：

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

typedef struct TreeNode {
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

void preOrder(TreeNode *root) {
    if (root) {
        printf("%d ", root->data);
        preOrder(root->left);
        preOrder(root->right);
    }
}

中序遍历（左 - 根 - 右）的递归实现：

void inOrder(TreeNode *root) {
    if (root) {
        inOrder(root->left);
        printf("%d ", root->data);
        inOrder(root->right);
    }
}

后序遍历（左 - 右 - 根）的递归实现：

void postOrder(TreeNode *root) {
    if (root) {
        postOrder(root->left);
        postOrder(root->right);
        printf("%d ", root->data);
    }
}

非递归实现深度优先搜索

图的非递归 DFS

基于邻接矩阵的图的非递归 DFS 可以使用栈来实现。以下是代码示例：

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

#define MAX_VERTICES 100

void DFSNonRecursive(int **adjMatrix, int start, int vertices) {
    int stack[MAX_VERTICES];
    int top = -1;
    int visited[MAX_VERTICES] = {0};

    stack[++top] = start;
    visited[start] = 1;

    while (top != -1) {
        int vertex = stack[top--];
        printf("%d ", vertex);
        for (int i = vertices - 1; i >= 0; i--) {
            if (adjMatrix[vertex][i] &&!visited[i]) {
                stack[++top] = i;
                visited[i] = 1;
            }
        }
    }
}

基于邻接表的图的非递归 DFS 同样使用栈：

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

#define MAX_VERTICES 100

typedef struct Node {
    int vertex;
    struct Node *next;
} Node;

typedef struct {
    Node *head[MAX_VERTICES];
} Graph;

void DFSNonRecursive(Graph *graph, int start) {
    int stack[MAX_VERTICES];
    int top = -1;
    int visited[MAX_VERTICES] = {0};

    stack[++top] = start;
    visited[start] = 1;

    while (top != -1) {
        int vertex = stack[top--];
        printf("%d ", vertex);
        Node *temp = graph->head[vertex];
        while (temp) {
            if (!visited[temp->vertex]) {
                stack[++top] = temp->vertex;
                visited[temp->vertex] = 1;
            }
            temp = temp->next;
        }
    }
}

二叉树的非递归 DFS

二叉树的非递归先序遍历可以使用栈：

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

typedef struct TreeNode {
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

void preOrderNonRecursive(TreeNode *root) {
    if (!root) return;
    TreeNode *stack[MAX_VERTICES];
    int top = -1;

    stack[++top] = root;

    while (top != -1) {
        TreeNode *node = stack[top--];
        printf("%d ", node->data);
        if (node->right) stack[++top] = node->right;
        if (node->left) stack[++top] = node->left;
    }
}

二叉树的非递归中序遍历也使用栈：

void inOrderNonRecursive(TreeNode *root) {
    if (!root) return;
    TreeNode *stack[MAX_VERTICES];
    int top = -1;
    TreeNode *current = root;

    while (current || top != -1) {
        while (current) {
            stack[++top] = current;
            current = current->left;
        }
        current = stack[top--];
        printf("%d ", current->data);
        current = current->right;
    }
}

二叉树的非递归后序遍历稍微复杂一些，需要两个栈或者一个栈加一个标记变量：

void postOrderNonRecursive(TreeNode *root) {
    if (!root) return;
    TreeNode *stack1[MAX_VERTICES];
    TreeNode *stack2[MAX_VERTICES];
    int top1 = -1, top2 = -1;

    stack1[++top1] = root;

    while (top1 != -1) {
        TreeNode *node = stack1[top1--];
        stack2[++top2] = node;
        if (node->left) stack1[++top1] = node->left;
        if (node->right) stack1[++top1] = node->right;
    }

    while (top2 != -1) {
        TreeNode *node = stack2[top2--];
        printf("%d ", node->data);
    }
}

深度优先搜索的时间和空间复杂度

图的深度优先搜索复杂度

邻接矩阵表示

对于有 n 个节点和 m 条边的图，在邻接矩阵表示下，DFS 的时间复杂度为 (O(n^2))。这是因为在最坏情况下，对于每个节点，我们需要遍历邻接矩阵的一行，该行有 n 个元素。空间复杂度为 (O(n^2))，用于存储邻接矩阵，以及 (O(n)) 用于存储访问标记数组，总共 (O(n^2 + n)=O(n^2))。

邻接表表示

在邻接表表示下，DFS 的时间复杂度为 (O(n + m))。我们需要访问每个节点一次（(O(n))），并且对于每个节点，遍历其邻接表（总共有 (m) 条边，所以是 (O(m))）。空间复杂度为 (O(n + m))，其中 (O(n)) 用于存储节点的链表头指针，(O(m)) 用于存储边的链表节点，以及 (O(n)) 用于访问标记数组，总共 (O(n + m + n)=O(n + m))。

二叉树的深度优先搜索复杂度

对于具有 n 个节点的二叉树，无论是递归还是非递归的 DFS，时间复杂度都是 (O(n))。这是因为我们需要访问每个节点一次。空间复杂度在递归情况下取决于递归调用栈的深度，最坏情况下为 (O(n))（例如单链二叉树），平均情况下为 (O(\log n))（平衡二叉树）。在非递归情况下，空间复杂度取决于栈的大小，最坏情况下也是 (O(n))。

深度优先搜索的应用场景

迷宫求解

迷宫可以看作是一个图，每个单元格是一个节点，相邻单元格之间的通道是边。通过 DFS，我们可以从起点开始，尝试不同的路径，直到找到出口或者遍历完所有可达路径。

拓扑排序

在有向无环图（DAG）中，DFS 可以用于拓扑排序。我们对图进行 DFS，在回溯时记录节点的访问顺序，最后得到的顺序就是拓扑排序的结果。

连通分量查找

对于无向图，我们可以使用 DFS 来查找图的连通分量。从一个未访问的节点开始进行 DFS，所有被访问到的节点构成一个连通分量。重复这个过程，直到所有节点都被访问，就可以找到所有的连通分量。

深度优先搜索实现中的常见问题及解决方法

栈溢出问题（递归实现）

在递归实现 DFS 时，如果图或树的结构很深，可能会导致栈溢出。解决方法可以是增加栈的大小（在一些系统中可行），或者改为非递归实现，使用自己管理的栈。

重复访问问题

如果在实现中没有正确标记已访问的节点，可能会导致节点被重复访问，进入无限循环。确保在访问一个节点后，及时标记其为已访问。对于图，要注意无向图中边的双向性，避免因为双向边导致重复访问。

性能优化

在处理大规模图时，邻接表表示通常比邻接矩阵更高效。另外，可以对非递归实现的栈操作进行优化，例如使用更高效的栈数据结构，减少不必要的内存分配和释放。

深度优先搜索与其他搜索算法的比较

与广度优先搜索（BFS）的比较

• 搜索策略：DFS 沿着一条路径尽可能深入，而 BFS 是一层一层地扩展搜索范围。
• 时间和空间复杂度：在图的情况下，对于邻接矩阵表示，BFS 的时间复杂度也是 (O(n^2))，空间复杂度为 (O(n))（队列存储节点）；对于邻接表表示，BFS 的时间复杂度为 (O(n + m))，空间复杂度为 (O(n))。在二叉树中，BFS 的空间复杂度在最坏情况下为 (O(n))（完全二叉树的最底层节点数）。
• 应用场景：BFS 更适合用于寻找最短路径问题，因为它是按层扩展的；而 DFS 更适合用于需要遍历所有路径或者寻找深度相关的解决方案的问题。

与启发式搜索算法（如 A*算法）的比较

• 搜索策略：A*算法等启发式搜索算法使用启发函数来指导搜索方向，优先选择看起来更有希望达到目标的路径。而 DFS 没有这种启发式指导，只是盲目地深入搜索。
• 时间和空间复杂度：A*算法的时间和空间复杂度取决于启发函数的质量。如果启发函数准确，它可以比 DFS 更高效地找到目标。但在最坏情况下，其复杂度可能与 DFS 相似甚至更差。
• 应用场景：A*算法常用于需要在大量状态中快速找到最优解的场景，如游戏地图寻路等；而 DFS 适用于对路径长度没有严格要求，只需要找到一条可行路径或者遍历所有路径的情况。

通过以上对 C 语言实现深度优先搜索的详细介绍，从数据结构准备、递归与非递归实现、复杂度分析、应用场景到与其他算法的比较，希望读者能对 DFS 在 C 语言中的实现和应用有更深入的理解。在实际编程中，可以根据具体问题的需求，灵活选择合适的实现方式和数据结构，以达到最佳的性能和效果。