#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; }
时间: 2024-02-14 21:07:05 浏览: 79
这段代码实现了一个图的广度优先遍历算法,使用了邻接矩阵来表示图。其中visited数组用于记录节点是否被访问过,queue数组用于实现队列,front和rear分别是队首和队尾指针。输入时先读入节点个数n,然后再读入邻接矩阵G。接下来对于每个未被访问过的节点i,都从它开始进行广度优先遍历,并输出遍历结果。
相关问题
#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 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。
阅读全文