#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>头文件。

#include <stdio.h> #include <stdlib.h> #define MAXN 50 int visited[MAXN]; // 记录节点是否被访问过 int queue[MAXN]; // 队列 int front=0,rear=0; // 队首和队尾指针 int n; // 图的节点个数 // 遍历节点v void BFS(int v, int G[][MAXN]) { visited[v]=1; // 标记为已访问 queue[rear++]=v; // 加入队列 while(front<rear) { // 队列非空 int u=queue[front++]; // 取出队首节点 printf("%d ",u); // 输出节点编号 for(int i=0;i<n;i++) { if (G[u][i]&&!visited[i]) { // 若节点i与u相邻且未访问 visited[i] = 1; // 标记为已访问 queue[rear++] = i; // 加入队列 } } } } int main() { int i,j; int G[MAXN][MAXN]; // 图的邻接矩阵 scanf("%d",&n); for(i=0;i<n;i++) { for(j=0;j<n;j++) { scanf("%d",&G[i][j]); } } for(i=0;i<n;i++) { if (!visited[i]) { // 若节点i未被访问 BFS(i,G); // 从节点i开始遍历 } } printf("\n"); return 0; }

这段代码实现了一个图的广度优先遍历算法，使用了邻接矩阵来表示图。其中visited数组用于记录节点是否被访问过，queue数组用于实现队列，front和rear分别是队首和队尾指针。输入时先读入节点个数n，然后再读入邻接矩阵G。接下来对于每个未被访问过的节点i，都从它开始进行广度优先遍历，并输出遍历结果。