九乡新闻网陈大惠的传统文化:最小生成树
来源：百度文库 编辑：九乡新闻网 时间：2024/05/09 20:03:06
求最小生成树的具体算法(pascal): A.Prim算法： procedure 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:=v0; end; for i:=1 to n-1 do begin {寻找离生成树最近的未加入顶点 k} min:=maxlongint; for j:=1 to n do if (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]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语言完整代码如下（已编译通过）： #include #include #include #define MAX_VERTEX_NUM 20 #define OK 1 #define ERROR 0 #define MAX 1000 typedef struct Arcell { double adj; }Arcell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct { char vexs[MAX_VERTEX_NUM]; //节点数组 AdjMatrix arcs; //邻接矩阵 int vexnum,arcnum; //图的当前节点数和弧数 }MGraph; typedef struct Pnode //用于普利姆算法 { char adjvex; //节点 double lowcost; //权值 }Pnode,Closedge[MAX_VERTEX_NUM]; //记录顶点集U到V-U的代价最小的边的辅助数组定义 typedef struct Knode //用于克鲁斯卡尔算法中存储一条边及其对应的2个节点 { char ch1; //节点1 char ch2; //节点2 double value; //权值 }Knode,Dgevalue[MAX_VERTEX_NUM]; //----------------------------------------------------------------------------------- int CreateUDG(MGraph & G,Dgevalue & dgevalue); int LocateVex(MGraph G,char ch); int Minimum(MGraph G,Closedge closedge); void MiniSpanTree_PRIM(MGraph G,char u); void Sortdge(Dgevalue & dgevalue,MGraph G); //----------------------------------------------------------------------------------- int CreateUDG(MGraph & G,Dgevalue & dgevalue) //构造无向加权图的邻接矩阵 { int i,j,k; cout<<"请输入图中节点个数和边/弧的条数:"; cin>>G.vexnum>>G.arcnum; cout<<"请输入节点:"; for(i=0;i>G.vexs[i]; for(i=0;i> 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; } return OK; } int LocateVex(MGraph G,char ch) //确定节点ch在图G.vexs中的位置 { int a ; for(int i=0; i 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; } } } } void main() { int i,j; MGraph G; char u; Dgevalue dgevalue; CreateUDG(G,dgevalue); cout<<"图的邻接矩阵为:"<>u; cout<<"构成最小代价生成树的边集为:\n"; MiniSpanTree_PRIM(G,u); cout<<"============克鲁斯科尔算法=============\n"; cout<<"构成最小代价生成树的边集为:\n"; MiniSpanTree_KRSL(G,dgevalue); }