Python中prim算法或kruscal算法的实现

发布网友 发布时间：2022-04-20 20:25

我来回答

共1个回答

热心网友 时间：2023-07-06 13:23

kruskal:
#include "stdio.h"
#include "stdlib.h"
#include "iostream"
using namespace std;
#define MAXE 100 //MAXE为最大的边数
struct edges
{
int bv,tv,w; //边集类型,存储一条边的起始顶点bv、终止顶点tv和权w
}edges;
typedef struct edges edgeset[MAXE];
//寻找v所在的连通集
int seeks(int set[],int v)
{
int i=v;
while (set[i]>0)

i=set[i];
return i;
}
void kruskal(edgeset ge,int n,int e)
{
int set[MAXE],v1,v2,i,j;
for(i=1;i<=n;i++)
set[i]=0;
i=1; //i表示待获取的生成树中的边数,初值为1
j=1; //j表示ge中的下标,初值为1
while(j<n&&i<=e)//按边权递增顺序,逐边检查该边是否应加入到生成树中
{
v1=seeks(set,ge[i].bv); //确定顶点v所在的连通集
v2=seeks(set,ge[i].tv);
cout<<ge[i].bv<<":"<<v1<<", "<<ge[i].tv<<":"<<v2<<endl;
if(v1!=v2) //当v1,v2不在同一顶点集合,确定该边应当选入生成树
{
cout<<"("<<ge[i].bv<<", "<<ge[i].tv<<") "<<ge[i].w<<endl;
set[v1]=v2;
j++;
}
i++;
}
}
int main()
{
edgeset ee;
int n,e; //n是图的结点数,e是图的边数
n=6;
e=3;
for(int i=1;i<=e;i++)
{
scanf_s("%d",&ee[i].bv);
scanf_s("%d",&ee[i].tv);
scanf_s("%d",&ee[i].w);
}
//ee表示的边集图是按权值从小到大排列的
printf("最小生成树边集及它的权值: \n");
kruskal(ee,n,e);
system("pause");
return 0;
}
prim:

#include "stdio.h"
#include "stdlib.h"
#include "iostream"
using namespace std;
#define N 3
void prim(int c[N][N])
{
//lowcost 为顶点间的最小距离，closest为最小距离上的邻接顶点
//lowcost[i]:与顶点i连通的最小边的权值
//closest[i]:与顶点i连通的邻接顶点
int lowcost[N],closest[N];
int i,j,k,min;

//lowcost,closest初始化
for(i=0;i<N;i++)
{
lowcost[i]=c[0][i];
closest[i]=0;
}
closest[0]=-1;

//寻找U 和 V 之间连接的最短距离的邻接点
for(i=0;i<N;i++)
{
min=32767;
k=0;
//寻找U 和 V 之间连接的最短距离的邻接点
for(j=0;j<N;j++)
{
if((lowcost[j]<min)&&(closest[j]!=-1))
{
min=lowcost[j];
k=j;
}
}
//输出新的邻接顶点，并修改lowcost值
if(k)
{
cout<<"("<<closest[k]<<", "<<k<<") "<<lowcost[k]<<endl;
closest[k]=-1;
for(j=1;j<N;j++)
{
if(closest[j]!=-1)// huo if(!(closest[j]==-1))
{
//修改lowcost值
lowcost[j]=c[k][j];
//修改邻接顶点
closest[j]=k;
}
}
}
}
}

int main()
{
int i,j,a[3][3];
cout<<"请输入二维数组："<<endl;
for(i=0;i<3;i++)

for(j=0;j<3;j++)

cin>>a[i][j];
cout<<"最小树的结构为："<<endl;
prim(a);
int q;
cin>>q;
return 0;
}