企业官网建设流程全解析

加权无向图

定义:

加权无向图是一种为每条边关联一个权重值或是成本的图模型

应用:

• 这种图能够自然地表示许多应用。在一副航空图中，边表示航线，权值则可以表示距离或是费用。例如，从西安飞纽约，怎样飞才能使时间成本最低或者是金钱成本最低？
• 在一副电路图中，边表示导线，权值则可能表示导线的长度即成本，或是信号通过这条先所需的时间。此时我们很容易就能想到，最小成本的问题，

在下图中，从顶点0到顶点4有三条路径，分别为0-2-3-4,0-2-4,0-5-3-4,那我们如果要通过那条路径到达4顶点最好呢？此时就要考虑，那条路径的成本最低。

加权无向图-----边的表示

• 加权无向图中的边我们就不能简单的使用v-w两个顶点表示了，而必须要给边关联一个权重值，因此我们可以使用对象来描述一条边。

API设计：

代码：

packagegraph.tu;publicclassEdgeimplementsComparable<Edge>{privatefinalintv;//顶点一privatefinalintw;//顶点二privatefinaldoubleweight;//当前边的权重//通过顶点v和w，以及权重weight值构造一个边对象publicEdge(intv,intw,doubleweight){this.v=v;this.w=w;this.weight=weight;}//获取边的权重值publicdoubleweight(){returnweight;}//获取边上的一个点publicinteither(){returnv;}//获取边上除了顶点vertex外的另外一个顶点publicintother(intvertex){if(vertex==v){returnw;}else{returnv;}}@OverridepublicintcompareTo(Edgethat){//使用一个遍历记录比较的结果intcmp;if(this.weight()>that.weight()){//如果当前边的权重值大，则让cmp=1；cmp=1;}elseif(this.weight()<that.weight()){//如果当前边的权重值小，则让cmp=-1；cmp=-1;}else{//如果当前边的权重值和that边的权重值一样大，则让cmp=0cmp=0;}returncmp;}}

加权无向图—的实现

importjava.util.Queue;importjava.util.concurrent.ConcurrentLinkedQueue;publicclassEdgeWeightedGraph{//顶点总数privatefinalintV;//边的总数privateintE;//邻接表privateQueue<Edge>[]adj;//创建一个含有V个顶点的空加权无向图publicEdgeWeightedGraph(intv){//初始化顶点数量this.V=v;//初始化边的数量this.E=0;//初始化邻接表this.adj=newConcurrentLinkedQueue[v];for(inti=0;i<adj.length;i++){adj[i]=newConcurrentLinkedQueue<Edge>();}}//获取图中顶点的数量publicintV(){returnV;}//获取图中边的数量publicintE(){returnE;}//向加权无向图中添加一条边epublicvoidaddEdge(Edgee){//需要让边e同时出现在e这个边的两个顶点的邻接表中intv=e.either();intw=e.other(v);adj[v].offer(e);adj[w].offer(e);//边的数量+1E++;}//获取和顶点v关联的所有边publicQueue<Edge>adj(intv){returnadj[v];}//获取加权无向图的所有边publicQueue<Edge>edges(){//创建一个队列对象，存储所有的边Queue<Edge>allEdges=newConcurrentLinkedQueue<>();//遍历图中的每一个顶点，找到该顶点的邻接表，邻接表中存储了该顶点关联的每一条边//因为这是无向图，所以同一条边同时出现在了它关联的两个顶点的邻接表中，需要让一条边只记录一次；for(intv=0;v<V;v++){//遍历v顶点的邻接表，找到每一条和v关联的边for(Edgee:adj(v)){if(e.other(v)<v){allEdges.offer(e);}}}returnallEdges;}}

最小生成树

• 之前学习的加权图，我们发现它的边关联了一个权重，那么我们就可以根据这个权重解决最小成本问题，但如何才能找到最小成本对应的顶点和边呢？最小生成树相关算法可以解决。
  

最小生成树—定义：

权重之和)最小的生成树

• 图的生成树是它的一棵含有其所有顶点的无环连通子图，一副加权无向图的最小生成树它的一棵权值(树中所有边的权重之和)最小的生成树
  

约定：

1. 只考虑连通图

• 只考虑连通图。最小生成树的定义说明它只能存在于连通图中，如果图不是连通的，那么分别计算每个连通图子图的最小生成树，合并到一起称为最小生成森林。
  

2. 所有边的权重都各不相同

• 如果不同的边权重可以相同，那么一副图的最小生成树就可能不唯一了，虽然我们的算法可以处理这种情况，但为了好理解，我们约定所有边的权重都各不相同。

最小生成树-----原理

1. 树的性质

1.1 用一条边接树中的任意两个顶点都会产生一个新的环；

1.2. 从树中删除任意一条边，将会得到两棵独立的树；

2. 切分定理

要从一副连通图中找出该图的最小生成树，需要通过切分定理完成。

切分：

• 将图的所有顶点按照某些规则分为两个非空且没有交集的集合。

横切边：

• 连接两个属于不同集合的顶点的边称之为横切边。

例如我们将图中的顶点切分为两个集合，灰色顶点属于一个集合，白色顶点属于另外一个集合，那么效果如下：

切分定理：

在一副加权图中，给定任意的切分，它的横切边中的权重最小者必然属于图中的最小生成树。

注意:
一次切分产生的多个横切边中，权重最小的边不一定是所有横切边中唯一属于图的最小生成树的边。