#include <iostream>
using namespace std;
const int INF=99;
const int n=6;
//顶点数
int G[n][n]={INF, 6, 1, 5,INF,INF,
6,INF, 5,INF, 3,INF,
1, 5,INF, 5, 6, 4,
5,INF, 5,INF,INF, 2,
INF, 3, 6,INF,INF, 6,
INF,INF, 4, 2, 6,INF,
};
struct Edge
{
int adjvex;
//最小边在U中的那个顶点
int lowcost;
//最小边上的权值
};
Edge closedge[n];
// closedge[i]表示第i个顶点与第adjvex个顶点相邻,边的最小权值为lowcost
void init()
{
closedge[0].lowcost=0;
//第0个顶点并入U集
for(int i=1;i<n;i++)
{
closedge[i]={0,G[0][i]};
}
}
int min()
{
int v=1;
while(closedge[v].lowcost==0)
v++;
for(int i=1;i<n;i++)
{
if(closedge[i].lowcost)
if(closedge[i].lowcost < closedge[v].lowcost)
v=i;
}
return v;
}
void prim()
{
for(int i=1;i<n;i++)
//遍历其余n-1个顶点
{
int k=min();
cout<<"v"<<closedge[k].adjvex+1<<" ";
cout<<"v"<<k+1<<" ";
cout<<closedge[k].lowcost<<endl;
closedge[k].lowcost=0;
//第K个顶点并入U集
for(int j=1;j<n;j++)
{
if(G[k][j] < closedge[j].lowcost)
closedge[j]={k,G[k][j]};
}
}
}
int main()
{
init();
prim();
return 0;
}
相关文章
- 【数据结构】最小生成树之prim算法和kruskal算法
- 数据结构【完整代码】之(C语言实现【顺序存储表、单链表】创建、插入、删除、查找、输出、求长度、合并的实现与测试)
- 数据结构之实现Kruskal算法,求连通图的最小生成树
- 大话数据结构学习笔记 - 图的最小生成树之Prim算法
- python实现Prim算法求解加权连通图的最小生成树问题
- 数据结构之实现Prim算法,求连通图的最小生成树
- 【数据结构】最小生成树之prim算法和kruskal算法
- 数据结构之实现Kruskal算法,求连通图的最小生成树
- 数据结构之图---最小生成树Prim算法---C++实现
- 【数据结构算法】图(六):基于邻接矩阵的最小生成树(prim算法)Python实现