prim算法c语言
把main函数改成：
main(){
GraphMatrix graph = {
"abcd",
{{7,8,Max,15},{12,100,6,20},{Max,100,4,13},{Max,4,8,10}},
};
Edge mst[Max];
int i,j;
prim(graph,mst);
for(j=0;j<Max;j++)
{
printf("%c\t",mst[j].stop_vex);
printf("%c\t",mst[j].start_vex);
printf("%d\n",mst[j].weight);
}
}
还有GraphMatrix结构体里的vexs数组最好定义为vexs[VN+1]给字符串末尾的‘\0'留地方。
② 用c语言描述prim算法求最小生成树.... 求高人指点啊，给出完整的代码，那个邻接矩阵是要要一次全部输入的
#include <cstdio>
#include <iostream>
#include <memory.h>
using namespace std;
const int maxn=102;
const int inf=1<<30;
int map[maxn][maxn];
int dis[maxn];
bool flag[maxn];
int a,b,c,n,m,ans;
void init()
{
memset(map,-1,sizeof(map));
for(int i=0;i<m;i++)
{
scanf("%d%d%d",&a,&b,&c);
if(map[a][b]==-1 || c< map[a][b])
{
map[a][b]=map[b][a]=c;
}
}
}
void prim()
{
memset(flag,false,sizeof(flag));
for(int i=1;i<=n;i++)dis[i]=inf;
dis[1]=0;
ans=0;
for(int j=1;j<=n;j++)
{
int now,value=inf;
for(int i=1;i<=n;i++)
{
if(flag[i]==false && dis[i]<value)
{
value=dis[i];
now=i;
}
}
if(value==inf)
{
cout << "-1" <<endl;
return;
}
flag[now]=true;
ans+=dis[now];
for(int i=1;i<=n;i++)
{
if(!flag[i] && map[now][i]!=-1 && dis[i]>map[now][i])
dis[i]=map[now][i];
}
}
cout << ans <<endl;
}
int main()
{
//'freopen("in.txt","r",stdin);
while(cin >> n >> m)
{
init();
prim();
}
return 0;
}
测试数据：
Sample Input
3 3
1 2 1
1 3 1
2 3 3
Sample Output
2
既然问到了prim算法相信你能看懂测试数据是什么意思~
③ 用prim算法的思想，用C语言编写出最小生成树的方法的代码
PrimMST(G，T，r){
//求图G的以r为根的MST，结果放在T=(U，TE)中
InitCandidateSet(…)；//初始化：设置初始的轻边候选集，并置T=({r}，￠)
for(k=0；k<n-1；k++){
//求T的n-1条树边
(u，v)=SelectLiShtEdge(…)；//选取轻边(u，v)；
T←T∪{(u，v)}；//扩充T，即(u，v)涂红加入TE，蓝点v并人红点集U
ModifyCandidateSet(…)；
//根据新红点v调整候选轻边集
}
}
④ 急！数据结构最小生成树prim算法C语言实现
Kruskal算法：
void Kruskal(Edge E[],int n,int e)
{
int i,j,m1,m2,sn1,sn2,k;
int vset[MAXE];
for (i=0;i<n;i++) vset[i]=i; //初始化辅助数组
k=1; //k表示当前构造最小生成树的第几条边,初值为1
j=0; //E中边的下标,初值为0
while (k<n) //生成的边数小于n时循环
{
m1=E[j].u;m2=E[j].v; //取一条边的头尾顶点
sn1=vset[m1];sn2=vset[m2]; //分别得到两个顶点所属的集合编号
if (sn1!=sn2) //两顶点属于不同的集合,该边是最小生成树的一条边
{
printf(" (%d,%d):%d/n",m1,m2,E[j].w);
k++; //生成边数增1
for (i=0;i<n;i++) //两个集合统一编号
if (vset[i]==sn2) //集合编号为sn2的改为sn1
vset[i]=sn1;
}
j++; //扫描下一条边
}
}
Prim算法：
void prim(MGraph g,int v)
{
int lowcost[MAXV],min,n=g.vexnum;
int closest[MAXV],i,j,k;
for (i=0;i<n;i++) //给lowcost[]和closest[]置初值
{
lowcost[i]=g.edges[v][i];
closest[i]=v;
}
for (i=1;i<n;i++) //找出n-1个顶点
{
min=INF;
for (j=0;j<n;j++) //在(V-U)中找出离U最近的顶点k
if (lowcost[j]!=0 && lowcost[j]<min)
{
min=lowcost[j];k=j;
}
printf(" 边(%d,%d)权为:%d/n",closest[k],k,min);
lowcost[k]=0; //标记k已经加入U
for (j=0;j<n;j++) //修改数组lowcost和closest
if (g.edges[k][j]!=0 && g.edges[k][j]<lowcost[j])
{
lowcost[j]=g.edges[k][j];closest[j]=k;
}
}
}
⑤ 数据结构 图的基本操作要C语言的完整代码！！
#include<stdio.h>
#define n 6
#define e 8
void CREATGRAPH();
typedef char vextype;
typedef float adjtype;
typedef struct{
vextype vexs[n];
adjtype arcs[n][n];
}graph;
int main()
{
CREATGRAPH();
printf("创建成功！\n");
}
void CREATGRAPH()
{
graph *ga;
int i,j,k;
float w;
for(i=0;i<n;i++)
ga->vexs[i]=getchar();
for(i=0;i<n;i++)
for(j=0;j<n;j++)
ga->arcs[i][j]=0;
for(k=0;k<e;k++)
{
scanf("%d%d%f",&i,&j,&w);
ga->arcs[i][j]=w;
ga->arcs[j][i]=w;
}
printf("创建成功！\n");
}
没写完，，自己加加吧！
⑥ 最小生成树怎么求
一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边。最小生成树可以用kruskal（克鲁斯卡尔）算法或Prim（普里姆）算法求出。
求MST的一般算法可描述为：针对图G，从空树T开始，往集合T中逐条选择并加入n-1条安全边（u，v），最终生成一棵含n-1条边的MST。
当一条边（u，v）加入T时，必须保证T∪{(u，v)}仍是MST的子集，我们将这样的边称为T的安全边。
伪代码
GenerieMST(G){//求G的某棵MST
T〈-￠； //T初始为空，是指顶点集和边集均空
while T未形成G的生成树 do{
找出T的一条安全边（u，v）；//即T∪{(u，v)}仍为MST的子集
T=T∪{(u，v)}； //加入安全边，扩充T
}
return T； //T为生成树且是G的一棵MST
}
注意：
下面给出的两种求MST的算法均是对上述的一般算法的求精，两算法的区别仅在于求安全边的方法不同。
为简单起见，下面用序号0，1，…，n-1来表示顶点集，即是：
V(G)={0，1，…，n-1}，
G中边上的权解释为长度，并设T=(U，TE）。
求最小生成树的具体算法（pascal):
Prim算法
procere prim(v0:integer);
var
lowcost,closest:array[1..maxn] of integer;
i,j,k,min:integer;
begin
for i:=1 to n do begin
lowcost[i]:=cost[v0,i];
closest[i]:=v0;
end;
for i:=1 to n-1 do begin
{寻找离生成树最近的未加入顶点 k}
min:=maxlongint;
for j:=1 to n do
if (lowcost[j]<min) and (lowcost[j]<>0) then begin
min:=lowcost[j];
k:=j;
end;
lowcost[k]:=0; {将顶点k 加入生成树}
{生成树中增加一条新的边 k 到 closest[k]}
{修正各点的 lowcost 和 closest 值}
for j:=1 to n do
if cost[k,j]<lowcost[j] then begin
lowcost[j]:=cost[k,j];
closest[j]:=k;
end;
end;
end;
Kruskal算法
按权值递增顺序删去图中的边，若不形成回路则将此边加入最小生成树。
function find(v:integer):integer; {返回顶点 v 所在的集合}
var i:integer;
begin
i:=1;
while (i<=n) and (not v in vset) do inc(i);
if i<=n then find:=i else find:=0;
end;
procere kruskal;
var
tot,i,j:integer;
begin
for i:=1 to n do vset:=i;{初始化定义 n 个集合，第 I个集合包含一个元素 I}
p:=n-1; q:=1; tot:=0; {p 为尚待加入的边数，q 为边集指针}
sort;
{对所有边按权值递增排序，存于 e中，e.v1 与 e.v2 为边 I 所连接的两个顶点的
序号，e.len 为第 I条边的长度}
while p>0 do begin
i:=find(e[q].v1）;j:=find(e[q].v2）;
if i<>j then begin
inc(tot,e[q].len);
vset:=vset+vset[j];vset[j]:=[];
dec(p);
end;
inc(q);
end;
writeln(tot);
end;
C语言代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
#include<stdio.h>
#include<stdlib.h>
#include<iostream.h>
#defineMAX_VERTEX_NUM20
#defineOK1
#defineERROR0
#defineMAX1000
typedefstructArcell
{
doubleadj;
}Arcell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedefstruct
{
charvexs[MAX_VERTEX_NUM];//节点数组
AdjMatrixarcs;//邻接矩阵
intvexnum,arcnum;//图的当前节点数和弧数
}MGraph;
typedefstructPnode//用于普利姆算法
{
charadjvex;//节点
doublelowcost;//权值
}Pnode,Closedge[MAX_VERTEX_NUM];//记录顶点集U到V-U的代价最小的边的辅助数组定义
typedefstructKnode//用于克鲁斯卡尔算法中存储一条边及其对应的2个节点
{
charch1;//节点1
charch2;//节点2
doublevalue;//权值
}Knode,Dgevalue[MAX_VERTEX_NUM];
//-------------------------------------------------------------------------------
intCreateUDG(MGraph&G,Dgevalue&dgevalue);
intLocateVex(MGraphG,charch);
intMinimum(MGraphG,Closedgeclosedge);
voidMiniSpanTree_PRIM(MGraphG,charu);
voidSortdge(Dgevalue&dgevalue,MGraphG);
//-------------------------------------------------------------------------------
intCreateUDG(MGraph&G,Dgevalue&dgevalue)//构造无向加权图的邻接矩阵
{
inti,j,k;
cout<<"请输入图中节点个数和边/弧的条数：";
cin>>G.vexnum>>G.arcnum;
cout<<"请输入节点：";
for(i=0;i<G.vexnum;++i)
cin>>G.vexs[i];
for(i=0;i<G.vexnum;++i)//初始化数组
{
for(j=0;j<G.vexnum;++j)
{
G.arcs[i][j].adj=MAX;
}
}
cout<<"请输入一条边依附的定点及边的权值："<<endl;
for(k=0;k<G.arcnum;++k)
{
cin>>dgevalue[k].ch1>>dgevalue[k].ch2>>dgevalue[k].value;
i=LocateVex(G,dgevalue[k].ch1）;
j=LocateVex(G,dgevalue[k].ch2）;
G.arcs[i][j].adj=dgevalue[k].value;
G.arcs[j][i].adj=G.arcs[i][j].adj;
}
returnOK;
}
intLocateVex(MGraphG,charch)//确定节点ch在图G.vexs中的位置
{
inta;
for(inti=0;i<G.vexnum;i++)
{
if(G.vexs[i]==ch)
a=i;
}
returna;
}
voidMiniSpanTree_PRIM(MGraphG,charu)//普利姆算法求最小生成树
{
inti,j,k;
Closedgeclosedge;
k=LocateVex(G,u);
for(j=0;j<G.vexnum;j++)
{
if(j!=k)
{
closedge[j].adjvex=u;
closedge[j].lowcost=G.arcs[k][j].adj;
}
}
closedge[k].lowcost=0;
for(i=1;i<G.vexnum;i++)
{
k=Minimum(G,closedge);
cout<<"("<<closedge[k].adjvex<<","<<G.vexs[k]<<","<<closedge[k].lowcost<<")"<<endl;
closedge[k].lowcost=0;
for(j=0;j<G.vexnum;++j)
{
if(G.arcs[k][j].adj<closedge[j].lowcost)
{
closedge[j].adjvex=G.vexs[k];
closedge[j].lowcost=G.arcs[k][j].adj;
}
}
}
}
intMinimum(MGraphG,Closedgeclosedge)//求closedge中权值最小的边，并返回其顶点在vexs中的位置
{
inti,j;
doublek=1000;
for(i=0;i<G.vexnum;i++)
{
if(closedge[i].lowcost!=0&&closedge[i].lowcost<k)
{
k=closedge[i].lowcost;
j=i;
}
}
returnj;
}
voidMiniSpanTree_KRSL(MGraphG,Dgevalue&dgevalue)//克鲁斯卡尔算法求最小生成树
{
intp1,p2,i,j;
intbj[MAX_VERTEX_NUM];//标记数组
for(i=0;i<G.vexnum;i++)//标记数组初始化
bj[i]=i;
Sortdge(dgevalue,G);//将所有权值按从小到大排序
for(i=0;i<G.arcnum;i++)
{
p1=bj[LocateVex(G,dgevalue[i].ch1）];
p2=bj[LocateVex(G,dgevalue[i].ch2）];
if(p1!=p2）
{
cout<<"("<<dgevalue[i].ch1<<","<<dgevalue[i].ch2<<","<<dgevalue[i].value<<")"<<endl;
for(j=0;j<G.vexnum;j++)
{
if(bj[j]==p2）
bj[j]=p1;
}
}
}
}
voidSortdge(Dgevalue&dgevalue,MGraphG)//对dgevalue中各元素按权值按从小到大排序
{
inti,j;
doubletemp;
charch1,ch2;
for(i=0;i<G.arcnum;i++)
{
for(j=i;j<G.arcnum;j++)
{
if(dgevalue[i].value>dgevalue[j].value)
{
temp=dgevalue[i].value;
dgevalue[i].value=dgevalue[j].value;
dgevalue[j].value=temp;
ch1=dgevalue[i].ch1;
dgevalue[i].ch1=dgevalue[j].ch1;
dgevalue[j].ch1=ch1;
ch2=dgevalue[i].ch2;
dgevalue[i].ch2=dgevalue[j].ch2;
dgevalue[j].ch2=ch2;
}
}
}
}
voidmain()
{
inti,j;
MGraphG;
charu;
Dgevaluedgevalue;
CreateUDG(G,dgevalue);
cout<<"图的邻接矩阵为："<<endl;
for(i=0;i<G.vexnum;i++)
{
for(j=0;j<G.vexnum;j++)
cout<<G.arcs[i][j].adj<<"";
cout<<endl;
}
cout<<"=============普利姆算法===============\n";
cout<<"请输入起始点：";
cin>>u;
cout<<"构成最小代价生成树的边集为：\n";
MiniSpanTree_PRIM(G,u);
cout<<"============克鲁斯科尔算法=============\n";
cout<<"构成最小代价生成树的边集为：\n";
MiniSpanTree_KRSL(G,dgevalue);
}
pascal算法
program didi;
var
a:array[0..100000] of record
s,t,len:longint;
end;
fa,r:array[0..10000] of longint;
n,i,j,x,y,z:longint;
tot,ans:longint;
count,xx:longint;
procere quick(l,r:longint);
var
i,j,x,y,t:longint;
begin
i:=l;j:=r;
x:=a[(l+r) div 2].len;
repeat
while x>a[i].len do inc(i);
while x<a[j].len do dec(j);
if i<=j then
begin
y:=a[i].len;a[i].len:=a[j].len;a[j].len:=y;
y:=a[i].s;a[i].s:=a[j].s;a[j].s:=y;
y:=a[i].t;a[i].t:=a[j].t;a[j].t:=y;
inc(i);dec(j);
end;
until i>j;
if i<r then quick(i,r);
if l<j then quick(l,j);
end;
function find(x:longint):longint;
begin
if fa[x]<>x then fa[x]:=find(fa[x]);
find:=fa[x];
end;
procere union(x,y:longint);{启发式合并}
var
t:longint;
begin
x:=find(x);
y:=find(y);
if r[x]>r[y] then
begin
t:=x;x:=y;y:=t;
end;
if r[x]=r[y] then inc(r[x]);
fa[x]:=y;
end;
begin
readln(xx,n);
for i:=1 to xx do fa[i]:=i;
for i:=1 to n do
begin
read(x,y,z);
inc(tot);
a[tot].s:=x;
a[tot].t:=y;
a[tot].len:=z;
end;
quick（1,tot);{将边排序}
ans:=0;
count:=0;
i:=0;
while count<=x-1 do{count记录加边的总数}
begin
inc(i);
with a[i] do
if find(s)<find(t) then
begin
union(s,t);
ans:=ans+len;
inc(count);
end;
end;
write(ans);
end.
Prim
var
m,n:set of 1..100;
s,t,min,x,y,i,j,k,l,sum,p,ii:longint;
a:array[1..100,1..100]of longint;
begin
readln(p);
for ii:=1 to p do
begin
k:=0; sum:=0;
fillchar(a,sizeof(a),255);
readln(x);
m:=[1];
n:=[2..x];
for i:=1 to x do
begin
for j:=1 to x do
begin
read(a[i,j]);
if a[i,j]=0
then a[i,j]:=maxlongint;
end;
readln;
end;
for l:=1 to x-1 do
begin
min:=maxlongint;
for i:=1 to x do
if i in m
then begin
for j:=1 to x do
begin
if (a[i,j]<min)and(j in n)
then begin
min:=a[i,j];
s:=i;
t:=j;
end;
end;
end;
sum:=sum+min;
m:=m+[t];
n:=n-[t];
inc(k);
end;
writeln(sum);
end;
end.
⑦ 普林算法如果两条边权相同怎么办
普利姆算法（prim算法），每次选择最小边的时候，可能存在多条同样权值的边可选，此时任意选其一就可以。
参考资料：数据结构（C语言版 第二版）
⑧ c语言最小生成树
我前段时间写了一个。
你自己改改吧。
#include <stdio.h>
#include <math.h>
struct point
{
double x,y;
};
struct distence
{
double _distence;
bool islink;
};
static double CaculateDistence(point x,point y)
{
return sqrt(pow((x.x-y.x),2.0)+pow((x.y-y.y),2.0));
}
static bool isInGroup(int *group,int value)
{
for(int i=0;i<10;++i)
{
if(value==group[i]){return true;}
}
return false;
}
int main()
{
/* 初始化各个点的值 */
point _point[10]={{2.4169,8.2119},{4.0391,0.1540},{0.9645,0.4302},{1.3197,1.6899},{9.4205,6.4912},
{9.5613,7.3172},{5.7521,6.4775},{0.5978,4.5092},{2.3478,5.4701},{3.5316,2.9632}};
/* 初始化距离数组 */
distence _distence[10][10]={0.0,0};
////////////////////////////////////////////////////////////////
/* 计算距离 */
int i,j;
for (i=0;i<10;++i)
{
for(j=0;j<10;++j)
{
if(i==j)_distence[i][j]._distence=0;
else _distence[i][j]._distence=CaculateDistence(_point[i],_point[j]);
}
}
////////////////////////////////////////////////////////////////////
int pointgroup[10]={0};
int size=1;
pointgroup[0]=0;
///////////////////////////////////////////////////////////////
/* 计算最小生成树 */
for(;size<10;)
{
double dismin=32454.0;
int tmpx=0,tmpy=0;
for(i=0;i<size;++i)
{
for(j=0;j<10;++j)
{
if(_distence[pointgroup[i]][j].islink)continue;
else if(pointgroup[i]==j)continue;
else if(_distence[pointgroup[i]][j]._distence<dismin &&
!isInGroup(pointgroup,j)){
dismin=
_distence[pointgroup[i]][j]._distence;
tmpx=pointgroup[i];
tmpy=j;
}
else continue;
}
}
_distence[tmpx][tmpy].islink=true;
_distence[tmpy][tmpx].islink=true;
pointgroup[size]=tmpy;
++size;
}
//////////////////////打印最小生成树//////////////////////////
for(i=0;i<10;++i)
{
for(int j=0;j<10;++j)
{
if(_distence[i][j].islink)printf("%d ------ %d\n",i,j);
}
}
return 0;
}
⑨ C语言算法求解：对任意给定的网络（顶点数和边数自定），设计算法生成它的最小生成树。
上一个图和代码：
图1为要创建的图，图2为对应的最小生成树
代码为：
//图论之最小生成树：prim算法实现
#include"stdio.h"
#include"malloc.h"
//声明
voidoutput(structadjacentlisthead*alh,intmapsize);
structadjacentlistson//邻接表项结构体
{
intsonelement;
intquanvalue;
structadjacentlistson*next;
};
structadjacentlisthead//邻接表头结构体
{
charflag;
intelement;
intcurqvalue;
structadjacentlisthead*previous;
structadjacentlistson*startson;
};
structadjacentlisthead*mapinitialnize(intmapsize)//初始化图函数
{
structadjacentlisthead*alh=NULL;
structadjacentlistson*newnode=NULL;
inti,x,y,z;
alh=malloc(sizeof(structadjacentlisthead)*mapsize);
if(alh==NULL)
returnNULL;
for(i=0;i<mapsize;i++)
{
alh[i].flag=0;
alh[i].element=i+1;
alh[i].curqvalue=0;
alh[i].previous=NULL;
alh[i].startson=NULL;
}
scanf("%d%d%d",&x,&y,&z);
while(x&&y)//直到输入的x,y中至少有一个0为止
{
newnode=malloc(sizeof(structadjacentlistson));
newnode->sonelement=y;
newnode->quanvalue=z;
newnode->next=alh[x-1].startson;
alh[x-1].startson=newnode;
scanf("%d%d%d",&x,&y,&z);
}
returnalh;
}
intfindminnode(structadjacentlisthead*alh,intmapsize)//找到最小权值对应的结点
{
inti,minvalue=~(1<<(sizeof(int)*8-1)),minplace=0;
for(i=0;i<mapsize;i++)
{
if(alh[i].flag==0&&alh[i].curqvalue!=0)
{
if(alh[i].curqvalue<minvalue)
{
minvalue=alh[i].curqvalue;
minplace=i+1;//
}
}
}
returnminplace;
}
voidfindthemintree(structadjacentlisthead*alh,intstartplace,intmapsize)//找到最小生成树
{
structadjacentlistson*alstmp=NULL;
intcurplace=startplace;
while(curplace)
{
alstmp=alh[curplace-1].startson;
alh[curplace-1].flag=1;//正在访问
while(alstmp)
{
if(alh[alstmp->sonelement-1].flag==0)
{
if(alh[alstmp->sonelement-1].curqvalue==0||(alh[alstmp->sonelement-1].curqvalue>alstmp->quanvalue))//比较方法与有权图有一点不同
{
alh[alstmp->sonelement-1].curqvalue=alstmp->quanvalue;
alh[alstmp->sonelement-1].previous=&alh[curplace-1];
}
}
alstmp=alstmp->next;
}
curplace=findminnode(alh,mapsize);//通过函数找到最小的一个结点
}
}
voidoutput(structadjacentlisthead*alh,intmapsize)
{
inti;
for(i=0;i<mapsize;i++)
{
printf("%d点的权值为：%d ",i+1,alh[i].curqvalue);
}
printf("................................................... ");
}
intmain()
{
structadjacentlisthead*alh=NULL;
intmapsize=7,startplace=1;
alh=mapinitialnize(mapsize);
findthemintree(alh,startplace,mapsize);
output(alh,mapsize);
}
输入数据对应第一图：
122
134
141
212
243
2510
314
342
365
411
423
432
457
468
474
5210
547
576
635
648
671
744
756
761
000
⑩ 关于PRIM算法求最小生成树的问题（c语言版）
/*
邻接矩阵存储图
测试数据
6 10
1 2 6
1 3 1
1 4 5
2 3 5
2 5 3
3 4 5
3 5 6
3 6 4
4 6 2
5 6 6
*/
#include <stdio.h>
#include <limits.h>
#define N 100
int p[N], key[N], tb[N][N];
void prim(int v, int n)
{
int i, j;
int min;
for (i = 1; i <= n; i++)
{
p[i] = v;
key[i] = tb[v][i];
}
key[v] = 0;
for (i = 2; i <= n; i++)
{
min = INT_MAX;
for (j = 1; j <= n; j++)
if (key[j] > 0 && key[j] < min)
{
v = j;
min = key[j];
}
printf("%d%d ", p[v], v);
key[v] = 0;
for (j = 1; j <= n; j++)
if (tb[v][j] < key[j])
p[j] = v, key[j] = tb[v][j];
}
}
int main()
{
int n, m;
int i, j;
int u, v, w;
while (scanf("%d%d", &n, &m))
{
for(i = 1; i <= n; i++)
{
for (j = 1; j <= n; j++)
tb[i][j] = INT_MAX;
}
while (m--)
{
scanf("%d%d%d", &u, &v, &w);
tb[u][v] = tb[v][u] = w;
}
prim(1, n);
printf("\n");
}
return 0;
}
要求出所有的最小生成树。。貌似有点麻烦。。