1条回答 默认 最新
- 芣苢的成长之路 2023-06-27 11:26关注
MGraph结构体表示邻接矩阵法表示的有向网,包括顶点数组、邻接矩阵和顶点数、弧数等信息。
MiniSpanTree_Prim函数利用Prim算法求最小生成树,并输出最小生成树的边和权值。
ShortestPath_Dijkstra函数利用Dijkstra算法求单源最短路径,并输出起点到各顶点的最短路径和距离。
在主函数中,先读入顶点和弧的权值,然后调用MiniSpanTree_Prim和ShortestPath_Dijkstra函数求解最小生成树和最短路径。#include <stdio.h> #include <stdlib.h> #include <limits.h> #define MAX_VERTEX_NUM 100 // 最大顶点数 #define INF INT_MAX // 无穷大 /* 邻接矩阵法表示的有向网 */ typedef struct { int vertex[MAX_VERTEX_NUM]; // 顶点数组 int arc[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵 int vexnum, arcnum; // 顶点数和弧数 } MGraph; /* Prim算法求最小生成树 */ void MiniSpanTree_Prim(MGraph G, int start) { int lowcost[MAX_VERTEX_NUM]; // 存储V-U中各顶点到U的最小权值 int adjvex[MAX_VERTEX_NUM]; // 存储lowcost中最小值对应的顶点编号 int visited[MAX_VERTEX_NUM] = {0}; // 标记是否已加入U int i, j, k, min; // 初始化lowcost和adjvex数组 for (i = 0; i < G.vexnum; i++) { lowcost[i] = G.arc[start][i]; adjvex[i] = start; } visited[start] = 1; // 将起点start加入U // 依次加入剩余的n-1个顶点 for (i = 1; i < G.vexnum; i++) { // 找到V-U中到U距离最小的顶点k min = INF; for (j = 0; j < G.vexnum; j++) { if (visited[j] == 0 && lowcost[j] < min) { min = lowcost[j]; k = j; } } visited[k] = 1; // 将顶点k加入U // 更新lowcost和adjvex数组 for (j = 0; j < G.vexnum; j++) { if (visited[j] == 0 && G.arc[k][j] < lowcost[j]) { lowcost[j] = G.arc[k][j]; adjvex[j] = k; } } } // 输出最小生成树的边和权值 printf("Prim算法求得的最小生成树为:\n"); for (i = 1; i < G.vexnum; i++) { printf("(%d, %d) ", adjvex[i], i); } printf("\n最小权值为:%d\n", lowcost[1]); } /* Dijkstra算法求单源最短路径 */ void ShortestPath_Dijkstra(MGraph G, int start) { int dist[MAX_VERTEX_NUM]; // 存储起点start到各顶点的最短距离 int path[MAX_VERTEX_NUM]; // 存储起点start到各顶点的最短路径中的上一个顶点 int visited[MAX_VERTEX_NUM] = {0}; // 标记是否已确定最短路径 int i, j, k, min; // 初始化dist和path数组 for (i = 0; i < G.vexnum; i++) { dist[i] = G.arc[start][i]; path[i] = start; } visited[start] = 1; // 将起点start加入集合S // 依次确定剩余的n-1个顶点的最短路径 for (i = 1; i < G.vexnum; i++) { // 找到未确定最短路径的顶点中距离start最近的顶点k min = INF; for (j = 0; j < G.vexnum; j++) { if (visited[j] == 0 && dist[j] < min) { min = dist[j]; k = j; } } visited[k] = 1; // 将顶点k加入集合S // 更新dist和path数组 for (j = 0; j < G.vexnum; j++) { if (visited[j] == 0 && dist[k] + G.arc[k][j] < dist[j]) { dist[j] = dist[k] + G.arc[k][j]; path[j] = k; } } } // 输出起点start到各顶点的最短路径和距离 printf("起点为%d的最短路径如下:\n", start); for (i = 0; i < G.vexnum; i++) { if (i != start) { printf("V%d -> V%d: ", start, i); j = i; while (j != start) { printf("V%d <- ", j); j = path[j]; } printf("V%d,距离为%d\n", start, dist[i]); } } } int main() { MGraph G; int i, j; int start = 0; // 起点编号 // 输入顶点数和弧数 printf("请输入有向网的顶点数和弧数:"); scanf("%d%d", &G.vexnum, &G.arcnum); // 输入顶点 printf("请输入%d个顶点:\n", G.vexnum); for (i = 0; i < G.vexnum; i++) { scanf("%d", &G.vertex[i]); } // 初始化邻接矩阵 for (i = 0; i < G.vexnum; i++) { for (j = 0; j < G.vexnum; j++) { G.arc[i][j] = INF; } } // 输入弧的权值 printf("请输入%d条弧的起点、终点和权值:\n", G.arcnum); for (i = 0; i < G.arcnum; i++) { int start, end, weight; scanf("%d%d%d", &start, &end, &weight); G.arc[start][end] = weight; G.arc[end][start] = weight; // 将有向边直接视为无向边 } // 利用Prim算法求最小生成树 MiniSpanTree_Prim(G, start); // 利用Dijkstra算法求单源最短路径 ShortestPath_Dijkstra(G, start); return 0; }
解决 无用评论 打赏 举报
悬赏问题
- ¥15 #MATLAB仿真#车辆换道路径规划
- ¥15 java 操作 elasticsearch 8.1 实现 索引的重建
- ¥15 数据可视化Python
- ¥15 要给毕业设计添加扫码登录的功能!!有偿
- ¥15 kafka 分区副本增加会导致消息丢失或者不可用吗?
- ¥15 微信公众号自制会员卡没有收款渠道啊
- ¥100 Jenkins自动化部署—悬赏100元
- ¥15 关于#python#的问题:求帮写python代码
- ¥20 MATLAB画图图形出现上下震荡的线条
- ¥15 关于#windows#的问题:怎么用WIN 11系统的电脑 克隆WIN NT3.51-4.0系统的硬盘