最小生成树prim算法
#include <iostream>using namespace std;
#define MAXSIZE 100
#define INFINITY 65535
typedef int ElemType;
typedef char VertexType;
typedef struct MGraph{
VertexType vertex;///顶点表
ElemType arc;///邻接矩阵，可看作边表
ElemType vertexNum, arcNum;///vertexNum是顶点数，arcNum是边数
};
void CreateMGraph(MGraph *G) {
int i, j, k ,w ;
cout << "输入边数和顶点数：";
cin >> G->arcNum >> G->vertexNum;
//输入顶点
cout << "输入顶点" << endl;
for (i = 0; i < G->vertexNum; i++) {
cin >> G->vertex;
}
//初始化矩阵
for (i = 0; i < G->vertexNum; i++) {
for (j = 0; j < G->vertexNum; j++) {
G->arc = INFINITY;
G->arc = 0;
}
}
///输入由顶点构成的边
for (k = 0; k < G->arcNum; k++) {
cout << "请输入与边关联的两个顶点的序号和权值,例如（ 1 2 34）：" << endl;
cin >> i >> j>>w;
G->arc = w;
G->arc = G->arc;
}
}
void MinSpanTree_Prim(MGraph G){
int min,i, j, k;
int adjvex;//存放相关顶点的下标
int lowest;//存放相关顶点权值的下标
lowest = 0;
adjvex = 0;//初始化
//初始化
for( i = 0;i < G.vertexNum; i++)
{
adjvex = 0;//初始化
lowest =G.arc;//存放与V0有联系的边的权值
}
//构造最小生成树
for ( i = 1 ;i < G.vertexNum;i++)
{
min = INFINITY;
k = 0;
//找到与起点相关的边的最小权值
for(j =1 ;j < G.vertexNum ; j++)
{
if(lowest != 0 && lowest < min)
{
min = lowest;
k=j;//将当前最小权值的下表存放给k
}
}
cout<<adjvex<<"\t"<<k<<endl;//打印最小权值的边，adjvex在遍历第二次时，存放的是上一个顶点，而k是此次的顶点
lowest = 0;
//开始遍历与这个顶点有关的边+
for( j = 1;j < G.vertexNum; j++ )
{
if(lowest != 0 && G.arc < lowest )
{
lowest = G.arc;//此时lowest【j】是最小权值,且其他都为0或者无穷大,所以这个是最小的，下次循环用
adjvex = k;//将下标为k的顶点放入adjvex
}
}
}
}
void print(MGraph *G){
int i , j;
cout<<"输出邻接矩阵:"<<endl;
//输出矩阵
for(i = 0;i < G->vertexNum; i++)
{
for(j = 0; j <G->vertexNum; j++)
{
cout<<G->arc<<"\t";
}
cout<<endl;
}
}
int main() {
MGraph G;
CreateMGraph(&G);
MinSpanTree_Prim(G);
print(&G);
return 0;
}
这个代码是我已经调试过没问题的 👍
页:
[1]