Prim算法和Kruskal算法的Matlab实现

1.实验目的（结出本次实验所涉及并要求掌握的知识点）最小生成树kruskal算法和prim算法的实现2.实验内容（结出实验内容具体描述）最小生成树kruskal算法和prim算法的实现3.算法描述及实验步骤（用适当的形式表达算法设计思想与算法实现步骤）数据结构：（MST也是图，所以实现用了邻接表表示）void union_v(LinkGraph*g,int index,int j){edgenode*p=g->adjlist[index].firstedge;g->adjlist[index].state=j;while(p){if(g->adjlist[p->adjvex].state!=j)union_v(g,p->adjvex,j);p=p->next;}}//（加边）对边按权排升序，每次考虑最小边，判断他两端是否是不同集合，是就把这边unionedges* Kruskal_MST(LinkGraph*g,int c){edges*head=creatEdgeList(g);edges*p;edgenode*s;int i,j;//判断每一条边，是否需要unionprintf("排序后的边结点：\n");p=head->next;while(p){printf("%d %d %d",p->leftv,p->rightv,p->weigth);printf("\n");p=p->next;}p=head->next;for(i=0;i<g->n;i++){g->adjlist[i].state=i;// 初始化点集，每个点都位于不同的连通分量}while(p){if(g->adjlist[p->leftv].state!=g->adjlist[p->rightv].state){// 只要这条边可以加入MST，就创建图结点// 把这些边当成图结点，创建图（MST树）p->flag=1;i=p->leftv;j=p->rightv;s=(edgenode *)malloc(sizeof(edgenode));s->adjvex=j;s->weigth=p->weigth;s->next=g->adjlist[i].firstedge; // 头插法创建邻接表g->adjlist[i].firstedge=s;if (c==0) { // c=0表示无向图s=(edgenode *)malloc(sizeof(edgenode));s->adjvex=i;s->next=g->adjlist[j].firstedge;g->adjlist[j].firstedge=s;}// union操作int m=g->adjlist[i].state;int n=g->adjlist[j].state;if(m<n){g->adjlist[j].state=m;union_v(g,j,m);}else{g->adjlist[i].state=n;}}p=p->next;}// 返回边结点链表return head;}Prim算法的实现：edges* Prim_MST(LinkGraph*g,int c){edges*head=creatEdgeList(g);edges*p;edgenode*s;int i,j;printf("排序后的边结点：\n");p=head->next;while(p){printf("%d %d %d",p->leftv,p->rightv,p->weigth);printf("\n");p=p->next;}for(i=0;i<g->n;i++){g->adjlist[i].state=0;// 初始化点集，所有点未在MST中}//从head的第一条边的顶点出发，逐个寻找需要union的int count=0;//用来记录目前MST中有多少个点p=head->next;g->adjlist[p->leftv].state=1;//选中第一个点加入count++;int l,r;while(count!=g->n){p=head->next;while(p){l=g->adjlist[p->leftv].state;r=g->adjlist[p->rightv].state;// 只有l，r一个在点集，一个不在点集，才unionif(l+r == 1){if(l*r==0){p->flag=1;count++;// 建MST树/图j=p->rightv;s=(edgenode *)malloc(sizeof(edgenode));s->adjvex=j;s->weigth=p->weigth;s->next=g->adjlist[i].firstedge; // 头插法创建邻接表g->adjlist[i].firstedge=s;if (c==0) { // c=0表示无向图s=(edgenode *)malloc(sizeof(edgenode));s->adjvex=i;s->next=g->adjlist[j].firstedge;g->adjlist[j].firstedge=s;}// union操作if(l==0)g->adjlist[p->leftv].state=1;else if (r==0)g->adjlist[p->rightv].state=1;break;}else{p=p->next;}}else{p=p->next;}}}// 返回边结点链表return head;}4.调试过程及运行结果（详细记录在调试过程中出现的问题及解决方法。

MATLAB中常见的图论算法介绍一、引言图是计算机科学中非常重要的一种数据结构，广泛应用于各个领域。

图论算法能够解决多种问题，如网络分析、社交网络分析、路径规划等。

在本篇文章中，我们将介绍一些在MATLAB中常见的图论算法，帮助读者了解和应用这些算法。

二、图的表示方法在MATLAB中，图可以用邻接矩阵或邻接表来表示。

邻接矩阵是一个二维矩阵，其中行和列分别代表图的节点，矩阵中的元素表示节点之间的关系。

邻接表是一个包含图中所有节点的列表，每个节点链接到其相邻节点的列表。

三、最短路径算法1. Dijkstra算法Dijkstra算法用于解决单源最短路径问题，即寻找一个节点到图中其他所有节点的最短路径。

算法的基本思想是通过不断选择最短路径的节点来逐步扩展最短路径树。

在MATLAB中，可以使用graph对象和shortestpath函数来实现Dijkstra算法。

