大话数据结构之图-邻接矩阵最小生成树Prim(C++)

el/2024/4/12 15:34:12

大话数据结构

Unit6 图

关于邻接矩阵的最小生成树PRIM算法

代码

#include <iostream>
typedef char VertexType;
typedef int EdgeType;
#define MAXVEX 100
#define INFINITY 65535
using namespace std;
int visited[100];//构建顶点表
typedef struct {VertexType vexs[MAXVEX];        //顶点数组EdgeType arc[MAXVEX][MAXVEX];   //边的矩阵表示int numVertexes, numEdges;      //图中当前的顶点数和边数
}MGraph;//创建邻接矩阵
void CreatMgraph(MGraph* G) {int i, j, k, w;cout << "输入顶点数和边数:" << endl;cin >> G->numVertexes >> G->numEdges;for (i = 0;i < G->numVertexes;i++) {cout << "请输入顶点名:" << endl;cin >> G->vexs[i];}//初始化邻接矩阵for (i = 0;i < G->numVertexes;i++) {for (j = 0;j < G->numVertexes;j++) {G->arc[i][j] = INFINITY;}}//构建邻接矩阵for (k = 0;k < G->numEdges;k++) {cout << "输入边(vi,vj)上的下标i,下标j和权w:" << endl;cin >> i >> j >> w;G->arc[i][j] = w;G->arc[j][i] = G->arc[i][j];}
}//Prim算法生成最小生成树
void MiniSpanTree_Prim(MGraph G) {int min, i, j, k;int adjvex[MAXVEX];int lowcost[MAXVEX];lowcost[0] = 0;adjvex[0] = 0;for (i = 0;i < G.numVertexes;i++) {lowcost[i] = G.arc[0][i];adjvex[i] = 0;}for (i = 1;i < G.numVertexes;i++) {min = INFINITY;j = 1;k = 0;while (j < G.numVertexes) {if (lowcost[j] != 0 && lowcost[j] < min) {min = lowcost[j];k = j;}j++;}cout << G.vexs[k]<<min;lowcost[k] = 0;for (j = 1;j < G.numVertexes;j++) {if (lowcost[j] != 0 && G.arc[k][j] < lowcost[j]) {lowcost[j] = G.arc[k][j];adjvex[j] = k;}}}}int main() {MGraph* grap = (MGraph*)malloc(sizeof(MGraph));CreatMgraph(grap);MiniSpanTree_Prim(*grap);free(grap);return 0;
}

运行结果

在这里插入图片描述
在这里插入图片描述


http://www.ngui.cc/el/3458398.html

相关文章

大话数据结构之图-邻接矩阵最小生成树Kruskal算法(C++)

大话数据结构 Unit6 图 邻接矩阵的最小生成树Kruskal算法 代码 #include <iostream> typedef char VertexType; typedef int EdgeType; #define MAXVEX 100 #define MAXEDGE 10 #define INFINITY 65535 using namespace std; int visited[100];//构建顶点表 typedef …

大话数据结构之图-邻接矩阵最短路径Dijkstra(C++)

大话数据结构 Unit6 图 邻接矩阵的最短路径Dijkstra算法 代码 #include <iostream> typedef char VertexType; typedef int EdgeType; #define MAXVEX 100 #define INFINITY 65535 using namespace std; int visited[100]; #define MAXVEX 9 #define INFINITY 65535 …

大话数据结构之图-邻接矩阵最短路径Floyd(C++)

大话数据结构 Unit6 图 邻接矩阵的最短路径Floyd算法 代码 #include <iostream> typedef char VertexType; typedef int EdgeType; #define MAXVEX 10 #define INFINITY 65535 using namespace std; int visited[100]; typedef int Pathmatirx[MAXVEX][MAXVEX]; type…

信号的时域特征分析matlab程序

%信号的时域特征分析 Nlength(x); tlinspace(0,1,8192); %时域图 figure;plot(t,x);xlabel(‘Time’);ylabel(‘Amplitude’);title(‘时域图’) %信号的平均值 Xmeansum(x)/N %信号的有效值 Xrmssqrt(sum(x.^2)/N) %信号的方根幅值 Xr(sum(abs(x))/N)^2 %信号的绝对平均幅值 a…

4阶经典龙格库塔格式

%用途&#xff1a;4阶经典龙格库塔格式解常微分方程组y’f(x,y),y(x0)y0 %格式&#xff1a;[x,y]marunge4s(dyfun,xspan,y0,h) %dyfun为向量函数f(x,y),xspan为求解区间[x0,xn], %init为初值向量&#xff0c;N为步数&#xff0c;x返回节点&#xff0c;y返回数值解向量 function…

什么是格式良好的XML文件

格式良好的XML是遵循所有“XML文档规则”的XML文档&#xff0c;如下所列。这些规则规定了标记如何置于内容周围&#xff0c;如何按层次嵌套元素&#xff0c;如何为属性加标点以及怎样的元素名称是可接受的。XML文档规则创建XML文档时&#xff0c;必须遵循一些基本的指导原则&am…

关于maven下jsp页面无法使用EL表达式问题

问题&#xff1a;maven环境下搭建项目jsp页面无法使用EL表达式原因&#xff1a;web.xml版本过于老旧解决方案&#xff1a; 将web.xml里面的代码替换成&#xff1a; <?xml version"1.0" encoding"UTF-8"?><web-app xmlns"http://java.sun.c…

maven环境下无法使用C标签库

原因&#xff1a;缺少依赖 解决方案&#xff1a;首先去http://mvnrepository.com/官网分别搜索jstl和standard将椭圆形区域的代码添加到maven的pom.xml即可同上问题解决

java.lang.IllegalArgumentException: org.hibernate.QueryException: Unexpected gap in ordinal paramet

报错内容&#xff1a; java.lang.IllegalArgumentException: org.hibernate.QueryException: Unexpected gap in ordinal parameter labels [0 -> 2] : [0,2] at org.hibernate.internal.ExceptionConverterImpl.convert(ExceptionConverterImpl.java:133) at org.…

hibernate之property配置

<!--声明Hibernate配置文件的开始--> <hibernate-configuration> <!--表明以下的配置是针对session-factory配置的&#xff0c;SessionFactory是Hibernate中的一个类&#xff0c;这个类主要负责保存HIbernate的配置信息&#xff0c;以及对Session的操作--&…