本文目录
求最小生成树 利用Kruskal算法求图G的一棵最小生成树T，用c语言
#include 《cstdlib》#include 《iostream》#include 《queue》using namespace std;///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// Description: 并查集存储结构// Tags: 值为-1则表示为根节点struct DisjointSet{int *arr;// 值为父节点下标int number;// arr元素个数};///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// Description: 初始化并查集结构// Input: number - 元素的个数// Output:s - number个元素自成一集的并查集void InitSet(DisjointSet &s, int number){s.number = number;s.arr = new int;memset(s.arr, -1, sizeof(int) * number);}///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// Description: 删除并查集结构// Input: s - 并查集存储结构// Output:s - 回收内存后的结构void FreeSet(DisjointSet &s){if (s.arr){delete s.arr;s.number = 0;}}///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// Description: 获得某个结点的根节点// Input: s - 并查集; index - 结点下标// Output: return - 根节点下标 int GetRoot(DisjointSet &s, int index){while (s.arr != -1)index = s.arr;return index;}///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// Description: 合并index1和index2所在的两个集合// Input: index1 - 结点1下标, index2 - 结点2下标// Output: s - 并查集void Union(DisjointSet &s, int index1, int index2){int root1 = GetRoot(s, index1);int root2 = GetRoot(s, index2);s.arr = root2;}///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// Description: 判断两个结点是否在同一个集合中// Input: s - 并查集, index1 - 结点1下标, index2 - 结点2下标// Output: return - true: 在 false: 不在bool Find(DisjointSet &s, int index1, int index2){return GetRoot(s, index1) == GetRoot(s, index2);}///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// Description: 图的邻接矩阵struct Graph{int **value;// 权值,-1表示无法到达int number;};///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// Description: 初始化一个图// Input: g - 图的存储结构, number - 结点个数// Output: g - 图void InitGraph(Graph &g, int number){int i = 0;g.value = new int *;for (i = 0; i 《 number; i++)g.value; g.number = number;memset(*g.value, -1, sizeof(int) * number * number);}///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// Description: 回收一个图// Input: g - 图, number - 结点个数// Output: g - 图的存储结构void FreeGraph(Graph &g){int i = 0;for (i = 0; i 《 g.number; i++)delete ;delete g.value;g.value = 0;g.number = 0;}///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// Description: 为图在a，b间添加一条边// Input:e1, e2 - 两个结点, value - 权值// Output: graph - 加边后的图void AddEdge(Graph &graph, int e1, int e2, int value){graph.value =value;graph.value = value;}///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// Description: 显示一条边struct OneEdge{OneEdge(int _a = 0, int _b = 0, int _value = 0):a(_a), b(_b), value(_value){}int a, b;// 边的两个结点int value;// 边的权值};///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// Description: 根据权值判断两个边的大小// Tags: 由于priority_queue是最大堆，所以这里小于号变成大于号，从而使priority_queue变成最小堆bool operator 《(OneEdge e1, OneEdge e2){if (e1.value 》 e2.value) return true;else return false;}///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// Description: 用户输入图的边// Input: n - 加边的个数// Output: graph - 加边后的图// Tags: Console下用户输入点对(a, b, v)void InputEdge(Graph &graph, int n){int i = 0, a, b, v;for (i = 0; i 《 n; i++){scanf("%d %d %d", &a, &b, &v);AddEdge(graph, a, b, v);}}int main(){const int NODE_NUMBER = 6;const int EDGE_NUMBER = 9;Graph graph;// 图DisjointSet set;// 并查集priority_queue《OneEdge》 edge;// 2叉堆InitGraph(graph, NODE_NUMBER);// 初始化图InputEdge(graph, EDGE_NUMBER);InitSet(set, NODE_NUMBER);// 初始化并查集 int i = 0, j = 0;// 初始化堆for (i = 0; i 《 NODE_NUMBER; i++)for (j = i; j 《 NODE_NUMBER; j++)if (graph.value 》 0)edge.push(OneEdge(i, j, graph.value));int min_pay = 0;// 最小耗费值int add_num = 0;// 已经添加了几个边OneEdge min_value_edge;// 当前权值最小边while (add_num 《 NODE_NUMBER - 1){min_value_edge = edge.top();// 这里是因为了STL中2叉堆的结构中有一个缓冲区// 需要将缓冲区中的每一个元素弹出来if(min_value_edge.value 》 0 && !Find(set, min_value_edge.a, min_value_edge.b)){Union(set, min_value_edge.a, min_value_edge.b);min_pay += min_value_edge.value;add_num++;}edge.pop();}printf("%d", min_pay);return 0;}这个是c++语言的，最小权值存储在min_pay中，树存储在并查集set中，且在获取最小权值路径的时候用了STL中的2叉堆，算法复杂度为O(|V| * lgE)不知是否满足您的要求
最小生成树怎么求
一个有 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的某棵MSTT〈-￠； //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算法procedure prim(v0:integer);varlowcost,closest:array of integer;i,j,k,min:integer;beginfor i:=1 to n do beginlowcost;closest:=v0;end;for i:=1 to n-1 do begin{寻找离生成树最近的未加入顶点 k}min:=maxlongint;for j:=1 to n doif (lowcost《》0) then beginmin:=lowcost;k:=j;end;lowcost:=0; {将顶点k 加入生成树}{生成树中增加一条新的边 k 到 closest}{修正各点的 lowcost 和 closest 值}for j:=1 to n doif cost then beginlowcost;closest:=k;end;end;end;Kruskal算法按权值递增顺序删去图中的边，若不形成回路则将此边加入最小生成树。function find(v:integer):integer; {返回顶点 v 所在的集合}var i:integer;begini:=1;while (i《=n) and (not v in vset) do inc(i);if i《=n then find:=i else find:=0;end;procedure kruskal;vartot,i,j:integer;beginfor 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 begini:=find(e.v2）;if i《》j then begininc(tot,e.len);vset:=vset+vset;dec(p);end;inc(q);end;writeln(tot);end;C语言代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185#include《stdio.h》#include《stdlib.h》#include《iostream.h》#defineMAX_VERTEX_NUM20#defineOK1#defineERROR0#defineMAX1000typedefstructArcell{doubleadj;}Arcell,AdjMatrix;typedefstruct{charvexs;//节点数组AdjMatrixarcs;//邻接矩阵intvexnum,arcnum;//图的当前节点数和弧数}MGraph;typedefstructPnode//用于普利姆算法{charadjvex;//节点doublelowcost;//权值}Pnode,Closedge;//记录顶点集U到V-U的代价最小的边的辅助数组定义typedefstructKnode//用于克鲁斯卡尔算法中存储一条边及其对应的2个节点{charch1;//节点1charch3;//节点2doublevalue;//权值}Knode,Dgevalue; //-------------------------------------------------------------------------------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;for(i=0;i《G.vexnum;++i)//初始化数组{for(j=0;j《G.vexnum;++j){G.arcs.adj=MAX;}}cout《《"请输入一条边依附的定点及边的权值："《《endl;for(k=0;k《G.arcnum;++k){cin》》dgevalue.value;i=LocateVex(G,dgevalue.ch1）;j=LocateVex(G,dgevalue.ch3）;G.arcs.value;G.arcs.adj;}returnOK;}intLocateVex(MGraphG,charch)//确定节点ch在图G.vexs中的位置{inta;for(inti=0;i《G.vexnum;i++){if(G.vexs==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.adjvex=u;closedge.adj;}}closedge.lowcost=0;for(i=1;i《G.vexnum;i++){k=Minimum(G,closedge);cout《《"("《《closedge.lowcost《《")"《《endl;closedge.lowcost=0;for(j=0;j《G.vexnum;++j){if(G.arcs.lowcost){closedge;closedge.adj;}}}}intMinimum(MGraphG,Closedgeclosedge)//求closedge中权值最小的边，并返回其顶点在vexs中的位置{inti,j;doublek=1000;for(i=0;i《G.vexnum;i++){if(closedge.lowcost《k){k=closedge.lowcost;j=i;}}returnj;}voidMiniSpanTree_KRSL(MGraphG,Dgevalue&dgevalue)//克鲁斯卡尔算法求最小生成树{intp1,p2,i,j;intbj;//标记数组for(i=0;i《G.vexnum;i++)//标记数组初始化bj=i;Sortdge(dgevalue,G);//将所有权值按从小到大排序for(i=0;i《G.arcnum;i++){p1=bj;p2=bj;if(p1!=p2）{cout《《"("《《dgevalue.value《《")"《《endl;for(j=0;j《G.vexnum;j++){if(bj==p2）bj=p1;}}}}voidSortdge(Dgevalue&dgevalue,MGraphG)//对dgevalue中各元素按权值按从小到大排序{inti,j;doubletemp;charch1,ch3;for(i=0;i《G.arcnum;i++){for(j=i;j《G.arcnum;j++){if(dgevalue.value){temp=dgevalue.value;dgevalue.value;dgevalue.value=temp;ch1=dgevalue.ch1;dgevalue.ch1;dgevalue.ch1=ch1;ch3=dgevalue.ch3;dgevalue.ch3;dgevalue.ch3=ch3;}}}}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.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;vara:array of records,t,len:longint;end;fa,r:array of longint;n,i,j,x,y,z:longint;tot,ans:longint;count,xx:longint;procedure quick(l,r:longint);vari,j,x,y,t:longint;begini:=l;j:=r;x:=a.len;repeatwhile x》a.len do inc(i);while x《a.len do dec(j);if i《=j thenbeginy:=a.len:=y;y:=a.s:=y;y:=a.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;beginif fa);find:=fa;end;procedure union(x,y:longint);{启发式合并}vart:longint;beginx:=find(x);y:=find(y);if r thenbegint:=x;x:=y;y:=t;end;if r);fa:=y;end;beginreadln(xx,n);for i:=1 to xx do fa:=i;for i:=1 to n dobeginread(x,y,z);inc(tot);a.s:=x;a.t:=y;a.len:=z;end;quick（1,tot);{将边排序}ans:=0;count:=0;i:=0;while count《=x-1 do{count记录加边的总数}begininc(i);with a doif find(s)《find(t) thenbeginunion(s,t);ans:=ans+len;inc(count);end;end;write(ans);end.Primvarm,n:set of 1..100;s,t,min,x,y,i,j,k,l,sum,p,ii:longint;a:arrayof longint;beginreadln(p);for ii:=1 to p dobegink:=0; sum:=0;fillchar(a,sizeof(a),255);readln(x);m:=;n:=;for i:=1 to x dobeginfor j:=1 to x dobeginread(a);if a=0then a:=maxlongint;end;readln;end;for l:=1 to x-1 dobeginmin:=maxlongint;for i:=1 to x doif i in mthen beginfor j:=1 to x dobeginif (a《min)and(j in n)then beginmin:=a;s:=i;t:=j;end;end;end;sum:=sum+min;m:=m+;n:=n-;inc(k);end;writeln(sum);end;end.