首先，使用graph对象创建图，然后使用shortestpath函数计算从源节点到目标节点的最短路径。

2. Bellman-Ford算法Bellman-Ford算法也用于解决单源最短路径问题，但相比Dijkstra算法，Bellman-Ford算法可以处理带有负权边的图。

算法的基本思想是通过松弛操作来逐步减小节点的估计距离，直到找到最短路径。

在MATLAB中，可以使用graph对象和shortestpath函数来实现Bellman-Ford算法。

与Dijkstra算法类似，首先使用graph对象创建图，然后使用shortestpath函数计算最短路径。

四、最小生成树算法1. Prim算法Prim算法用于寻找一个无向图的最小生成树。

算法的基本思想是从一个初始节点开始，逐步添加边，直到所有节点都被连接成一棵生成树。

在MATLAB中，可以使用graph对象和minspantree函数来实现Prim算法。

首先，使用graph对象创建图，然后使用minspantree函数计算最小生成树。

Kruskal算法和Prim算法本节所阐述的两种最小生成树算法是上节所介绍的一般算法的细化。

每个算法均采用一特定规则来确定GENERIC-MST算法第3行所描述的安全边；在Kruskal算法中，集合A是一森林，加大集合A中的安全边总是图中连结两不同连通支的最小权边。

在Prim算法中，集合A仅形成单棵树。

添加入集合A的安全边总是连结树与一非树结点的最小权边。

Kruskal算法Kruskal算法是直接基于上一节中给出的一般最小生成树算法的基础之上的。

该算法找出森林中连结任意两棵树的所有边中具有最小权值的边(u,v)作为安全边，并把它添加到正在生长的森林中。

设C1和C2表示边(u,v)连结的两棵树。

因为(u,v)必是连C1和其他某棵树的一条轻边，所以由推论2可知(u,v)对C1是安全边。

Kruskal算法同时也是一种贪心算法，因为算法每一步添加到森林中的边的权值都尽可能小。

Kruskal算法的实现类似于计算连通支的算法。

它使用了分离集合数据结构以保持数个互相分离的元素集合。

每一集合包含当前森林中某个树的结点，操作FIND-SET(u)返回包含u的集合的一个代表元素，因此我们可以通过FIND-SET(v)来确定两结点u和v是否属于同一棵树，通过操作UNION来完成树与树的联结。

MST-KRUSKAL(G,w)1. A←∅2. for 每个结点v V[G]3. do MAKE-SET(v)4. 根据权w的非递减顺序对E的边进行排序5. for 每条边(u,v)∈E，按权的非递减次序6. do if FIND-SET(u) ≠ FIND-SET(v)7. then A←A∪{(u,v)}8. UNION(u,v)9 return AKruskal算法的工作流程如图4所示。

阴影覆盖的边属于正在生成的森林A。

算法按权的大小顺序考察各边。

箭头指向算法每一步所考察到的边。

第1-3行初始化集合A为空集并建立|V|棵树，每裸树包含图的一个结点。

最⼩⽣成树问题---Prim算法与Kruskal算法实现（MATLAB语⾔实现） 2015-12-17晚，复习，甚是⽆聊，阅《复杂⽹络算法与应⽤》⼀书，得知最⼩⽣成树问题（Minimum spanning tree）问题。

记之。

何为树：连通且不含圈的图称为树。

图T=(V,E),|V|=n,|E|=m,下列关于树的说法等价：T是⼀个树。

T⽆圈，且m=n-1。

T连通，且m=n-1。

T⽆圈，但每加⼀新边记得到唯⼀⼀个圈。

T连通，但任舍去⼀边就不连通。

T中任意两点，有唯⼀道路相连。

何为⽣成树：若图G=(V,E)的⽣成⼦图是⼀棵树，则称该树为图G的⽣成树，也称⽀撑树，简称为图G的数。

图G中属于⽣成树的边称为数枝（Branch）。

何为最⼩⽣成树：连通图G=(V,E),每条边上有⾮负权L(e)。

⼀棵树上所有树枝权的总和，称为这个⽣成树的权。

具有最⼩权的⽣成树称为最⼩⽣成树，也就是说最⼩⽀撑树，简称最⼩树。

私以为，两种算法其实都是贪⼼，所以需要严格的证明。

由于最近时间零散、数学久置未学、对算法领域没有系统了解。

所以不进⾏深⼊探讨（也就是说证明），仅以⼀个简单实例做⼀个⼊门级的了解。

Prim算法： 给定连通赋权图G=(V,E,W)，其中W为邻接矩阵，设两个集合P和Q，其中P⽤于存放G的最⼩⽣成树中的节点，集合Q存放G的最⼩G的最⼩⽣成树中的边。

另集合P的初值为P={v1}(假设构造最⼩⽣成树时从v1出发)，集合Q的初值为P={空集}。

