《(实验6)贪婪技术实验》由会员分享，可在线阅读，更多相关《(实验6)贪婪技术实验（6页珍藏版）》请在金锄头文库上搜索。
1、曹加站20111060255信息计科六、(实验6)贪婪技术实验(1)写出并调试用Prim或者Kruskal的最小生成树程序。package caoj iazhan； import java.util.ArrayList;import java.util.Arrays； import java.util.HashSet；import java.util.Set；y *图的最小树生成算法* author win7*/public class MiniSpanTree (/ *求图最小生成树的PRIM算法*基木思想：假设N=(V,E)是联通网，TE是N上的最想生成树中的变得集合。算法从U=(uO)
2、(uO属于V),* TE=)开始，重复执行下述操作：在所有的u属于U, v属于V-U的边(u, v)属于E中 找到一条代价最小*的边(uO, vO)并入集合TE,同事v0并入U,直至U=V为止。此时TE中必Wn-1条边, 则T=(V,(TE)*为N的最小生成树。* param graph 图* param start 开始节点* param n图中节点数*/public static void PRIM(int graph,int start,int n)(int mins = new int n 2 ； /IJ于保存集合U到V-U之间的最小边和它的 值，mins i 0值表示到该节点i边的起
3、始节点值为表示没有到它的起始点，mins i 1值 表示到该边的最小值，/mins i 1 =0表示该节点己将在集合U中for (int i = 0； in； i + +) /初始化minsif(i=start)minsi 0=-l；mins i 1=0；)else if ( graphstart i !=-l) (/说明存在(start, i)的边mins i 0=start；minsi1= graphstarti；)else(mins i 0=-l；mins i 1=Integer.MAX_VALUE； 一/System. out. print In ( umins n + i + u 0
4、 =u+mins i 0 +u | | mins u + i + ,f 1 =u+minsi1)；)for(int i=0;in-1;i+)int minV=-1,minW=Integer.MAX_VALUE；for (int j=0； jminsj 1 )(minW=minsj1； minV=j；)/System.out.printin(HminV=u+minV)；minsminV 1=0；System, out .printin (”最小生成树的第” + i+条最小边=,权重=” +minW)；for (int j=0; jn； j+) (/E新mins数组if(mins j 1 !=0)
5、 (/System. out. print In (,rMINV=11 +minV+,r | | tree minV j =11 + tree minV j )/if ( graphminV j !=【& graphminV jminsj 1 ) (minsj 0=minV；mins j 1= graphminV j；/ *求最小树的Kruskal算法*算法思想：克善斯卡尔算法从另一个途径求网中的最小生成树。假设联通网N=(V, E)，则令*最小生成树的厨师状态为只有n个顶点而无边的非连通图T=(V,),途中每个顶点自 称一个连通分量。*在E中选择代价最小的边，若该边衣服的顶点落在T中不同的连
6、通分量上，则将此边加入 到T中，否则舍去此边*而选择下一条最小的边。以此类推，直至T中所有的顶点都在同一连通分量上为止。* param V图中的节点集合* param E图中边的集合*/public static void KRUSKAL(int V,Edge E)(Arrays . sort (E) ； /将边按照权巫w升序排序ArrayList sets=new ArrayList()； for(int i=0；iV.length；i+)(HashSet set=new HashSet()； setadd(Vi)； setsadd(set)；)System.out.printin(n +
7、+ + + + + + + + + + + + + + + + + + + + + size= n + sets.size()； for(int i=0；iE.length；i+)int start=E i .i,end=E i .j；int counti = -l,countj = -2；for(int j =0；j sets.size () ；j + + ) HashSet set=sets.get(j)； if (set.contains(start) counti=j；)if (set.contains(end) countj =j；)if (counti0| |countjto.w)
8、 return 1；else if(this.w=to.w) return 0;else return -1；)Overridepublic String toString() return nstart=n+i+n|end=u+j+u|w=n+w； )(2)写出并调试用Dijkstra程序。package caoj iazhanl；public class Dijkstra ( public static void main(String args) new Dijkstra () .use ();)public void use()(new DijkstraO . di j kstra (
9、0 , a, dist, prev)； for (int i = 0； i dist.length； i+) ( System, out .print (dist i +11 u )；)单元最短路径问题的Dijkstra算法public void dijkstra (int v , float a, float dist, int prev) ( int n = dist.length - 1 ； if(v n-1) return； boolean s = new booleann+1；/初始化for(int i = 1； i = n； i + + ) ( dist i = a v i; s
10、i = false；if (dist i = Float VALUE) ( previ = 0； else ( previ = v； )distv = 0；sv = true；for(int i = 1； i n； i+)(float temp = Float.MAX_VALUE；int u = v；for(int j = 1； j = n； j + +) (if(!sj) & (distj temp)( U = j ;temp = dist j；)su = true； /找到了笫一个并入S的节点for(int j = 1； j = n； j + + ) (if ( ( !s j ) & (au j Float. MAX_VALUE) ) ( float newdist = distu + auj； if(newdist dist j)(/dist j减少
