Prim 算法和Kruskal 算法的Matlab 实现连线问题应用举例：欲铺设连接n 个城市的高速公路，若i 城与j 城之间的高速公路造价为ij C ，试设计一个线路图，使总的造价最低。
连线问题的数学模型就是图论中在连通的赋权图上求权最小的支撑树。
试用Matlab 分别实现求最小支撑数的Prim 算法和Krusal 算法（避圈法）。
一.基本要求：（1） 画出程序流程图；（2） 对关键算法、变量和步骤进行解释说明；（3） 用如下两图对所写算法的正确性进行验证。
即输入图的信息，输出对应图的最小支撑树及其权值。
v 1v 745v216196611218302051514924167534844（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条，从如此大的边集中选取最短边是不太经济的。
利用MST性质，可以用下述方法构造候选最小边集：对应V-U中的每个顶点，保留从该顶点到U中的各顶点的最短边，取候选边最短边集为V-U中的n-k个顶点所关联的n-k条最短边的集合。
为表示候选最短边集，需设置两个一维数组lowcost[n]和adjvex[n],其中lowcost用来保存集合V-U中的各顶点与集合U中顶点的最短边的权值，lowcost[v]=0表示顶点v已经加入最小生成树中；adjvex用来保存依附于该边在集合U中的顶点。
例如下式表明顶点和顶点之间的权值为w lowcost[i]=w;adjvex[i]=k;程序流程图关键代码说明：1．将用于验证算法正确性的两幅图用邻接矩阵的形式保存，分别保存为文件Graph1.m,Graph2.m（注：矩阵的对角线元素设置为零。
）并在主程序finallyprim中直接进行调用。
2．在输入起点时应该给程序的阅读者就该图的顶点数作出提示，不然的话使用者很可能会输入越界下标。
采取的方法如下len=length(graph_adjacent);%求图中有多少个顶点k=sprintf('please input the point where you want to start ,do remember it must bebetween 1 and %d ',len);start_point=input(k);%输入最小生成树产生起点采取了sprintf格式化字符串的方法，就避免了编程的人每次根据输入图的顶点数手动对提示作修改。
效果如下：在对第一幅图进行算法验证时在workspace会如下输出:please input the point where you want to start ,do remember it must be between 1and 7在对第二幅图进行算法验证时在workspace会有如下输出：please input the point where you want to start ,do remember it must be between 1and 83．在输出结果时为了使结果在workspace中输出的清晰，使人一目了然，也使用了sprintf格式化字符串的方法，代码如下s=0;for ii=1:len-1k=sprintf('最小生成树第%d条边：（%d,%d），权值为%d',ii,tree(ii,1),tree(ii,2),graph_adjacent(tree(ii,1),tree(ii,2)));disp(k);disp(' ');s=s+graph_adjacent(tree(ii,1),tree(ii,2));enddisp('最小生成树的总代价为：')disp(s);4．下面对算法的核心部分进行说明：在len-1次循环中，每次循环要完成以下三项工作1.找到最小边，（需要求lowcost数组的最小非零值，因为0表示该边已经被加入到了最小生成树中）由于是求非零的最小值，就不能在直接用min函数了。
我采取的方法是这样的：k=lowcost>0;%k为一逻辑数组，它和lowcost同维，对于每一个位% 置i如果lowcost(i)>0则k(i)=1%否则k(i)=0;稍候将用这个数组进行辅助寻址cost_min=min(lowcost(k));%找出lowcost中除0外的最小值index=find(lowcost==cost_min);%找出此最小值在lowcost中的下标，即找到相应的节点index=index(1);%因为最小值的下标可能不止一个，这里取第一个下标进行处理lowcost(index)=0;%表明该节点已经加入了最小生成树中采用这种方法不仅充分利用了matlab的built_in函数，还避免了自己编写代码（循环+判断lowcost[v]是否为0）来实现寻找不为零的最小值的麻烦，提高了代码执行的效率。
2.对lowcost和adjvex进行更新，即：设刚加入最小生成树的顶点为index，比较对于U-V中的每个顶点v:比较lowcost(v)和（v，index）边的权值大小，如果（v，index）边的权值小，则令lowcost(v)的值为该边的权值，并将adjvex(v)的值等于indexfor j=1:lenif lowcost(j)>graph_adjacent(j,index);lowcost(j)=graph_adjacent(j,index);adjvex(j)=index;endend3.将该边保存tree(i,:)=[adjvex(index),index];ii.结果如下求第一张图的最小生成树：求第二张图的最小生成树：II .用Krusal算法（避圈法）求最小生成树i．算法分析及需求分析，程序设计Kruskal算法的基本思想是：设无向连通网为G=（V，E），令G的最小生成树为T=（U，TE），其初始状态为U=V，TE={},这样T中各顶点各自构成一个连通分量。
然后按照边的权值由小到大的顺序，依次考察边集E中的各条边。
若被考察的边的两个顶点属于T的两个不同的连通分量，则将此边加入到TE中去，同时把两个连通分量连接成一个连通分量；若被考察边的两个结点属于同一个连通分量，则舍去此边，以免造成回路，如此下去，当T 中的连通分量个数为1时，此连通分量便为G的一棵最小生成树。
显然，Kruskal算法实现起来要比prim算法复杂些。
选择合适的存储结构存储图，采用合适的排序算法对程序执行效率的提高非常重要，采用简单而明了的方法判断边的两个端点是否在一个连通分支上更是尤为重要。
一般来说，涉及Kruskal算法多采取边集数组做为图的存储结构，但考虑到matlab不像C语言那样可以方便地动态的生成数组和释放内存，仍采取了邻接矩阵的形式保存图，用于测试的两幅图，分别保存为Graph11.M,Graph22.M.（注：邻接矩阵的对角线元素设定为100）这样既方便对边进行操作，又方便对边的顶点进行操作。
使用邻接矩阵容易引起的问题是：由于邻接矩阵是对称矩阵，比如graph_adjacent(1,2)和graph_adjacent(2,1)代表的是同一条边，所以当有一条边被选入最小生成树后，要对它的两个结点分别进行更新。
整个程序是以顶点为基本单位处理的。
由于一条边对应两个结点，取标号较小的顶点做为主要处理对象，并用它来寻址该边所对应的另一个结点。
这样规格化的好处在于：程序流程的每一步都会在自己的预测中，出现了错误易于查找。
下面介绍一下一个matlab的built_in排序函数sort这个函数的功能非常强，也正因为采用了这个函数才使我的程序简洁高效。
[Y，I]=sort（A）；其中A为矩阵。
则Y为将A中各列按从小到大排序后的结果，I为Y中的元素在原矩阵A中所在的行号。
举例如下对于判断两个点是否在同一个连通分支，我的方法如下：声明一数组tag保存每个结点所在的连通分支的标号，初始值为每个结点的标号，当两个连通分量相连后则将它们的tag值设为一致程序流程图：关键代码说明：1．如何判断两个点是否在同一个连通分支①将图中每个顶点的tag值设为自身标号for j=1:lentag(j)=j;%关联标志初始化，将每个顶点的关联标志设为其本身end;②当确定两个顶点不在同一个连通分支时，将它们对应的边加入最优边集superedge中，并修改其中一个顶点的及其所在连通分支的各个点的tag值，使其和另一连通分支具有相同的tag值。
if(tag(anotherpoint)~=tag(index))%当两个点不属于一个连通集时，这两个点之间的边为最小生成树的边superedge(i,:)=[index,anotherpoint];%将其加入最小生成树的边集中i=i+1;%下标加1%下面的语句的作用是将两个连通分支变成一个连通分支，即tag值一样for j=1:len%以index的tag值为标准if((tag(j)==tag(anotherpoint))&(j~=anotherpoint))%遍搜tag数组，先将和anotherpoint tag值一样的点的tag值变为index的tag值tag(j)=tag(index);endendtag(anotherpoint)=tag(index);%将anotherpoint的tag值变为index的tag 值endend注意：上面的红色代码部分，要先将连同分支的其他点的tag值变为tag（index），最后在改变tag（anotherpoint）的tag值，如果先将tag(anotherpoint)的值改变了，编号在anotherpoint之后的点的tag值就无法正确更新了2.寻找最小边[Y,I]=sort(temp);%将temp的每列按从小到大排序，数组Y保存temp 排序后的结果，I中保存相应结果对应的在temp中的下标cost_min=min(Y(1,:));%找出权值最小的边index=find(Y(1,:)==cost_min);%找出权值最小的边对应的顶点index=index(1);%一条边对应两个节点，且不同的边的权值可能一样，这里为了方便处理人为规定了顺序，取标号最小的顶点进行处理anotherpoint=I(1,index);%找到该边对应的另一个顶点%将该边对应的权值修改为最大，防止该边在下次循环中再次被选为最优边temp(index,anotherpoint)=100;temp(anotherpoint,index)=100;3.显示模块采用的代码参见prim算法。