（1）P = {v1},Q = {空集}； （2）while P ~= Q 找到最⼩边pv,其中p∈P,v∈V-P; P = P + {v}; Q = Q + {pv}; end Kruskal算法 （1）选e1∈E(G)，使得w(e1) = min（选e1的权值最⼩）。

（2）e1,e2,...,e i已选好，则从E(G)-{e1,e2,...,e i}中选取e i+1,使得G[{e1,e2,...,e i,e i+1}]中⽆圈，且，w(e i+1) = min。

实现Prim算法和Kruskal 算法1、程序代码#include<stdio.h>#define TURE 999typedef struct ArcNode{char vexs[10];int edgs[10][10];int n,e;}MGraph;struct edg{int v1;int v2;int cost;}A[10],B[10];//创建图void GreateMGraph(MGraph *G){int i,j,k,weight,m,n;int ch1,ch2;char a,b;printf("\n输入顶点数和边数(用空格隔开):");scanf("%d %d",&(G->n),&(G->e)); //输入顶点数,边数for(i=0;i<G->n;i++){getchar();printf("\n请输入第%d个顶点:",i+1);scanf("%c",&(G->vexs[i])); //输入顶点}for(i=0;i<G->n;i++)for(j=0;j<G->n;j++)G->edgs[i][j]=0;for(k=0;k<G->e;k++){printf("\n请输入第%d条边的顶点权值(格式如:顶点1 顶点2 权值):",k+1);getchar();scanf("%c %c %d",&a,&b,&weight);m=0;n=0;for( m=0;G->vexs[m]!=a;m++);for( n=0;G->vexs[n]!=b;n++);ch1=m;ch2=n;G->edgs[ch1][ch2]=weight;G->edgs[ch2][ch1]=weight;}}void prim(MGraph *G, int v){int i,j,k,min;struct{ int adjvex;int lowcost;} closedge[10];for (i=0;i<G->n;i++) //初始化{closedge[i].lowcost=G->edgs[v][i];closedge[i].adjvex=v;}closedge[v].lowcost=TURE;for (i=1;i<G->n;i++){min=100; /* 100为允许的最大权值*/for(j=0;j<G->n;j++)if (closedge[j].lowcost!=TURE && closedge[j].lowcost!=0){if (closedge[j].lowcost<min){min=closedge[j].lowcost;k=j;}}printf("(%c,%c,%d) ", G->vexs[closedge[k].adjvex], G->vexs[k], min); closedge[k].lowcost=TURE;for (j=0;j<G->n;j++)if (closedge[j].lowcost!=TURE)if(G->edgs[k][j]<closedge[j].lowcost||closedge[j].lowcost==0 ){closedge[j].lowcost=G->edgs[k][j];closedge[j].adjvex=k;}}}void Kruskal(MGraph *G){int k=0,m=0,n=0;int vf1,vf2,min,vset[100];for(int i=0;i<G->n;i++)for(int j=0;j<G->n;j++)if(G->edgs[i][j]!=0){if(i<=j){A[k].v1=i;A[k].v2=j;A[k].cost=G->edgs[i][j];k++;}}n=0;while(m<=G->e-1){min=999;for(int i=n;i<k;i++)if(A[i].cost<min){B[n].v1=A[i].v1;B[n].v2=A[i].v2;B[n].cost=A[n].cost;min=A[i].cost;}n++;m++;}for(int i=0;i<G->n;i++){vset[i]=i;}k=0;while(k<=G->e){vf1=B[k].v1;vf2=B[k].v2;if(vset[vf1]!=vset[vf2]){printf("(%c,%c,%d)",G->vexs[B[k].v1],G->vexs[B[k].v2],B[k].cost);vset[vf2]=vset[vf1];}k++;}}int main(){MGraph *G,a;int choice;G=&a;GreateMGraph(G);while(1){printf("\n");printf("\n 1——prim算法 ");printf("\n 2——kruskal算法 ");printf("\n 请选择： ");scanf("%d",&choice);getchar();switch(choice){case 1: printf("\nprim算法输出为："); prim(G,0);break;case 2:printf("\nKruskal算法输出为："); Kruskal(G);break;default: break;}}return 0;}2、运行截图3、时间复杂度Prim算法：时间复杂度为O(n^2) Kruskal 算法：时间复杂度为为O(elog2e)。

