文章目录加权无向图定义:加权无向图是一种为每条边关联一个权重值或是成本的图模型应用:加权无向图-----边的表示API设计代码加权无向图---的实现最小生成树最小生成树---定义权重之和)最小的生成树约定1. 只考虑连通图2. 所有边的权重都各不相同最小生成树-----原理1. 树的性质2. 切分定理切分横切边切分定理在一副加权图中给定任意的切分它的横切边中的权重最小者必然属于图中的最小生成树。加权无向图定义:加权无向图是一种为每条边关联一个权重值或是成本的图模型应用:这种图能够自然地表示许多应用。在一副航空图中边表示航线权值则可以表示距离或是费用。例如从西安飞纽约怎样飞才能使时间成本最低或者是金钱成本最低在一副电路图中边表示导线权值则可能表示导线的长度即成本或是信号通过这条先所需的时间。此时我们很容易就能想到最小成本的问题在下图中从顶点0到顶点4有三条路径分别为0-2-3-4,0-2-4,0-5-3-4,那我们如果要通过那条路径到达4顶点最好呢此时就要考虑那条路径的成本最低。加权无向图-----边的表示加权无向图中的边我们就不能简单的使用v-w两个顶点表示了而必须要给边关联一个权重值因此我们可以使用对象来描述一条边。API设计代码packagegraph.tu;publicclassEdgeimplementsComparableEdge{privatefinalintv;//顶点一privatefinalintw;//顶点二privatefinaldoubleweight;//当前边的权重//通过顶点v和w以及权重weight值构造一个边对象publicEdge(intv,intw,doubleweight){this.vv;this.ww;this.weightweight;}//获取边的权重值publicdoubleweight(){returnweight;}//获取边上的一个点publicinteither(){returnv;}//获取边上除了顶点vertex外的另外一个顶点publicintother(intvertex){if(vertexv){returnw;}else{returnv;}}OverridepublicintcompareTo(Edgethat){//使用一个遍历记录比较的结果intcmp;if(this.weight()that.weight()){//如果当前边的权重值大则让cmp1cmp1;}elseif(this.weight()that.weight()){//如果当前边的权重值小则让cmp-1cmp-1;}else{//如果当前边的权重值和that边的权重值一样大则让cmp0cmp0;}returncmp;}}加权无向图—的实现importjava.util.Queue;importjava.util.concurrent.ConcurrentLinkedQueue;publicclassEdgeWeightedGraph{//顶点总数privatefinalintV;//边的总数privateintE;//邻接表privateQueueEdge[]adj;//创建一个含有V个顶点的空加权无向图publicEdgeWeightedGraph(intv){//初始化顶点数量this.Vv;//初始化边的数量this.E0;//初始化邻接表this.adjnewConcurrentLinkedQueue[v];for(inti0;iadj.length;i){adj[i]newConcurrentLinkedQueueEdge();}}//获取图中顶点的数量publicintV(){returnV;}//获取图中边的数量publicintE(){returnE;}//向加权无向图中添加一条边epublicvoidaddEdge(Edgee){//需要让边e同时出现在e这个边的两个顶点的邻接表中intve.either();intwe.other(v);adj[v].offer(e);adj[w].offer(e);//边的数量1E;}//获取和顶点v关联的所有边publicQueueEdgeadj(intv){returnadj[v];}//获取加权无向图的所有边publicQueueEdgeedges(){//创建一个队列对象存储所有的边QueueEdgeallEdgesnewConcurrentLinkedQueue();//遍历图中的每一个顶点找到该顶点的邻接表邻接表中存储了该顶点关联的每一条边//因为这是无向图所以同一条边同时出现在了它关联的两个顶点的邻接表中需要让一条边只记录一次for(intv0;vV;v){//遍历v顶点的邻接表找到每一条和v关联的边for(Edgee:adj(v)){if(e.other(v)v){allEdges.offer(e);}}}returnallEdges;}}最小生成树之前学习的加权图我们发现它的边关联了一个权重那么我们就可以根据这个权重解决最小成本问题但如何才能找到最小成本对应的顶点和边呢最小生成树相关算法可以解决。最小生成树—定义权重之和)最小的生成树图的生成树是它的一棵含有其所有顶点的无环连通子图一副加权无向图的最小生成树它的一棵权值(树中所有边的权重之和)最小的生成树约定1. 只考虑连通图只考虑连通图。最小生成树的定义说明它只能存在于连通图中如果图不是连通的那么分别计算每个连通图子图的最小生成树合并到一起称为最小生成森林。2. 所有边的权重都各不相同如果不同的边权重可以相同那么一副图的最小生成树就可能不唯一了虽然我们的算法可以处理这种情况但为了好理解我们约定所有边的权重都各不相同。最小生成树-----原理1. 树的性质1.1 用一条边接树中的任意两个顶点都会产生一个新的环1.2. 从树中删除任意一条边将会得到两棵独立的树2. 切分定理要从一副连通图中找出该图的最小生成树需要通过切分定理完成。切分将图的所有顶点按照某些规则分为两个非空且没有交集的集合。横切边连接两个属于不同集合的顶点的边称之为横切边。例如我们将图中的顶点切分为两个集合灰色顶点属于一个集合白色顶点属于另外一个集合那么效果如下切分定理在一副加权图中给定任意的切分它的横切边中的权重最小者必然属于图中的最小生成树。注意:一次切分产生的多个横切边中权重最小的边不一定是所有横切边中唯一属于图的最小生成树的边。