西昌有哪些做网站的公司,免费卖货平台,利用云服务器做网站,潍坊企业自助建站图论若干定义 图#xff08;graph#xff09;G#xff08;V,E#xff09;由定点vertex的集合V#xff0c; 和边edge的集合E组成。每一条边都是一个点对点#xff08;v#xff0c;w#xff09;#xff0c;其中 v,w 属于V集合的子集 如果点对点 是有序的#xff0c;那…图论若干定义 图graphGV,E由定点vertex的集合V 和边edge的集合E组成。每一条边都是一个点对点vw其中 v,w 属于V集合的子集 如果点对点 是有序的那么图就是有向图directed 图中的一条路径Path是定点序列的集合 w1w2w3…wn使得wi wi1 是边E的子集 其中1 i N,这样一条路径的长度length是该路径上的边数他等于N-1。从一个点的到他自身可以看成是一条路径如果路径不包含边那么路径的长度为0. 如果图有一条从一个定点到自身的边vv那么这条路径v也叫作环loop 连通图 如果一个无向图中从一个顶点到每个其他顶点存在一条路径则称改无向图是连通图 强连通图 一个有向的连通图是强连通图 基础图 如果一个有向图不是强连通图但是他的有基础的图结构即其边上去掉方向所成的图是连通的那么改有向图称为弱连通图 完全图 若图中每一对顶点之间都存在一条边的我们称这种图为完全图 现实中案例 航空系统每个机场都是顶点机场之间的航线是边边可以有权重标识时间距离费用等。交通流可以用一个图来模型化每一条街道交叉口标识一个顶点每一条街道都是一条边。边的值可以代表速度限制或者容量车道数量等。我们可以找一条最短路径或者用改信息找出交通瓶颈最可能的位置。
图的表示基本数据结构
我们先用一个案例有向图无向图类似表示如图中假设可以从1号顶点编号。图中不表示7个顶点和12条表。
方法一二维数组
最简单的数据结构使用一个二维数组标识称为邻接矩阵adjacent matrix 标识法。对于每条边uv设置A[u][v] true;否则 设置false。如果边有一个权重那么我们设置A[u][v] X权重值。例如我们寻找最廉价的航空线路那么我们可以用 MXA 无穷大标识不存在航线。如果处于某种原因我们找到最昂贵的路线那么可以用 -MAX表示不存在的边。以上二维数组的表示方式优点是非常简单但是空间需求是OV^2 如果图的边不是很多那么这种标识的代价就会非常大若图是稠密dense的E O(| V ^ 2|)那么我们用二维数组的邻接矩阵的标识方法是合适的因为数据结构中每一个位置的值都是有用的值。致命的缺点在于我们现实生活中的案例几乎都是稀疏的数据例如街道路口几乎所有街道多的话都只有四个方向东南西北因此任意路口的标识为节点 方向标识边那么E 4V如果3000 个路口3000 个顶点12000 条边那么需要3000*3000 的数组而且数组中大部分元素都是false因为一个节点只连接附近四个节点与其他节点的连通数据位false。浪资源
方法二邻接表 如果图不是稠密的是稀疏的则更好的解决方案就是邻接表adjacency list表示对每一个顶点我们使用一个表存放所有邻接的顶点。这个时候占用的空间是 O(E V)他相对于图的大小而言是线性的这种抽象表示方法我们用如下图表示很想一个MAP数据接口的样子。如果边有权重那么我们可以在图节点E中附加信息增加权重信息存在邻接表中。 邻接表是标识图的标准方法。无向图可以类似的标表示每条边uv出现在两个表中因此空间的使用基本是双倍的。在图论算法中通常需要找出与某个给定顶点v邻接的所有的顶点。 而这可以通过简单的扫描相应邻接表来完成用时与这些找到顶点的个数成正比 如下代码定义邻接表节点
/*** 图节点元素* author liaojiamin* Date:Created in 16:28 2020/12/28*/
public class Vertex implements ComparableVertex {//图节点出度节点 数组private ListVertex vertexList new ArrayList();//图节点入度节点 数组private ListVertex insertVertexList new ArrayList();private Integer dist;private boolean know;//目标节点到本节点的上一个节点的 节点信息private Vertex path;private Integer weight;public ListVertex getInsertVertexList() {return insertVertexList;}public void setInsertVertexList(ListVertex insertVertexList) {this.insertVertexList insertVertexList;}public Integer getWeight() {return weight;}public void setWeight(Integer weight) {this.weight weight;}public Vertex getPath() {return path;}public void setPath(Vertex path) {this.path path;}public ListVertex getVertexList() {return vertexList;}public void setVertexList(ListVertex vertexList) {this.vertexList vertexList;}public Integer getDist() {return dist;}public void setDist(Integer dist) {this.dist dist;}public boolean isKnow() {return know;}public void setKnow(boolean know) {this.know know;}Overridepublic int compareTo(Vertex o) {return this.dist - o.dist;}
}拓扑排序
拓扑排序是对有向无圈图的顶点的一种排序是的如果存在一条从Vi 到Vj的路径那么在排序中Vj就出现在Vi的后面如下图中有向边vw表示在v必须先比w 先完成。如果图中含有圈那么拓扑排序是不可能存在的因为对圈上的任何两个顶点vwv先于w同时也需要满足w先于v。此处拓扑排序不必是惟一的任何合理的排序都是合理的。如下图所示 图中v1,v2,v5,v4,v3,v6,v7和v1,v2,v5,v4,v7 两个都是拓扑排序
拓扑排序算法分析
一个简单的拓扑排序算法 先找出任意一个没有入边的顶点显示出改顶点将他及其边一起从图中删除对图中其余部分同样用这种方法处理。 实现方式如下
/*** 图论 求拓扑排序算法* author liaojiamin* Date:Created in 14:56 2021/1/6*/
public class GraphTopLogicalSort {//节点定义Vertex//图节点相邻节点组// private ListVertex vertexList new ArrayList(); 存储节点出度节点// private ListVertex insertVertexList new ArrayList(); 存储节点入度节点// private Integer dist; 存储节点拓扑编号//假设图基本数据结构已经被读入邻接表中private static final ListVertex vertices new ArrayList();/*** 寻找入度为0 的图节点* */public Vertex findNewVertexOfIndegreeZero(){Vertex insetZeroVertex null;for (Vertex vertex : vertices) {if(vertex.getInsertVertexList().size() 0){insetZeroVertex vertex;}}//节点入度出度都为0 删除节点信息if(insetZeroVertex ! null insetZeroVertex.getVertexList().size() 0){vertices.remove(insetZeroVertex);}return insetZeroVertex;}/*** 拓扑排序算法* */public void topSort(){for (int i 0; i vertices.size(); i) {Vertex v findNewVertexOfIndegreeZero();if(v null){//每个节点都有入度说明是有圈return;}v.setDist(i);for (Vertex vertex : v.getVertexList()) {//更新V节点相邻节点中所有信息vertex.getVertexList().remove(v);}}}
}
以上实现方式中findNewVertexOfIndegreeZero方法是对顶点数组的一个遍历所有每次对他的调用都会花费O(V)的世界由于有V次这样的调用所有算法时间复杂度为O(V^2)优化方式邻接表标识图的方式注定他是稀疏的因此我们每次去更新节点的入度的时候只有少部分节点需要更新也久只有少部分节点的入度将变为0 此时我们通过扫描所有数据的方式来查找入度为 0 的代价太大我们可以用一个队列或者栈来存储入度为 0 的节点对每个顶点计算入度后然后将入度为0 的节点天界到队列当队列不为空就删除顶点V并将对应邻接节点入度减去v这样拓扑排序的顺序就是出队列的顺序。代码实现如下 /*** 优化拓扑算法* */public void topSort_v1(){ListVertex insertZeroVertex new ArrayList();insertZeroVertex.add(findNewVertexOfIndegreeZero());int i 0;while (insertZeroVertex.size() 0){Vertex v insertZeroVertex.remove(0);v.setDist(i);for (Vertex vertex : v.getVertexList()) {//减少入度vertex.getInsertVertexList().remove(v);if(vertex.getInsertVertexList().size() 0){//将入度为0 的节点加入队列insertZeroVertex.add(vertex);}}}}最短路径算法
最短路径算法是在赋权图的情况下使用与每条边vivj想联系的是穿越改边的代价权重Cij。一条路径v1v2v3v4…vn的值叫做赋权路径长度weighted path length而无权路径长unweighted path length只是路径上边的数量即N-1。
单源最短路径问题 给定一个赋权图G VE和一个特定顶点s作为输入找出s到G中每一个其他顶点的最短赋权路径。如下案例 从v1到v6的最短赋权路径的值为6他是从v1 到 v4 到v7 在到v6的路径。在这两个顶点之间的最短无权路径长度为2.一般说当不指名我们讨论的是赋权路径还是无权路径时候如果图是赋权的那就是赋权路径。还有上图中从v6 到v1 是无路径的。
负圈值
以上案例中如果存在负数的权重那么会有问题如下图。从v5 到v4 的路径值为1但是通过下面的循环v5,v4,v2,v5,v4存在一条更短的路径他的值是-5.这条路径任然不是最短的因为我们可以循环中不断的重复。因此这两个顶点之间最短路径问题是不确定的。类似v1 到v6的最短路径也是不确定的。这种情况就叫做负圈值当图中存在负圈值最短路径问题是不确定的有负的边增加问题难度
四种最短路径目标
首先开了无权最短路径问题并指出如何以O(EV)的时间复杂度求解无负边情况先求解赋权最短路径使用合理数据结构实现运行时间在O(ElogV)有负边情况提供解决方案时间复杂度O(E*V)以线性时间解决无圈图特殊情况的赋权问题
无权最短路径
如下图表示一个无权图G使用某个顶点s作为输入参数我们要找出从s到所有其他顶点的最短路径。因为是无权所有我们只需要关注边我们将他当成是权重为1 的赋权问题。
算法分析
选择s为v3次数立刻可以看出s到v3的最短路径是0 到自己接的是无距离的。标记如图 接着寻址与s相邻的节点即s出发距离为1 的节点。这些顶点可以通过查询与s节点的领接节点数组来找到。我们看到v1和v6与s相邻如下图 同理继续寻址邻接到v1和v6的顶点显然是v2v4他们到v3的最短路径是2 最后通过v2v4的邻接节点找到v5v7各有一条3的最短路径: 以上搜索图的方法称为广度优先搜索breadth-first search。按层处理顶点距离开始最近的那些顶点首先被求值最远的顶点最后被求值。这很像树的层序遍历level-order traversal。 算法分析 对每个顶点跟踪三个信息首先将从s开始到顶点的距离dist记录为0因为s到自身的距离是0顶点s的path属性记录为null这个变量用来标记我们能够显示出的实际路径know变量标记为false标识他是否被处理过处理过后标记为true保证不会重复处理而导致更长的路径因为按广度优先原则首先处理的路径一定是对短的路径。算法流程将dist 0 上的顶点声明为know接着dist 1 上的顶点声明为know在dist 2的know依次类推并且每一步骤将上一步骤节点存储在Path中我们通过追溯Path遍历可以显示实际的路径如下代码实现
/*** 最短路径算法* author liaojiamin* Date:Created in 16:29 2020/12/28*/
public class GraphShotLine {//图节点数组private static final ListVertex vertexVraph new ArrayList();private static final Integer MAX_DIST Integer.MAX_VALUE;/*** 递归打印路径* */public void printPath(Vertex v){if(v.getPath() ! null){printPath(v.getPath());}System.out.println(v);}/*** 无权重图最短路径算法 解法一* 时间复杂度O(V^2)* */public void unweighted(Vertex s){for (Vertex vertex : vertexVraph) {vertex.setDist(MAX_DIST);vertex.setKnow(false);}s.setDist(0);Integer NUM_VERTICES vertexVraph.size();//遍历从 0 ~ MAX 距离的距离范围内所有节点到目标节点的距离默认最差是链式距离是NUM_VERTICESfor (Integer i 0; i NUM_VERTICES; i) {for (Vertex vertex : vertexVraph) {if(!vertex.isKnow() vertex.getDist() i){vertex.setKnow(true);for (Vertex sunVertex : vertex.getVertexList()) {if(sunVertex.getDist() MAX_DIST){sunVertex.setDist(i 1);sunVertex.setPath(vertex);}}}}}}}如上代码实现中双重for循环时间复杂度O(v^2).一个明显的效率低下的地方在于在for循环还未结束的时候其实已经将所有节点都已经编辑为know但是循环还在继续。直到所有节点都被遍历一次为止。优化方式我们可以用类似对拓扑排序的做法来避免这种双重循环最简单的方式我们将即将要处理的节点放入队列中然后依次从队列中取出来处理 当处理s节点的时候将s设置know将s添加到有序队列将出队列第一个节点此时是s节点将s邻接节点的dist1并且将所有邻接节点如队列持续上面两个步骤知道队列中的节点为空为止如下代码实现
/*** 最短路径算法二* author liaojiamin* Date:Created in 16:29 2020/12/28*/
public class GraphShotLine {//图节点数组private static final ListVertex vertexVraph new ArrayList();private static final Integer MAX_DIST Integer.MAX_VALUE;/*** 递归打印路径* */public void printPath(Vertex v){if(v.getPath() ! null){printPath(v.getPath());}System.out.println(v);}/*** 无权重图最短路径算法 解法二* */public void unweighted_1(Vertex s){for (Vertex vertex : vertexVraph) {vertex.setDist(MAX_DIST);vertex.setKnow(false);}s.setDist(0);LinkedListVertex sunVertexList new LinkedList();sunVertexList.addFirst(s);while (!sunVertexList.isEmpty()){Vertex sunVertex sunVertexList.getFirst();sunVertexList.removeFirst();for (Vertex vertex : sunVertex.getVertexList()) {if(vertex.getDist() MAX_DIST){vertex.setDist(sunVertex.getDist() 1);vertex.setPath(sunVertex);sunVertexList.addLast(vertex);}}}}
}使用拓扑排序的方式处理最短路径问题只要使用的是邻接表运行时间就是O(EV)
Dijkstra算法
如果图是有权重图那么问题会更复杂一点但是算法还是可以通用。我们还是保留之前的图节点结构。解决单源最短路径问题一般嘴阀叫做Dijkstra算法Dijkstras algorithm。这个有很多年历史的解决方法是贪婪算法greedy algorithm最好的案例。贪婪算法一般是分阶段求解一个问题在每个节点他都把出现的当作是最好的方法。Dijkstra算法按阶段进行和无权最短路径算法一样。每个阶段Dijkstra算法选择一个顶点v他在所有unknow顶点中具有最小的dist同时算法声明从s到v的最短路径是known的。阶段的其余部分由dith的更新工作组成。 在无权的情况下如果dist_w Max无穷大 那么设置dist_w dist_v 1。因此如果顶点v能提供一条更短的路径则我们本质上降低了dist_w的值。如果我们对赋权的情况也用这个逻辑那么当dist_w的新值dist_v C_vw是一个更小的值那么我们就设置dist_w dist_v V_vw总的来说使用通过w节点的路径上的顶点v是不是一个最优解取决于算法原始的dist_w 是不使用v的值的以上所有算出的值是使用v值后的最短路径
算法分析
依然按照之前的案例如下图中设开始节点s是v1第一个选择的顶点是v1路径长度 0 标记v1为known即v1是known的那么其他的节点的dist值就需要调整邻接到v1的节点v2 v4 两个调整 v2 v4 跳转之后的节点情况如下表格所示
vknwndistpathv1T0nullv2F2v1v3FMAXnullv4F1v1v5FMAXnullv6FMAXnullv7FMAXnull
下一步选取v4 因为v4.dist v2.dist标记v3的known true 顶点v3 v5v6v7,是邻接顶点他们的实际值需要调整如下图所示
vknwndistpathv1T0nullv2F2v1v3F3v4v4T1v1v5F3v4v6F9v4v7F5v4
接着选取v2 只有v4 v5是他邻接的顶点但是v4已经是known我们不做处理v5 邻接节点我们继续刚才那个步骤 那么dist v2.dist V_25 210 12,显然12 3 因为v5 的最短路径现有的是3 所以12 不是最优解v5 保留现在的值不变。
vknwndistpathv1T0nullv2T2v1v3F3v4v4T1v1v5F3v4v6F9v4v7F5v4
下一个被选取的是v5因为v5 是剩下unknown节点中dist最小的一个那么v7 是他的邻接节点同样算法v7 36 5所有保留原来最优值5 不变接着v3还是应为他是dist最小值v3邻接节点v6 dist 35 8 9将v6 的dist下调到8 最后结果如下图
vknwndistpathv1T0nullv2T2v1v3T3v4v4T1v1v5T3v4v6F8v3v7F5v4
接着继续选v7 邻接节点v6 下调到51 6得到如下
vknwndistpathv1T0nullv2T2v1v3T3v4v4T1v1v5T3v4v6F6v7v7T5v4
最后选v6
vknwndistpathv1T0nullv2T2v1v3T3v4v4T1v1v5T3v4v6T6v7v7T5v4
依据以上算法分析我们可以从某个顶点v开始到某顶点w的实际路径可以编写一个递归案例跟踪Path变量的值来得到最短路径如下代码实现
/*** 最短路径算法* author liaojiamin* Date:Created in 16:29 2020/12/28*/
public class GraphShotLine {//图节点数组private static final ListVertex vertexVraph new ArrayList();private static final Integer MAX_DIST Integer.MAX_VALUE;/*** 递归打印路径* */public void printPath(Vertex v){if(v.getPath() ! null){printPath(v.getPath());}System.out.println(v);}/*** 有权重图最短路径算法* */public void dijkstra(Vertex s){for (Vertex vertex : vertexVraph) {vertex.setDist(MAX_DIST);vertex.setKnow(false);}s.setDist(0);LinkedListVertex sunVertexList new LinkedList();sunVertexList.addFirst(s);while (sunVertexList.size() 0){//每次取第一个最小值Vertex smallVertex sunVertexList.removeFirst();smallVertex.setKnow(true);//保存需要添加的新节点LinkedListVertex newVertexList new LinkedList();for (Vertex vertex : smallVertex.getVertexList()) {if(!vertex.isKnow()){Integer cvw vertex.getWeight();if(smallVertex.getDist() cvw vertex.getDist()){vertex.setDist(smallVertex.getDist() cvw);vertex.setPath(smallVertex);//处理过的节点才是之后可能的路径newVertexList.add(vertex);}}}//将可能的路径按从小到大顺序加入有序队列sunVertexList.addAll(getSortVertex(newVertexList));}}/*** 对子节点列表进行从小到大排序* */public LinkedListVertex getSortVertex(ListVertex vertexs){if(vertexs.size() 0){return null;}for (int i 0; i vertexs.size(); i) {for(int j i;j 0;j--){if(vertexs.get(j-1).compareTo(vertexs.get(j)) 0 ){Vertex vertex vertexs.get(j-1);vertexs.set(j-1, vertexs.get(j));vertexs.set(j, vertex);}}}return new LinkedList(vertexs);}}如上算法中每次节点w的举报变化时候将w和新值d_w插入到队列中这样对优先队列中的每个顶点就可能有多个对象在队列中当我们deletedMin出队列首元素操作将最小的顶点从队列中删除必须坚持是否是known如果是就忽略不处理接着执行下一次deleteMin。算法的队列最大可能达到E 所有节点集合这么多。由于EV^2那么logE 2logv因此并不影响时间界限
上一篇数据结构与算法–B树原理及实现 下一篇数据结构与算法–图论-最短路径算法应用