图论算法matlab实现求最小费用最大流算法的 MATLAB 程序代码如下：n=5;C=[0 15 16 0 00 0 0 13 140 11 0 17 00 0 0 0 80 0 0 0 0]; %弧容量b=[0 4 1 0 00 0 0 6 10 2 0 3 00 0 0 0 20 0 0 0 0]; %弧上单位流量的费用wf=0;wf0=Inf; %wf 表示最大流量, wf0 表示预定的流量值for(i=1:n)for(j=1:n)f(i,j)=0;end;end %取初始可行流f 为零流while(1)for(i=1:n)for(j=1:n)if(j~=i)a(i,j)=Inf;end;end;end%构造有向赋权图for(i=1:n)for(j=1:n)if(C(i,j)>0&f(i,j)==0)a(i,j)=b(i,j); elseif(C(i,j)>0&f(i,j)==C(i,j))a(j,i)=-b(i,j);elseif(C(i,j)>0)a(i,j)=b(i,j);a(j,i)=-b(i,j);end;end;end for(i=2:n)p(i)=Inf;s(i)=i;end %用Ford 算法求最短路, 赋初值for(k=1:n)pd=1; %求有向赋权图中vs 到vt 的最短路for(i=2:n)for(j=1:n)if(p(i)>p(j)+a(j,i))p(i)=p(j)+a(j,i);s( i)=j;pd=0;end;end;endif(pd)break;end;end %求最短路的Ford 算法结束if(p(n)==Inf)break;end %不存在vs 到vt 的最短路, 算法终止. 注意在求最小费用最大流时构造有向赋权图中不会含负权回路, 所以不会出现k=ndvt=Inf;t=n; %进入调整过程, dvt 表示调整量while(1) %计算调整量if(a(s(t),t)>0)dvtt=C(s(t),t)-f(s(t),t); %前向弧调整量elseif(a(s(t),t)<0)dvtt=f(t,s(t));end %后向弧调整量if(dvt>dvtt)dvt=dvtt;endif(s(t)==1)break;end %当t 的标号为vs 时, 终止计算调整量t=s(t);end %继续调整前一段弧上的流fpd=0;if(wf+dvt>=wf0)dvt=wf0-wf;pd=1;end%如果最大流量大于或等于预定的流量值t=n;while(1) %调整过程if(a(s(t),t)>0)f(s(t),t)=f(s(t),t)+dvt; %前向弧调整elseif(a(s(t),t)<0)f(t,s(t))=f(t,s(t))-dvt;end %后向弧调整if(s(t)==1)break;end %当t 的标号为vs 时, 终止调整过程t=s(t);endif(pd)break;end%如果最大流量达到预定的流量值wf=0; for(j=1:n)wf=wf+f(1,j);end;end %计算最大流量zwf=0;for(i=1:n)for(j=1:n)zwf=zwf+b(i,j)*f(i,j);end;end%计算最小费用f %显示最小费用最大流图 6-22wf %显示最小费用最大流量zwf %显示最小费用, 程序结束__Kruskal 避圈法：Kruskal 避圈法的MATLAB 程序代码如下：n=8;A=[0 2 8 1 0 0 0 02 0 6 0 1 0 0 08 6 0 7 5 1 2 01 0 7 0 0 0 9 00 1 5 0 0 3 0 80 0 1 0 3 0 4 60 0 2 9 0 4 0 30 0 0 0 8 6 3 0];k=1; %记录A中不同正数的个数for(i=1:n-1)for(j=i+1:n) %此循环是查找A中所有不同的正数if(A(i,j)>0)x(k)=A(i,j); %数组x 记录A中不同的正数kk=1; %临时变量for(s=1:k-1)if(x(k)==x(s))kk=0;break;end;end %排除相同的正数k=k+kk;end;end;endk=k-1 %显示A中所有不同正数的个数for(i=1:k-1)for(j=i+1:k) %将x 中不同的正数从小到大排序if(x(j)<x(i))xx=x(j);x(j)=x(i);x(i)=xx;end;end;endT(n,n)=0; %将矩阵T 中所有的元素赋值为0q=0; %记录加入到树T 中的边数for(s=1:k)if(q==n)break;end %获得最小生成树T, 算法终止for(i=1:n-1)for(j=i+1:n)if(A(i,j)==x(s))T(i,j)=x(s);T(j,i)=x(s); %加入边到树T 中TT=T; %临时记录Twhile(1)pd=1; %砍掉TT 中所有的树枝for(y=1:n)kk=0;for(z=1:n)if(TT(y,z)>0)kk=kk+1;zz=z;end;end %寻找TT 中的树枝if(kk==1)TT(y,zz)=0;TT(zz,y)=0;pd=0;end;end %砍掉TT 中的树枝if(pd)break;end;end %已砍掉了TT 中所有的树枝pd=0; %判断TT 中是否有圈for(y=1:n-1)for(z=y+1:n)if(TT(y,z)>0)pd=1;break;end;end;end if(pd)T(i,j)=0;T(j,i)=0; %假如TT 中有圈else q=q+1;end;end;end;end;endT %显示近似最小生成树T, 程序结束用Warshall-Floyd 算法求任意两点间的最短路.n=8;A=[0 2 8 1 Inf Inf Inf Inf2 0 6 Inf 1 Inf Inf Inf8 6 0 7 5 1 2 Inf1 Inf 7 0 Inf Inf 9 Inf Inf 1 5 Inf 0 3 Inf 8 Inf Inf 1 Inf 3 0 4 6Inf Inf 2 9 Inf 4 0 3Inf Inf Inf Inf 8 6 3 0]; % MATLAB 中, Inf 表示∞D=A; %赋初值for(i=1:n)for(j=1:n)R(i,j)=j;end;end %赋路径初值for(k=1:n)for(i=1:n)for(j=1:n)if(D(i,k)+D(k,j)<D(i,j))D(i,j )=D(i,k)+D(k,j); %更新dijR(i,j)=k;end;end;end %更新rijk %显示迭代步数D %显示每步迭代后的路长R %显示每步迭代后的路径pd=0;for i=1:n %含有负权时if(D(i,i)<0)pd=1;break;end;end %存在一条含有顶点vi 的负回路if(pd)break;end %存在一条负回路, 终止程序end %程序结束利用 Ford--Fulkerson 标号法求最大流算法的MATLAB 程序代码如下：n=8;C=[0 5 4 3 0 0 0 00 0 0 0 5 3 0 00 0 0 0 0 3 2 00 0 0 0 0 0 2 00 0 0 0 0 0 0 40 0 0 0 0 0 0 30 0 0 0 0 0 0 50 0 0 0 0 0 0 0]; %弧容量for(i=1:n)for(j=1:n)f(i,j)=0;end;end %取初始可行流f 为零流for(i=1:n)No(i)=0;d(i)=0;end %No,d 记录标号图 6-19while(1)No(1)=n+1;d(1)=Inf; %给发点vs 标号while(1)pd=1; %标号过程for(i=1:n)if(No(i)) %选择一个已标号的点vifor(j=1:n)if(No(j)==0&f(i,j)<C(i,j)) %对于未给标号的点vj, 当vivj 为非饱和弧时No(j)=i;d(j)=C(i,j)-f(i,j);pd=0;if(d(j)>d(i))d(j)=d(i);endelseif(No(j)==0&f(j,i)>0) %对于未给标号的点vj, 当vjvi 为非零流弧时No(j)=-i;d(j)=f(j,i);pd=0;if(d(j)>d(i))d(j)=d(i);end;end;end;end;endif(No(n)|pd)break;end;end%若收点vt 得到标号或者无法标号, 终止标号过程if(pd)break;end %vt 未得到标号, f 已是最大流, 算法终止dvt=d(n);t=n; %进入调整过程, dvt 表示调整量while(1)if(No(t)>0)f(No(t),t)=f(No(t),t)+dvt; %前向弧调整elseif(No(t)<0)f(No(t),t)=f(No(t),t)-dvt;end %后向弧调整if(No(t)==1)for(i=1:n)No(i)=0;d(i)=0; end;break;end %当t 的标号为vs 时, 终止调整过程t=No(t);end;end; %继续调整前一段弧上的流fwf=0;for(j=1:n)wf=wf+f(1,j);end %计算最大流量f %显示最大流wf %显示最大流量No %显示标号, 由此可得最小割, 程序结束图论程序大全程序一：关联矩阵和邻接矩阵互换算法function W=incandadf(F,f)if f==0m=sum(sum(F))/2;n=size(F,1);W=zeros(n,m);k=1;for i=1:nfor j=i:nif F(i,j)~=0W(i,k)=1;W(j,k)=1;k=k+1;endendendelseif f==1m=size(F,2);n=size(F,1);W=zeros(n,n);for i=1:ma=find(F(:,i)~=0);W(a(1),a(2))=1;W(a(2),a(1))=1;endelsefprint('Please imput the right value of f');endW;程序二：可达矩阵算法function P=dgraf(A) n=size(A,1);P=A;for i=2:nP=P+A^i;endP(P~=0)=1;P;程序三：有向图关联矩阵和邻接矩阵互换算法function W=mattransf(F,f)if f==0m=sum(sum(F));n=size(F,1);W=zeros(n,m);k=1;for i=1:nfor j=i:nif F(i,j)~=0W(i,k)=1;W(j,k)=-1;k=k+1;endendendelseif f==1m=size(F,2);n=size(F,1);W=zeros(n,n);for i=1:ma=find(F(:,i)~=0);if F(a(1),i)==1W(a(1),a(2))=1;elseW(a(2),a(1))=1;endendelsefprint('Please imput the right value of f');endW;第二讲：最短路问题程序一：Dijkstra算法（计算两点间的最短路）function [l,z]=Dijkstra(W)n = size (W,1); for i = 1 :nl(i)=W(1,i);z(i)=0;endi=1;while i<=nfor j =1 :nif l(i)>l(j)+W(j,i)l(i)=l(j)+W(j,i);z(i)=j-1;if j<ii=j-1;endendendi=i+1;end程序二：floyd算法（计算任意两点间的最短距离）function [d,r]=floyd(a)n=size(a,1);d=a;for i=1:nfor j=1:nr(i,j)=j;endendr;for k=1:nfor i=1:nfor j=1:nif d(i,k)+d(k,j)<d(i,j)d(i,j)=d(i,k)+d(k,j);r(i,j)=r(i,k);endendendend程序三：n2short.m 计算指定两点间的最短距离function [P u]=n2short(W,k1,k2)n=length(W);U=W;m=1;while m<=nfor i=1:nfor j=1:nif U(i,j)>U(i,m)+U(m,j)U(i,j)=U(i,m)+U(m,j);endendendm=m+1;endu=U(k1,k2);P1=zeros(1,n);k=1;P1(k)=k2;V=ones(1,n)*inf;kk=k2;while kk~=k1for i=1:nV(1,i)=U(k1,kk)-W(i,kk);if V(1,i)==U(k1,i)P1(k+1)=i;kk=i;k=k+1;endendendk=1;wrow=find(P1~=0);for j=length(wrow):-1:1P(k)=P1(wrow(j));k=k+1;endP;程序四、n1short.m(计算某点到其它所有点的最短距离)function[Pm D]=n1short(W,k)n=size(W,1);D=zeros(1,n);for i=1:n[P d]=n2short(W,k,i);Pm{i}=P;D(i)=d;end程序五：pass2short.m(计算经过某两点的最短距离)function [P d]=pass2short(W,k1,k2,t1,t2)[p1 d1]=n2short(W,k1,t1);[p2 d2]=n2short(W,t1,t2);[p3 d3]=n2short(W,t2,k2);dt1=d1+d2+d3;[p4 d4]=n2short(W,k1,t2);[p5 d5]=n2short(W,t2,t1);[p6 d6]=n2short(W,t1,k2);dt2=d4+d5+d6;if dt1<dt2d=dt1;P=[p1 p2(2:length(p2)) p3(2:length(p3))];elsed=dt1;p=[p4 p5(2:length(p5)) p6(2:length(p6))];endP;d;第三讲：最小生成树程序一：最小生成树的Kruskal算法function [T c]=krusf(d,flag)if nargin==1n=size(d,2);m=sum(sum(d~=0))/2;b=zeros(3,m);k=1;for i=1:nfor j=(i+1):nif d(i,j)~=0b(1,k)=i;b(2,k)=j;b(3,k)=d(i,j);k=k+1;endendendelseb=d;endn=max(max(b(1:2,:)));m=size(b,2);[B,i]=sortrows(b',3);B=B';c=0;T=[];k=1;t=1:n;for i=1:mif t(B(1,i))~=t(B(2,i))T(1:2,k)=B(1:2,i);c=c+B(3,i);k=k+1;tmin=min(t(B(1,i)),t(B(2,i)));tmax=max(t(B(1,i)),t(B(2,i)));for j=1:nif t(j)==tmaxt(j)=tmin;endendendif k==nbreak;endendT;c;程序二：最小生成树的Prim算法function [T c]=Primf(a)l=length(a);a(a==0)=inf;k=1:l;listV(k)=0;listV(1)=1;e=1;while (e<l)min=inf;for i=1:lif listV(i)==1for j=1:lif listV(j)==0 & min>a(i,j)min=a(i,j);b=a(i,j);s=i;d=j;endendendendlistV(d)=1;distance(e)=b;source(e)=s;destination(e)=d;e=e+1;endT=[source;destination]; for g=1:e-1c(g)=a(T(1,g),T(2,g));endc;另外两种程序最小生成树程序1（prim 算法构造最小生成树）a=[inf 50 60 inf inf inf inf;50 inf inf 65 40 inf inf;60 inf inf 52 inf inf 45;...inf 65 52 inf 50 30 42;inf 40 inf 50 inf 70 inf;inf inf inf 30 70 inf inf;...inf inf 45 42 inf inf inf];result=[];p=1;tb=2:length(a);while length(result)~=length(a)-1temp=a(p,tb);temp=temp(:);d=min(temp);[jb,kb]=find(a(p,tb)==d);j=p(jb(1));k=tb(kb(1));result=[result,[j;k;d]];p=[p,k];tb(find(tb==k))=[];endresult最小生成树程序2（Kruskal 算法构造最小生成树）clc;clear;a(1,2)=50; a(1,3)=60; a(2,4)=65; a(2,5)=40;a(3,4)=52;a(3,7)=45; a(4,5)=50; a(4,6)=30;a(4,7)=42; a(5,6)=70;[i,j,b]=find(a);data=[i';j';b'];index=data(1:2,:);loop=max(size(a))-1;result=[];while length(result)<looptemp=min(data(3,:));flag=find(data(3,:)==temp);flag=flag(1);v1=data(1,flag);v2=data(2,flag);if index(1,flag)~=index(2,flag)result=[result,data(:,flag)];endindex(find(index==v2))=v1;data(:,flag)=[];index(:,flag)=[];endresult第四讲：Euler图和Hamilton图程序一：Fleury算法（在一个Euler图中找出Euler环游）注：包括三个文件；fleuf1.m, edf.m, flecvexf.mfunction [T c]=fleuf1(d)%注：必须保证是Euler环游，否则输出T=0,c=0 n=length(d);b=d;b(b==inf)=0;b(b~=0)=1;m=0;a=sum(b);eds=sum(a)/2;ed=zeros(2,eds);vexs=zeros(1,eds+1);matr=b;for i=1:nif mod(a(i),2)==1m=m+1;endendif m~=0fprintf('there is not exit Euler path.\n')T=0;c=0;endif m==0vet=1;flag=0;t1=find(matr(vet,:)==1);for ii=1:length(t1)ed(:,1)=[vet,t1(ii)];vexs(1,1)=vet;vexs(1,2)=t1(ii);matr(vexs(1,2),vexs(1,1))=0;flagg=1;tem=1;while flagg[flagg ed]=edf(matr,eds,vexs,ed,tem); tem=tem+1;if ed(1,eds)~=0 & ed(2,eds)~=0T=ed;T(2,eds)=1;c=0;for g=1:edsc=c+d(T(1,g),T(2,g));endflagg=0;break;endendendendfunction[flag ed]=edf(matr,eds,vexs,ed,tem)flag=1;for i=2:eds[dvex f]=flecvexf(matr,i,vexs,eds,ed,tem);if f==1flag=0;break;endif dvex~=0ed(:,i)=[vexs(1,i) dvex];vexs(1,i+1)=dvex;matr(vexs(1,i+1),vexs(1,i))=0;elsebreak;endendfunction [dvex f]=flecvexf(matr,i,vexs,eds,ed,temp) f=0;edd=find(matr(vexs(1,i),:)==1);dvex=0;dvex1=[];ded=[];if length(edd)==1dvex=edd;elsedd=1;dd1=0;kkk=0;for kk=1:length(edd)m1=find(vexs==edd(kk));if sum(m1)==0dvex1(dd)=edd(kk);dd=dd+1;dd1=1;elsekkk=kkk+1;endendif kkk==length(edd)tem=vexs(1,i)*ones(1,kkk);edd1=[tem;edd];for l1=1:kkklt=0;ddd=1;for l2=1:edsif edd1(1:2,l1)==ed(1:2,l2)lt=lt+1;endendif lt==0ded(ddd)=edd(l1); ddd=ddd+1;endendendif temp<=length(dvex1)dvex=dvex1(temp);elseif temp>length(dvex1) & temp<=length(ded)dvex=ded(temp);elsef=1;endend程序二：Hamilton改良圈算法（找出比较好的Hamilton路）function [C d1]= hamiltonglf(v)%d表示权值矩阵%C表示算法最终找到的Hamilton圈。

最⼩⽣成树---普⾥姆算法（Prim算法）和克鲁斯卡尔算法（Kruskal算法）最⼩⽣成树的性质：MST性质（假设N=(V,{E})是⼀个连通⽹，U是顶点集V的⼀个⾮空⼦集，如果（u，v）是⼀条具有最⼩权值的边，其中u属于U，v属于V-U，则必定存在⼀颗包含边（u，v）的最⼩⽣成树）普⾥姆算法（Prim算法)思路：以点为⽬标构建最⼩⽣成树1.将初始点顶点u加⼊U中，初始化集合V-U中各顶点到初始顶点u的权值；2.根据最⼩⽣成树的定义：从n个顶点中，找出 n - 1条连线，使得各边权值最⼩。

循环n-1次如下操作：（1）从数组lowcost[k]中找到vk到集合U的最⼩权值边，并从数组arjvex[k] = j中找到该边在集合U中的顶点下标(2)打印此边，并将vk加⼊U中。

（3）通过查找邻接矩阵Vk⾏的各个权值，即vk点到V-U中各顶点的权值，与lowcost的对应值进⾏⽐较，若更⼩则更新lowcost，并将k存⼊arjvex数组中以下图为例#include<bits/stdc++.h>using namespace std;#define MAXVEX 100#define INF 65535typedef char VertexType;typedef int EdgeType;typedef struct {VertexType vexs[MAXVEX];EdgeType arc[MAXVEX][MAXVEX];int numVertexes, numEdges;}MGraph;void CreateMGraph(MGraph *G) {int m, n, w; //vm-vn的权重wscanf("%d %d", &G->numVertexes, &G->numEdges);for(int i = 0; i < G->numVertexes; i++) {getchar();scanf("%c", &G->vexs[i]);}for(int i = 0; i < G->numVertexes; i++) {for(int j = 0; j < G->numVertexes; j++) {if(i == j) G->arc[i][j] = 0;else G->arc[i][j] = INF;}}for(int k = 0; k < G->numEdges; k++) {scanf("%d %d %d", &m, &n, &w);G->arc[m][n] = w;G->arc[n][m] = G->arc[m][n];}}void MiniSpanTree_Prim(MGraph G) {int min, j, k;int arjvex[MAXVEX]; //最⼩边在 U集合中的那个顶点的下标int lowcost[MAXVEX]; // 最⼩边上的权值//初始化,从点 V0开始找最⼩⽣成树Tarjvex[0] = 0; //arjvex[i] = j表⽰ V-U中集合中的 Vi点的最⼩边在U集合中的点为 Vjlowcost[0] = 0; //lowcost[i] = 0表⽰将点Vi纳⼊集合 U ，lowcost[i] = w表⽰ V-U中 Vi点到 U的最⼩权值for(int i = 1; i < G.numVertexes; i++) {lowcost[i] = G.arc[0][i];arjvex[i] = 0;}//根据最⼩⽣成树的定义：从n个顶点中，找出 n - 1条连线，使得各边权值最⼩for(int i = 1; i < G.numVertexes; i++) {min = INF, j = 1, k = 0;//寻找 V-U到 U的最⼩权值minfor(j; j < G.numVertexes; j++) {// lowcost[j] != 0保证顶点在 V-U中，⽤k记录此时的最⼩权值边在 V-U中顶点的下标if(lowcost[j] != 0 && lowcost[j] < min) {min = lowcost[j];k = j;}}}printf("V[%d]-V[%d] weight = %d\n", arjvex[k], k, min);lowcost[k] = 0; //表⽰将Vk纳⼊ U//查找邻接矩阵Vk⾏的各个权值，与lowcost的对应值进⾏⽐较，若更⼩则更新lowcost，并将k存⼊arjvex数组中for(int i = 1; i < G.numVertexes; i++) {if(lowcost[i] != 0 && G.arc[k][i] < lowcost[i]) {lowcost[i] = G.arc[k][i];arjvex[i] = k;}}}int main() {MGraph *G = (MGraph *)malloc(sizeof(MGraph));CreateMGraph(G);MiniSpanTree_Prim(*G);}/*input:4 5abcd0 1 20 2 20 3 71 2 42 3 8output:V[0]-V[1] weight = 2V[0]-V[2] weight = 2V[0]-V[3] weight = 7最⼩总权值: 11*/时间复杂度O(n^2)克鲁斯卡尔算法（Kruskal算法）思路：以边为⽬标进⾏构建最⼩⽣成树在边集中依次寻找最⼩权值边，若构建是不形成环路（利⽤parent数组记录各点的连通分量），则将其添加到最⼩⽣成树中。

适用标准文档《计算机仿真》期末大作业Prim 算法和 Kruskal 算法的 Matlab 实现05605 刘禹 050697（30）连线问题应用举例：欲铺设连结 n 个城市的高速公路，若i 城与 j 城之间的高速公路造价为C ij，试设计一个线路图，使总的造价最低。

连线问题的数学模型就是图论中在连通的赋权图上求权最小的支撑树。

试用 Matlab 分别实现求最小支撑数的Prim 算法和 Krusal算法（避圈法）。

一.基本要求：（1）画出程序流程图；（2）对重点算法、变量和步骤进行解说说明；（3）用以下两图对所写算法的正确性进行考证。

即输入图的信息，输出对应图的最小支撑树及其权值。

v 26v 79 224311834214622v 316 3011 419155v 1v 664352016v 45v 57448（4）剖析两种算法的实现复杂度。

二.扩展要求：（1）供给对算法效率（复杂度）进行评估的方法，并经过举例考证，与剖析获得的算法复杂度结果相比较；（2）从降低内存耗费、减少计算时间的角度，对算法进行优化。

三．实验步骤I.用 Prim 算法求最小生成树i．算法剖析及需求剖析，程序设计prim 算法的基本思想是：设G=（V， E）是一个无向连通网，令T=（ U， TE）是 G的最小生成树。

T 的初始状态为U={v0} （ v0）TE={}，而后重复履行下述操作：在全部u U，v V-U 的边中找一条代价最小的边（u，v）并入会合TE，同时 v 并入 U，直至 U=V为止。

明显， Prim 算法的基本思想是以局部最优化谋求全局的最优化，并且，还波及到开端结点的问题。

本程序达成的功能是：从图中的随意结点出发，都能够找出最小生成树实现方案剖析：Prim 算法的重点是怎样找到连结U 和 V-U 的最短边来扩大生成树T。

设目前T 中有 k 个点（即T 的极点集U 中有 k 个极点）则全部知足u U， v V-U 的边最多有k条，从这样大的边集中选用最短边是不太经济的。