#include <stdio.h> #include <stdlib.h> #define MAXN 1005 int m, n, start; int visited[MAXN]; int v[MAXN][MAXN]; int stack[MAXN]; int top = -1; int isEmpty() { return top == -1; } void push(int x) { stack[++top] = x; visited[x] = 1; } int pop() { int x = stack[top--]; return x; } void dfs(int root) { push(root); printf("%d ", root); while (!isEmpty()) { int cur = stack[top]; int flag = 1; for (int i = 1; i <= m; i++) { if (v[cur][i] && !visited[i]) { push(i); printf("%d ", i); flag = 0; break; } } if (flag) { int x = pop(); printf("%d ", x); } } } int main() { scanf("%d %d %d", &m, &n, &start); for (int i = 1; i <= n; i++) { int a, b; scanf("%d %d", &a, &b); v[a][b] = 1; v[b][a] = 1; } dfs(start); int flag = 1; for (int i = 1; i <= m; i++) { if (!visited[i]) { flag = 0; break; } } return 0; }

这是一个基于邻接矩阵实现的深度优先搜索（DFS）算法。代码中的主要逻辑为：

1. 定义一个栈（数组），用于存储待访问的节点。

2. 定义一个 visited 数组，用于记录每个节点是否被访问过。

3. 定义一个邻接矩阵 v，表示图的结构。

4. 首先将起始节点 push 进栈中，并打印该节点。

5. 不断执行以下步骤，直到栈为空：

1. 取出栈顶节点，并将其标记为已访问。

2. 遍历该节点的所有邻居节点，如果某个邻居节点未被访问，则将其 push 进栈中，并打印该节点。

3. 如果该节点的所有邻居节点都已被访问过，则将该节点 pop 出栈，并打印该节点。

6. 最后根据 visited 数组判断是否所有节点都被访问过。

在 main 函数中，首先读入图的信息（节点数、边数、起始节点以及每条边的两个端点），然后调用 dfs 函数进行深度优先搜索。最后根据 visited 数组的情况输出是否存在未被访问的节点。

相关问题

#include <stdio.h> #include <stdlib.h> #define MAXN 1005 int m, n, start; int visited[MAXN]; int v[MAXN][MAXN]; int top = -1; int isEmpty() { return top == -1; } void push(int x) { top++; visited[top] = x; } int pop() { int x = visited[top]; top--; return x; } void dfs(int root) { visited[root] = 1; for (int i = 1; i <= m; i++) { if (v[root][i] && !visited[i]) { push(root); printf("%d ", i); dfs(i); } } if (root != start) { printf("%d ", pop()); } } int main() { scanf("%d%d%d", &m, &n, &start); for (int i = 1; i <= n; i++) { int a, b; scanf("%d%d", &a, &b); v[a][b] = v[b][a] = 1; } printf("%d ", start); dfs(start); for (int i = 1; i <= m; i++) { if (!visited[i]) { printf("0"); break; } } return 0; }

这是一段用 C 语言编写的深度优先搜索（DFS）程序，用于解决图的连通性问题。该程序的输入包括三个整数 m、n、start，分别代表图中节点数、边数以及起始节点编号。程序通过读入 n 行数据，每行包括两个整数 a 和 b，代表节点 a 和节点 b 之间有一条边。在程序中，使用邻接矩阵 v 来存储图的信息，使用 visited 数组来记录节点是否被访问过。

程序从起始节点开始进行 DFS，对于每个节点，如果它与当前节点有连边且未被访问，就将其加入栈中，并输出该节点的编号。当某个节点的所有邻居节点都被访问过后，将该节点弹出栈并输出其编号。最后，程序检查是否有未被访问的节点，如果有，则说明图不连通，输出 0。

#include <stdio.h> #include <stdlib.h> #include <limits.h> #define MAXN 50 int n; // 图中顶点数 int graph[MAXN][MAXN]; // 邻接矩阵表示的图 int visited[MAXN]; // 标记顶点是否被访问 int dist[MAXN]; // 记录每个顶点与当前生成树的距离 int parent[MAXN]; // 记录每个顶点在当前生成树中的父节点 // 找到当前距离最小的顶点 int findMin() { int min = INT_MAX, minIndex; for (int i = 0; i < n; i++) { if (!visited[i] && dist[i] < min) { min = dist[i]; minIndex = i; } } return minIndex; } // 计算最小生成树的代价 int prim() { int totalCost = 0; // 初始化 for (int i = 0; i < n; i++) { visited[i] = 0; dist[i] = INT_MAX; } dist[0] = 0; // 从任意一个顶点开始都可以 parent[0] = -1; // 0 是根节点，没有父节点 // 构造最小生成树 for (int i = 0; i < n; i++) { int u = findMin(); visited[u] = 1; totalCost += dist[u]; for (int v = 0; v < n; v++) { if (graph[u][v] && !visited[v] && graph[u][v] < dist[v]) { parent[v] = u; dist[v] = graph[u][v]; } } } return totalCost; } int main() { scanf("%d", &n); // 读入邻接矩阵 for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { scanf("%d", &graph[i][j]); } } int cost = prim(); printf("%d\n", cost); return 0; }上述代码的各个步骤都有什么用

这段代码是一个实现Prim算法求解最小生成树的程序。下面是各个步骤的作用：

1. 定义图结构体，包含顶点数n、邻接矩阵graph、标记visited、距离dist和父节点parent。

2. 找到当前距离最小的顶点操作findMin，遍历未被访问的顶点，返回当前距离最小的顶点的位置。

3. 计算最小生成树的代价操作prim，初始化visited、dist和parent数组，将dist数组中第一个元素设为0，表示从该顶点开始，构造最小生成树。然后循环n次，每次找到当前距离最小的顶点u，并将其标记为已访问，累加totalCost。接着遍历与u相邻的未被访问的顶点v，如果u到v的距离小于v的dist，则更新v的dist和parent数组。

4. 主函数main，读入邻接矩阵，调用prim函数计算最小生成树的代价并输出。

注意：本程序中使用了int类型的最大值INT_MAX，需要包含<limits.h>头文件。