正文

掌握C语言深搜，这些例题让你轻松通关

/0 浏览量
0327

引言

深度优先搜索（Depth-First Search，DFS）是一种常用的图遍历算法，在C语言编程中应用广泛。通过学习DFS，我们可以解决许多与路径搜索、拓扑排序、连通性分析等问题相关的算法题。本文将详细介绍C语言实现DFS的方法，并通过一些经典例题帮助读者深入理解和掌握DFS。

DFS基本原理

DFS的基本思想是沿着某一方向搜索到底，如果该方向无路可走，则退回上一个节点，再改变方向搜索。在C语言中，我们可以使用递归或非递归的方式实现DFS。

DFS递归实现

以下是一个使用递归实现DFS的示例代码：

#include <stdio.h>

#define MAX_SIZE 100

// 图的邻接矩阵表示
int graph[MAX_SIZE][MAX_SIZE];

// 访问标记数组
int visited[MAX_SIZE];

// DFS递归函数
void DFS(int v) {
    visited[v] = 1;
    printf("%d ", v); // 标记访问

    for (int i = 0; i < MAX_SIZE; i++) {
        if (graph[v][i] && !visited[i]) {
            DFS(i); // 递归访问未访问的节点
        }
    }
}

int main() {
    // 初始化图和访问标记数组
    for (int i = 0; i < MAX_SIZE; i++) {
        visited[i] = 0;
    }

    // 假设图已初始化，此处省略...

    // 从节点0开始DFS
    DFS(0);

    return 0;
}

DFS非递归实现

以下是一个使用栈实现DFS的非递归示例代码：

#include <stdio.h>

#define MAX_SIZE 100

// 图的邻接矩阵表示
int graph[MAX_SIZE][MAX_SIZE];

// 栈结构
typedef struct {
    int data[MAX_SIZE];
    int top;
} Stack;

// 初始化栈
void initStack(Stack *s) {
    s->top = -1;
}

// 入栈
void push(Stack *s, int x) {
    if (s->top < MAX_SIZE - 1) {
        s->data[++s->top] = x;
    }
}

// 出栈
int pop(Stack *s) {
    if (s->top >= 0) {
        return s->data[s->top--];
    }
    return -1;
}

// 判断栈是否为空
int isEmpty(Stack *s) {
    return s->top == -1;
}

// DFS非递归函数
void DFS(int v) {
    Stack s;
    initStack(&s);

    push(&s, v);
    visited[v] = 1;

    while (!isEmpty(&s)) {
        int v = pop(&s);
        printf("%d ", v); // 标记访问

        for (int i = 0; i < MAX_SIZE; i++) {
            if (graph[v][i] && !visited[i]) {
                push(&s, i);
                visited[i] = 1;
            }
        }
    }
}

int main() {
    // 初始化图和访问标记数组
    for (int i = 0; i < MAX_SIZE; i++) {
        visited[i] = 0;
    }

    // 假设图已初始化，此处省略...

    // 从节点0开始DFS
    DFS(0);

    return 0;
}

经典例题

以下是一些使用DFS解决的实际问题：

  1. 图的遍历：使用DFS遍历一个无向图或有向图。
  2. 拓扑排序：对有向无环图（DAG）进行拓扑排序。
  3. 连通性分析：判断一个无向图或有向图是否连通。
  4. 迷宫求解：使用DFS找到从起点到终点的路径。

总结

通过本文的介绍，相信读者已经对C语言中的DFS有了深入的了解。通过学习和练习以上例题，相信读者能够轻松掌握DFS，并将其应用于解决实际问题。

-- 展开阅读全文 --