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 安卓adb backup备份应用数据失败
- ¥15 eclipse运行项目时遇到的问题
- ¥15 关于#c##的问题:最近需要用CAT工具Trados进行一些开发
- ¥15 南大pa1 小游戏没有界面,并且报了如下错误,尝试过换显卡驱动,但是好像不行
- ¥15 没有证书,nginx怎么反向代理到只能接受https的公网网站
- ¥50 成都蓉城足球俱乐部小程序抢票
- ¥15 yolov7训练自己的数据集
- ¥15 esp8266与51单片机连接问题(标签-单片机|关键词-串口)(相关搜索:51单片机|单片机|测试代码)
- ¥15 电力市场出清matlab yalmip kkt 双层优化问题
- ¥30 ros小车路径规划实现不了,如何解决?(操作系统-ubuntu)