普里姆算法
----------data.txt-----------
6 10
0 6 1 5 0 0
6 0 5 0 3 0
1 5 0 5 6 4
5 0 5 0 0 2
0 3 6 0 0 6
0 0 4 2 6 0
----------code.cpp---------
\#include\
\#include\
\#include\
\#define Max\_vnum 50
typedef struct {
int arcs[Max\_vnum][Max\_vnum];
int vexnum,arcnum;
}MGraph;
struct Closedge{int adjvex;int weight;};
int weight=0;
void InitGraph(MGraph &G)
{
FILE \*fin;
int t;
fin=fopen("data.txt","r");
fscanf(fin,"%d%d",&G.vexnum,&G.arcnum);
for(int i=0;i\
{
for(int j=0;j\
{
fscanf(fin,"%d",&t);
if(t==0)
G.arcs[i][j]=INT\_MAX;
else
G.arcs[i][j]=t;
}
}
fclose(fin);
return ;
}
void MiniSpanTree\_PRIM(MGraph G,int u)
{
struct Closedge closedge[Max\_vnum];
int i,j,k;
int t;
k=u;
for(j=0;j\
{
if(j!=k)
{
closedge[j].weight=G.arcs[k][j];
closedge[j].adjvex=u;
}
}
closedge[k].weight=0;
for(i=1;i\
{
t=INT\_MAX;
for(j=0;j\
{
if(closedge[j].weight!=0)
{
if(t\>closedge[j].weight)
{
t=closedge[j].weight;
k=j;
}
}
}
weight+=t;
printf("(v%d,v%d)n",closedge[k].adjvex+1,k+1);
closedge[k].weight=0;
for(j=0;j\
{
if(G.arcs[k][j]\
{
closedge[j].adjvex=k;
closedge[j].weight=G.arcs[k][j];
}
}
}
return ;
}
int main()
{
MGraph G;
InitGraph(G);
MiniSpanTree\_PRIM(G,0);
printf("weight=%dn",weight);
return 0;
}
------------------output----------------
(v1,v3)
(v3,v6)
(v6,v4)
(v3,v2)
(v2,v5)
weight=15
Comments