信阳网站推广公司怎么做自己的购物网站

当前位置： 首页 > news >正文

信阳网站推广公司,怎么做自己的购物网站,网页图片怎么下载,怎么弄自己的微信小程序友情链接#xff1a;数据结构专栏 目录 图【知识框架】 图的基本概念一、图的定义二、图的基本概念和术语1、有向图2、无向图3、简单图4、多重图5、完全图#xff08;也称简单完全图#xff09;6、子图7、连通、连通图和连通分量8、强连通图、强连通分量9、生成树、生成森林…友情链接数据结构专栏 目录 图【知识框架】 图的基本概念一、图的定义二、图的基本概念和术语1、有向图2、无向图3、简单图4、多重图5、完全图也称简单完全图6、子图7、连通、连通图和连通分量8、强连通图、强连通分量9、生成树、生成森林10、顶点的度、入度和出度11、边的权和网12、稠密图、稀疏图13、路径、路径长度和回路14、 简单路径、简单回路15、距离16、有向树 图的存储结构一、邻接矩阵二、邻接表三、十字链表四、邻接多重表五、边集数组 图的遍历一、深度优先遍历1、DFS算法2、DFS算法的性能分析3、深度优先的生成树和生成森林 二、广度优先遍历1、BFS算法2、BFS算法性能分析 三、图的遍历与图的连通性 最小生成树一、普里姆Prim算法二、克鲁斯卡尔Kruskal算法 最短路径一、迪杰斯特拉( Dijkstra )算法二、弗洛伊德( Floyd )算法 拓扑排序一、定义二、算法 关键路径一、定义二、算法 总结附录上文链接下文链接专栏参考资料 图 【知识框架】 图的基本概念 在线性表中数据元素之间是被串起来的仅有线性关系每个数据元素只有一个直接前驱和一个直接后继。在树形结构中数据元素之间有着明显的层次关系并且每一层上的数据元素可能和下一层中多个元素相关但只能和上一层中一个元素相关。图是一种较线性表和树更加复杂的数据结构。在图形结构中结点之间的关系可以是任意的图中任意两个数据元素之间都可能相关。 一、图的定义 图(Graph)是由顶点的有穷非空集合 V ( G ) V(G) V(G)和顶点之间边的集合 E ( G ) E(G) E(G)组成通常表示为: G ( V , E ) G(V,E) G(V,E)其中 G G G表示个图 V V V是图 G G G中顶点的集合 E E E是图 G G G中边的集合。若 V { v 1 , v 2 , … , v n } V {v_1, v_2,…,v_n} V{v1​,v2​,…,vn​}则用 ∣ V ∣ |V| ∣V∣表示图 G G G中顶点的个数也称图 G G G的阶 E { ( u , v ) ∣ u ∈ V , v ∈ V } E {(u, v) |u∈V, v∈V} E{(u,v)∣u∈V,v∈V}用 ∣ E ∣ |E| ∣E∣表示图 G G G中边的条数。 注意:线性表可以是空表树可以是空树但图不可以是空图。就是说图中不能一个顶点也没有图的顶点集V一定非空但边集E可以为空此时图中只有顶点而没有边。 二、图的基本概念和术语 1、有向图 若E是有向边(也称弧)的有限集合时则图G为有向图。弧是顶点的有序对记为v, w其中v,w是顶点v称为弧尾w称为弧头v,w称为从顶点v到顶点w的弧也称v邻接到w或w邻接自v。 图(a)所示的有向图 G 1 G_1 G1​可表示为 G 1 ( V 1 , E 1 ) G_1 (V_1,E_1) G1​(V1​,E1​) V 1 { 1 , 2 , 3 } V_1{1,2,3} V1​{1,2,3} E 1 { 1 , 2 , 2 , 1 , 2 , 3 } E_1{1,2,2,1,2,3} E1​{1,2,2,1,2,3} 2、无向图 若E是无向边(简称边)的有限集合时则图G为无向图。边是顶点的无序对记为(v, w)或(w,v),因为(v,w)(w,v), 其中v,w是顶点。可以说顶点w和顶点v互为邻接点。边(v, w)依附于顶点w和v或者说边(v, w)和顶点v, w相关联。
图(b)所示的无向图G2可表示为 G 2 ( V 2 , E 2 ) G_2(V_2,E_2) G2​(V2​,E2​) V 2 { 1 , 2 , 3 , 4 } V_2{1,2,3,4} V2​{1,2,3,4} E 2 { ( 1 , 2 ) , ( 1 , 3 ) , ( 1 , 4 ) , ( 2 , 3 ) , ( 2 , 4 ) , ( 3 , 4 ) } E_2{(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)} E2​{(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)} 3、简单图 一个图 G G G若满足:①不存在重复边;②不存在顶点到自身的边则称图 G G G为简单图。上图中 G 1 G_1 G1​和 G 2 G_2 G2​均为简单图。数据结构中仅讨论简单图。 4、多重图 若图 G G G中某两个结点之间的边数多于一条又允许顶点通过同一条边和自己关联则 G G G为多重图。多重图的定义和简单图是相对的。 5、完全图也称简单完全图 对于无向图 ∣ E ∣ |E| ∣E∣的取值范围是 0 0 0到 n ( n − 1 ) / 2 n(n-1)/2 n(n−1)/2有 n ( n − 1 ) / 2 n(n -1)/2 n(n−1)/2条边的无向图称为完全图在完全图中任意两个顶点之间都存在边。对于有向图 ∣ E ∣ |E| ∣E∣的取值范围是 0 0 0到 n ( n − 1 ) n(n-1) n(n−1)有 n ( n − 1 ) n(n-1) n(n−1)条弧的有向图称为有向完全图在有向完全图中任意两个顶点之间都存在方向相反的两条弧。上图中 G 2 G_2 G2​为无向完全图而 G 3 G_3 G3​为有向完全图。
6、子图 设有两个图 G ( V , E ) G(V, E) G(V,E)和 G ′ ( V ′ , E ′ ) G(V, E) G′(V′,E′) 若 V ′ V V′是 V V V的子集且 E ′ E E′是 E E E的子集则称 G ′ G G′是 G G G的子图。若有满足 V ( G ′ ) V ( G ) V(G) V(G) V(G′)V(G)的子图 G ′ G G′则称其为 G G G的生成子图。上图中 G 3 G_3 G3​为 G 1 G_1 G1​的子图。 注意:并非V和E的任何子集都能构成G的子图因为这样的子集可能不是图即E的子集中的某些边关联的顶点可能不在这个V的子集中。 7、连通、连通图和连通分量 在无向图中若从顶点 v v v到顶点 w w w有路径存在则称 v v v和 w w w是连通的。若图 G G G中任意两个顶点都是连通的则称图 G G G为连通图否则称为非连通图。无向图中的极大连通子图称为连通分量。若一个图有 n n n个顶点并且边数小于 n − 1 n-1 n−1则此图必是非连通图。如下图(a)所示 图 G 4 G_4 G4​有3个连通分量如图b所示。 注意:弄清连通、连通图、连通分量的概念非常重要。首先要区分极大连通子图和极小连通子图极大连通子图是无向图的连通分量极大即要求该连通子图包含其所有的边;极小连通子图是既要保持图连通又要使得边数最少的子图。 8、强连通图、强连通分量 在有向图中若从顶点 v v v到顶点 w w w和从顶点 w w w到项点 v v v之间都有路径,则称这两个顶点是强连通的。若图中任何一对顶点都是强连通的则称此图为强连通图。有向图中的极大强连通子图称为有向图的强连通分量图 G 1 G_1 G1​的强连通分量如下图所示。 注意:强连通图、强连通分量只是针对有向图而言的。一般在无向图中讨论连通性在有向图中考虑强连通性。 9、生成树、生成森林 连通图的生成树是包含图中全部顶点的一个极小连通子图。若图中顶点数为 n n n,则它的生成树含有 n − 1 n-1 n−1条边。对生成树而言若砍去它的一条边则会变成非连通图若加上一条边则会形成一个回路。在非连通图中连通分量的生成树构成了非连通图的生成森林。图 G 2 G2 G2​的一个生成树如下图所示。 注意:包含无向图中全部顶点的极小连通子图只有生成树满足条件因为砍去生成树的任一条边图将不再连通。 10、顶点的度、入度和出度 图中每个顶点的度定义为以该项点为一个端点的边的数目。 对于无向图顶点v的度是指依附于该顶点的边的条数记为 T D ( v ) TD(v) TD(v)。 在具有 n n n个顶点、 e e e条边的无向图中 ∑ i 1 n T D ( v i ) 2 e \displaystyle\sum{i1}^{n}TD(vi) 2e i1∑n​TD(vi​)2e即无向图的全部顶点的度的和等于边数的2倍因为每条边和两个顶点相关联。 对于有向图,顶点 v v v的度分为入度和出度,入度是以顶点 v v v为终点的有向边的数目记为 I D ( v ) ID(v) ID(v); 而出度是以顶点 v v v为起点的有向边的数目记为 O D ( v ) OD(v) OD(v)。顶点 v v v的度等于其入度和出度之和即 T D ( v ) I D ( v ) O D ( v ) 。 TD(v) ID(v) OD(v)。 TD(v)ID(v)OD(v)。 在具有 n n n个顶点、 e e e条边的有向图中 ∑ i 1 n I D ( v i ) ∑ i 1 n O D ( v i ) e \displaystyle\sum{i1}^{n}ID(vi)\displaystyle\sum{i1}^{n}OD(v_i)e i1∑n​ID(vi​)i1∑n​OD(vi​)e即有向图的全部顶点的入度之和与出度之和相等并且等于边数。这是因为每条有向边都有一个起点和终点。 11、边的权和网 在一个图中每条边都可以标上具有某种含义的数值该数值称为该边的权值。这种边上带有权值的图称为带权图也称网。 12、稠密图、稀疏图 边数很少的图称为稀疏图反之称为稠密图。稀疏和稠密本身是模糊的概念稀疏图和稠密图常常是相对而言的。一般当图G满足 ∣ E ∣ ∣ V ∣ l o g ∣ V ∣ |E| |V|log|V| ∣E∣∣V∣log∣V∣时可以将 G G G视为稀疏图。 13、路径、路径长度和回路 顶点 v p v_p vp​到顶点 v q v_q vq​之间的一条路径是指顶点序列 v p , v i 1 , v i 2 , … , v i m , v q vp,v{i1},v{i2},…,v{i_m},v_q vp​,vi1​​,vi2​​,…,vim​​,vq​当然关联的边也可以理解为路径的构成要素。路径上边的数目称为路径长度。第一个顶点和最后一个顶点相同的路径称为回路或环。若一个图有 n n n个顶点并且有大于 n − 1 n-1 n−1条边则此图一定有环。 14、 简单路径、简单回路 在路径序列中顶点不重复出现的路径称为简单路径。除第一个顶点和最后一个顶点外其余顶点不重复出现的回路称为简单回路。 15、距离 从顶点 u u u出发到顶点 v v v的最短路径若存在则此路径的长度称为从 u u u到 v v v的距离。若从 u u u到 v v v根本不存在路径则记该距离为无穷 ( ∞ ) (∞) (∞)。 16、有向树 一个顶点的入度为0、其余顶点的入度均为1的有向图称为有向树。 图的存储结构 由于图的结构比较复杂任意两个顶点之间都可能存在联系因此无法以数据元素在内存中的物理位置来表示元素之间的关系也就是说图不可能用简单的顺序存储结构来表示。而多重链表的方式要么会造成很多存储单元的浪费要么又带来操作的不便。因此对于图来说如何对它实现物理存储是个难题接下来我们介绍五种不同的存储结构。 一、邻接矩阵 图的邻接矩阵(Adjacency Matrix) 存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息一个二维数组(称为邻接矩阵)存储图中的边或弧的信息。 设图 G G G有 n n n个顶点则邻接矩阵 A A A是一个 n ∗ n n*n n∗n的方阵定义为: 下图是一个无向图和它的邻接矩阵 可以看出: 无向图的邻接矩阵一定是一个对称矩阵(即从矩阵的左上角到右下角的主对角线为轴右上角的元与左下角相对应的元全都是相等的)。 因此在实际存储邻接矩阵时只需存储上(或下)三角矩阵的元素。对于无向图邻接矩阵的第 i i i行(或第 i i i列)非零元素(或非 ∞ ∞ ∞元素)的个数正好是第 i i i个顶点的度 T D ( v i ) TD(v_i) TD(vi​)。比如顶点 v 1 v_1 v1​的度就是 1 0 1 0 2 10102 10102。求顶点 v i v_i vi​的所有邻接点就是将矩阵中第i行元素扫描一遍 A [ i ] [ j ] A[i][j] A[i][j]为 1就是邻接点。 下图是有向图和它的邻接矩阵 可以看出: 主对角线上数值依然为0。但因为是有向图所以此矩阵并不对称。有向图讲究入度与出度顶点 v 1 v_1 v1​的入度为1,正好是第 v 1 v_1 v1​列各数之和。顶点 v 1 v_1 v1​的出度为2即第 v 1 v_1 v1​行的各数之和。与无向图同样的办法判断顶点 v i v_i vi​到 v j v_j vj​是否存在弧只需要查找矩阵中 A [ i ] [ j ] A[i][j] A[i][j] 是否为1即可。 对于带权图而言,若顶点 v i v_i vi​和 v j v_j vj​之间有边相连则邻接矩阵中对应项存放着该边对应的权值 下图是有向网图和它的邻接矩阵 通过以上对无向图、有向图和网的描述可定义出邻接矩阵的存储结构 #define MaxVertexNum 100 //顶点数目的最大值 typedef char VertexType; //顶点的数据类型 typedef int EdgeType; //带权图中边上权值的数据类型 typedef struct{VertexType Vex[MaxVertexNum]; //顶点表EdgeType Edge[MaxVertexNum][MaxVertexNum]; //邻接矩阵边表int vexnum, arcnum; //图的当前顶点数和弧树 }MGraph;注意: ①在简单应用中可直接用二维数组作为图的邻接矩阵(顶点信息等均可省略)。 ②当邻接矩阵中的元素仅表示相应的边是否存在时EdgeType可定义为值为0和1的枚举类型。 ③无向图的邻接矩阵是对称矩阵对规模特大的邻接矩阵可采用压缩存储。 ④邻接矩阵表示法的空间复杂度为 O ( n 2 ) O(n^2) O(n2) 其中n为图的顶点数 ∣ V ∣ |V| ∣V∣。 ⑤ 用邻接矩阵法存储图很容易确定图中任意两个顶点之间是否有边相连。但是要确定图中有多少条边则必须按行、按列对每个元素进行检测所花费的时间代价很大。 ⑥ 稠密图适合使用邻接矩阵的存储表示。 二、邻接表 当一个图为稀疏图时边数相对顶点较少使用邻接矩阵法显然要浪费大量的存储空间如下图所示 而图的邻接表法结合了顺序存储和链式存储方法大大减少了这种不必要的浪费。 所谓邻接表是指对图 G G G中的每个顶点 v i v_i vi​建立一个单链表第 i i i个单链表中的结点表示依附于顶点 v i v_i vi​ 的边(对于有向图则是以顶点 v i v_i vi​为尾的弧)这个单链表就称为顶点 v i v_i vi​的边表(对于有向图则称为出边表)。边表的头指针和顶点的数据信息采用顺序存储(称为顶点表)所以在邻接表中存在两种结点:顶点表结点和边表结点如下图所示。 顶点表结点由顶点域(data)和指向第一条邻接边的指针(firstarc) 构成边表(邻接表)结点由邻接点域(adjvex)和指向下一条邻接边的指针域(nextarc) 构成。 无向图的邻接表的实例如下图所示。 有向图的邻接表的实例如下图所示。 此时我们很容易就可以算出某个顶点的入度或出度是多少判断两顶点是否存在弧也很容易实现。 对于带权值的网图可以在边表结点定义中再增加一个weight的数据域存储权值信息即可。 图的邻接表存储结构定义如下 #define MAXVEX 100 //图中顶点数目的最大值 type char VertexType; //顶点类型应由用户定义 typedef int EdgeType; //边上的权值类型应由用户定义 /边表结点/ typedef struct EdgeNode{int adjvex; //该弧所指向的顶点的下标或者位置EdgeType weight; //权值对于非网图可以不需要struct EdgeNode *next; //指向下一个邻接点 }EdgeNode;/顶点表结点/ typedef struct VertexNode{Vertex data; //顶点域存储顶点信息EdgeNode *firstedge //边表头指针 }VertexNode, AdjList[MAXVEX];/邻接表/ typedef struct{AdjList adjList;int numVertexes, numEdges; //图中当前顶点数和边数 }图的邻接表存储方法具有以下特点 若 G G G为无向图则所需的存储空间为 O ( ∣ V ∣ 2 ∣ E ∣ ) O(|V|2|E|) O(∣V∣2∣E∣)若 G G G为有向图,则所需的存储空间为 O ( ∣ V ∣ ∣ E ∣ ) O(|V||E|) O(∣V∣∣E∣)。前者的倍数2是由于无向图中,每条边在邻接表中出现了两次对于稀疏图采用邻接表表示将极大地节省存储空间。在邻接表中给定一顶点能很容易地找出它的所有邻边因为只需要读取它的邻接表。在邻接矩阵中相同的操作则需要扫描一行花费的时间为 O ( n ) O(n) O(n)。但是若要确定给定的两个顶点间是否存在边则在邻接矩阵中可以立刻查到而在邻接表中则需要在相应结点对应的边表中查找另一结点效率较低。在有向图的邻接表表示中求一个给定顶点的出度只需计算其邻接表中的结点个数但求其顶点的入度则需要遍历全部的邻接表。因此,也有人采用逆邻接表的存储方式来加速求解给定顶点的入度。当然,这实际上与邻接表存储方式是类似的。图的邻接表表示并不唯一因为在每个顶点对应的单链表中各边结点的链接次序可以是任意的它取决于建立邻接表的算法及边的输入次序。 三、十字链表 十字链表是有向图的一种链式存储结构。 对于有向图来说邻接表是有缺陷的。关心了出度问题想了解入度就必须要遍历整个图才能知道反之逆邻接表解决了入度却不了解出度的情况。有没有可能把邻接表与逆邻接表结合起来呢?答案是肯定的就是把它们整合在一起。这就是我们现在要介绍的有向图的一种存储方法十字链表(Orthogonal List)。 我们重新定义顶点表结点结构如下表所示。 其中firstin表示入边表头指针指向该顶点的入边表中第一个结点firstout 表示出边表头指针指向该顶点的出边表中的第一个结点。 重新定义的边表结点结构如下表所示。 其中tailvex 是指弧起点在顶点表的下标headvex 是指弧终点在顶点表中的下标headlink是指入边表指针域指向终点相同的下一条边taillink是指边表指针域指向起点相同的下一条边。如果是网还可以再增加一个weight域来存储权值。 接下来通过一个例子详细介绍十字链表的结构。 如下图所示顶点依然是存入一个一维数组 { V 0 , V 1 , V 2 , V 3 } {V_0,V_1,V_2,V_3} {V0​,V1​,V2​,V3​}实线箭头指针的图示完全与的邻接表的结构相同。就以顶点 V 0 V_0 V0​来说firstout 指向的是出边表中的第一个结点 V 3 V_3 V3​。所以 V 0 V_0 V0​边表结点的 h e a d v e x 3 headvex3 headvex3而tailvex就是当前顶点 V 0 V_0 V0​的下标0由于 V 0 V_0 V0​只有一个出边顶点所以headlink和taillink都是空。 我们重点需要来解释虚线箭头的含义它其实就是此图的逆邻接表的表示。对于 V 0 V_0 V0​来说它有两个顶点 V 1 V_1 V1​和 V 2 V_2 V2​的入边。因此 V 0 V_0 V0​的firstin指向顶点 V 1 V_1 V1​的边表结点中headvex为0的结点如上图右图中的①。接着由入边结点的headlink指向下一个入边顶点 V 2 V_2 V2​如图中的②。对于顶点 V 1 V_1 V1​,它有一个入边顶点 V 2 V_2 V2​所以它的firstin指向顶点 V 2 V_2 V2​的边表结点中headvex为1的结点如图中的③。顶点 V 2 V_2 V2​和 V 3 V_3 V3​也是同样有一个入边顶点如图中④和⑤。 十字链表的好处就是因为把邻接表和逆邻接表整合在了一起 这样既容易找到以 V 1 V_1 V1​为尾的弧也容易找到以 V 1 V_1 V1​为头的弧因而容易求得顶点的出度和入度。而且它除了结构复杂一点外其实创建图算法的时间复杂度是和邻接表相同的因此在有向图的应用中十字链表是非常好的数据结构模型。 四、邻接多重表 邻接多重表是无向图的另一种链式存储结构。 在邻接表中容易求得顶点和边的各种信息但在邻接表中求两个顶点之间是否存在边而对边执行删除等操作时需要分别在两个顶点的边表中遍历效率较低。比如下图中若要删除左图的 ( V 0 , V 2 ) (V_0,V_2) (V0​,V2​) 这条边需要对邻接表结构中右边表的阴影两个结点进行删除操作显然这是比较烦琐的。 重新定义的边表结点结构如下表所示。 其中ivex和jvex是与某条边依附的两个顶点在顶点表中下标。ilink 指向依附顶点ivex的下一条边jlink 指向依附顶点jvex的下一条边。这就是邻接多重表结构。 每个顶点也用一一个结点表示它由如下所示的两个域组成。 其中data 域存储该顶点的相关信息firstedge 域指示第一条依附于该顶点的边。 我们来看结构示意图的绘制过程理解了它是如何连线的也就理解邻接多重表构造原理了。如下图7所示左图告诉我们它有4个顶点和5条边显然我们就应该先将4个顶点和5条边的边表结点画出来。 我们开始连线如图首先连线的①②③④就是将顶点的firstedge指向一条边顶点下标要与ivex的值相同,这很好理解。接着由于顶点 V 0 V_0 V0​的 ( V 0 , V 1 ) (V_0,V_1) (V0​,V1​) 边的邻边有 ( V 0 , V 3 ) (V_0,V_3) (V0​,V3​) 和 ( V 0 , V 2 ) (V_0,V_2) (V0​,V2​)。 因此⑤⑥的连线就是满足指向下一条依附于顶点 V 0 V_0 V0​的边的目标注意ilink指向的结点的jvex一定要和它本身的ivex的值相同。同样的道理连线⑦就是指 ( V 1 , V 0 ) (V_1,V_0) (V1​,V0​) 这条边它是相当于顶点 V 1 V_1 V1​指向 ( V 1 , V 2 ) (V_1,V_2) (V1​,V2​) 边后的下一条。 V 2 V_2 V2​有三条边依附所以在③之后就有了⑧⑨。连线④的就是顶点 V 3 V_3 V3​在连线④之后的下一条边。 左图一共有5条边所以右图有10条连线完全符合预期。 到这里可以明显的看出邻接多重表与邻接表的差别仅仅是在于同一条边在邻接表中用两个结点表示而在邻接多重表中只有一个结点。 这样对边的操作就方便多了若要删除左图的 ( V 0 , V 2 ) (V_0,V_2) (V0​,V2​) 这条边只需要将右图的⑥⑨的链接指向改为NULL即可。 五、边集数组 边集数组是由两个一维数组构成。一个是存储顶点的信息;另一个是存储边的信息这个边数组每个数据元素由一条边的起点下标(begin)、 终点下标(end)和权(weight)组成如下图所示。显然边集数组关注的是边的集合在边集数组中要查找一个顶点的度需要扫描整个边数组效率并不高。因此它更适合对边依次进行处理的操作而不适合对顶点相关的操作。
图的遍历 图的遍历是和树的遍历类似我们希望从图中某一顶点出发访遍图中其余顶点且使每一个顶点仅被访问一次 这一过程就叫做图的遍历(Traversing Graph)。 对于图的遍历来通常有两种遍历次序方案:它们是深度优先遍历和广度优先遍历。 一、深度优先遍历 深度优先遍历(Depth First Search)也有称为深度优先搜索简称为DFS。 1、DFS算法 深度优先搜索类似于树的先序遍历。如其名称中所暗含的意思一样这种搜索算法所遵循的搜索策略是尽可能“深”地搜索一个图。它的基本思想如下:首先访问图中某一起始顶点v然后由v出发访问与v邻接且未被访问的任一顶点 w 1 w_1 w1​再访问与 w 1 w_1 w1​邻接且未被访问的任一顶点…重复上述过程。当不能再继续向下访问时依次退回到最近被访问的顶点若它还有邻接顶点未被访问过则从该点开始继续上述搜索过程直至图中所有顶点均被访问过为止。 般情况下其递归形式的算法十分简洁算法过程如下: bool visited[MAX_VERTEX_NUM]; //访问标记数组 /从顶点出发深度优先遍历图G/ void DFS(Graph G, int v){int w;visit(v); //访问顶点visited[v] TRUE; //设已访问标记//FirstNeighbor(G,v):求图G中顶点v的第一个邻接点若有则返回顶点号否则返回-1。//NextNeighbor(G,v,w):假设图G中顶点w是顶点v的一个邻接点返回除w外顶点vfor(w FirstNeighbor(G, v); w0; wNextNeighor(G, v, w)){if(!visited[w]){ //w为u的尚未访问的邻接顶点DFS(G, w);}} } /对图进行深度优先遍历/ void DFSTraverse(MGraph G){int v; for(v0; vG.vexnum; v){visited[v] FALSE; //初始化已访问标记数据}for(v0; vG.vexnum; v){ //从v0开始遍历if(!visited[v]){DFS(G, v);}} }以下面这个无向图为例 其深度优先遍历的结果为 a b d e h c f g abdehcfg abdehcfg 2、DFS算法的性能分析 DFS算法是一个递归算法需要借助一个递归工作栈故其空间复杂度为 O ( V ) O(V) O(V)。 对于n个顶点e条边的图来说邻接矩阵由于是二维数组要查找每个顶点的邻接点需要访问矩阵中的所有元素因此都需要 O ( V 2 ) O(V^2) O(V2)的时间。而邻接表做存储结构时找邻接点所需的时间取决于顶点和边的数量所以是 O ( V E ) O(VE) O(VE)。 显然对于点多边少的稀疏图来说邻接表结构使得算法在时间效率上大大提高。 对于有向图而言由于它只是对通道存在可行或不可行算法上没有变化是完全可以通用的。 3、深度优先的生成树和生成森林 深度优先搜索会产生一棵深度优先生成树。 当然这是有条件的即对连通图调用DFS才能产生深度优先生成树否则产生的将是深度优先生成森林如下图所示。基于邻接表存储的深度优先生成树是不唯一的 。
二、广度优先遍历 广度优先遍历(Breadth First Search)又称为广度优先搜索简称BFS。 1、BFS算法 如果说图的深度优先遍历类似树的前序遍历那么图的广度优先遍历就类似于树的层序遍历了。 广度优先搜索是一种分层的查找过程每向前走一步可能访问一批顶点不像深度优先搜索那样有往回退的情况因此它不是一个递归的算法。为了实现逐层的访问算法必须借助一个辅助队列以记忆正在访问的顶点的下一层顶点。 以下是广度优先遍历的代码 /邻接矩阵的广度遍历算法/ void BFSTraverse(MGraph G){int i, j;Queue Q;for(i 0; iG,numVertexes; i){visited[i] FALSE;}InitQueue(Q); //初始化一辅助用的队列for(i0; iG.numVertexes; i){//若是未访问过就处理if(!visited[i]){vivited[i] TRUE; //设置当前访问过visit(i); //访问顶点EnQueue(Q, i); //将此顶点入队列//若当前队列不为空while(!QueueEmpty(Q)){DeQueue(Q, i); //顶点i出队列//FirstNeighbor(G,v):求图G中顶点v的第一个邻接点若有则返回顶点号否则返回-1。//NextNeighbor(G,v,w):假设图G中顶点w是顶点v的一个邻接点返回除w外顶点vfor(jFirstNeighbor(G, i); j0; jNextNeighbor(G, i, j)){//检验i的所有邻接点if(!visited[j]){visit(j); //访问顶点jvisited[j] TRUE; //访问标记EnQueue(Q, j); //顶点j入队列}}}}} }以下面这个无向图为例 其广度优先遍历的结果为 a b c d e f g h abcdefgh abcdefgh。 2、BFS算法性能分析 无论是邻接表还是邻接矩阵的存储方式BFS 算法都需要借助一个辅助队列Q, n个顶点均需入队一次在最坏的情况下空间复杂度为 O ( V ) O(V) O(V)。 采用邻接表存储方式时每个顶点均需搜索一次(或入队一次) 在搜索任一顶点的邻接点时每条边至少访问一次算法总的时间复杂度为 O ( V E ) O(V E) O(VE)。采用邻接矩阵存储方式时查找每个顶点的邻接点所需的时间为 O ( V ) O(V) O(V)故算法总的时间复杂度为 O ( V 2 ) O(V^2) O(V2)。 注意图的邻接矩阵表示是唯一的但对于邻接表来说若边的输入次序不同生成的邻接表也不同。因此对于同样一个图基于邻接矩阵的遍历所得到的DFS序列和BFS序列是唯一的基于邻接表的遍历所得到的DFS序列和BFS序列是不唯一的。 三、图的遍历与图的连通性 图的遍历算法可以用来判断图的连通性。 对于无向图来说若无向图是连通的则从任一结点出发 仅需一次遍历就能够访问图中的所有顶点若无向图是非连通的则从某一个顶点出发一次遍历只能访问到该顶点所在连通分量的所有顶点而对于图中其他连通分量的顶点则无法通过这次遍历访问。对于有向图来说若从初始点到图中的每个顶点都有路径则能够访问到图中的所有顶点否则不能访问到所有顶点。 故在BFSTraverse ()或DFSTraverse ()中添加了第二个for循环再选取初始点继续进行遍历以防止一次无法遍历图的所有顶点。对于无向图上述两个函数调用BFS (G,i)或DFS(G,i)的次数等于该图的连通分量数而对于有向图则不是这样因为一个连通的有向图分为强连通的和非强连通的它的连通子图也分为强连通分量和非强连通分量非强连通分量一次调用BFS (G, i)或DFS (G, i)无法访问到该连通分量的所有顶点。 如下图所示为有向图的非强连通分量。
最小生成树 一个连通图的生成树是一个极小的连通子图它含有图中全部的顶点但只有足以构成一棵树的 n − 1 n-1 n−1条边若砍去它的一条边则会使生成树变成非连通图若给它增加一条边则会形成图中的一条回路。对于一个带权连通无向图 G ( V , E ) G(V, E) G(V,E)生成树不同其中边的权值之和最小的那棵生成树构造连通网的最小代价生成树称为G的最小生成树(Minimum-Spanning-Tree, MST)。 构造最小生成树有多种算法但大多数算法都利用了最小生成树的下列性质假设 G ( V , E ) G(V, E) G(V,E)是一个带权连通无向图 U U U是顶点集 V V V的一个非空子集。若 ( u , v ) (u,v) (u,v)是一条具有最小权值的边其中 u ∈ U , v ∈ V − U u∈U,v∈V-U u∈U,v∈V−U则必存在一棵包含边 ( u , v ) (u, v) (u,v)的最小生成树。 基于该性质的最小生成树算法主要有Prim算法和Kruskal算法它们都基于贪心算法的策略。 下面介绍一个通用的最小生成树算法 GENERIC_MST(G){TNULL;while T 未形成一棵生成树;do 找到一条最小代价边(u, v)并且加入T后不会产生回路;TT U (u, v); }通用算法每次加入一条边以逐渐形成一棵生成树下面介绍两种实现上述通用算法的途径。 一、普里姆Prim算法 Prim算法构造最小生成树的过程如下图所示。初始时从图中任取一顶点(如顶点加入树T此时树中只含有一个顶点之后选择一个与当前T中顶点集合距离最近的顶点并将该顶点和相应的边加入T每次操作后T中的顶点数和边数都增1。以此类推直至图中所有的顶点都并入T得到的T就是最小生成树。此时T中必然有n-1条边。 通俗点说就是从一个顶点出发在保证不形成回路的前提下每找到并添加一条最短的边就把当前形成的连通分量当做一个整体或者一个点看待然后重复“找最短的边并添加”的操作。 Prim算法的步骤如下 假设 G { V , E } G {V, E} G{V,E}是连通图其最小生成树 T ( U , E T ) T(U, E_T) T(U,ET​) E T E_T ET​是最小生成树中边的集合。 初始化向空树 T ( U , E T ) T(U, E_T) T(U,ET​)中添加图 G ( V , E ) G(V, E) G(V,E)的任一顶点 u 0 u_0 u0​使 U { u 0 } U{u_0} U{u0​} E T N U L L E_TNULL ET​NULL。 循环(重复下列操作直至 U V UV UV)从图 G G G中选择满足 { ( u , v ) ∣ u ∈ U , v ∈ V − U } {(u, v)|u∈U, v∈V-U} {(u,v)∣u∈U,v∈V−U}且具有最小权值的边 ( u , v ) (u,v) (u,v),加入树 T T T置 U U ∪ { v } UU∪{v} UU∪{v} E T E T U { ( u , v ) } E_T E_TU{(u, v)} ET​ET​U{(u,v)}。 额不得不说这样理解起来有点抽象为了能描述这个算法我们先构造一个邻接矩阵如下图的右图所示。
于是普里姆(Prim) 算法代码如下左侧数字为行号。其中INFINITY为权值极大值不妨设65535MAXVEX 为顶点个数最大值此处大于等于9即可。 /Prim算法生成最小生成树/ void MiniSpanTree_Prim(G){int min, i, j, k;int adjvex[MAXVEX]; //保存相关顶点下标int lowcost[MAXVEX]; //保存相关顶点间边的权值lowcost[0] 0; //初始化第一个权值为0即v0加入生成树//lowcost的值为0在这里就是此下标的顶点已经加入生成树adjvex[0] 0; //初始化第一个顶点下标为0for(i1; iG.numVertexes; i){lowcost[i] G.arc[0][i]; //将v0顶点与之组成边的权值存入数组adjvex[i] 0; //初始化都为v0的下标}for(i1; iG.numVertexes; i){min INFINITY; //初始化最下权值为∞通常设置一个不可能的很大的数字j 1; k 0;//循环全部顶点while(j G.numVertexes){//如果权值不为0且权值小于minif(lowcost[j] ! 0 lowcost[j] min){min lowcost[j]; //则让当前权值成为最小值k j; //将当前最小值的下标存入k}j;}print((%d, %d), adjvex[k], k); //打印当前顶点边中权值的最小边for(j1; jG.numvertexes; j){//若下标为k顶点各边权值小于此前这些顶点未被加入生成树权值if(lowcost[j] ! 0 G.arc[k][j] lowcost[j]){lowcost[j] G.arc[k][j]; //将较小权值存入lowcostadjvex[j] k; //将下标为k的顶点存入adjvex}}} }由算法代码中的循环嵌套可得知此算法的时间复杂度为 O ( n 2 ) O(n^2) O(n2)。 二、克鲁斯卡尔Kruskal算法 与Prim算法从顶点开始扩展最小生成树不同Kruskal 算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法。 Kruskal算法构造最小生成树的过程如下图所示。初始时为只有n个顶点而无边的非连通图 T V , T {V, {}} TV,每个顶点自成一个连通分量然后按照边的权值由小到大的顺序不断选取当前未被选取过且权值最小的边若该边依附的顶点落在T中不同的连通分量上则将此边加入 T T T否则舍弃此边而选择下一条权值最小的边。以此类推直至 T T T中所有顶点都在一个连通分量上。 算法思路 我们可以直接就以边为目标去构建因为权值是在边上直接去找最小权值的边来构建生成树也是很自然的想法只不过构建时要考虑是否会形成环路而已。此时我们就用到了图的存储结构中的边集数组结构。以下是edge边集数组结构的定义代码 /对边集数组Edge结构的定义/ typedef struct{int begin;int end;int weight; }Edge;我们将下面左图的邻接矩阵通过程序转化为右图的边集数组并且对它们按权值从小到大排序。 于是Kruskal算法代码如下左侧数字为行号。其中MAXEDGE为边数量的极大值此处大于等于15即可MAXVEX为顶点个数最大值此处大于等于9即可。 /Kruskar算法生成最小生成树/ void MiniSpanTree_Kruskal(MGraph G){int i, n, m;Edge edges[MAXEDGE]; //定义边集数组int parent[MAXVEX]; //定义一数组用来判断边与边是否形成环路/此处省略将邻接矩阵G转化为边集数组edges并按照权由小到大排序的代码/for(i0; iG.numVertexes; i){parent[i] 0; //初始化数组为0}for(i0; iG.numVertexes; i){n Find(parent, edges[i].begin);m Find(parent, edge[i],end);/假如n与m不等说明此边没有与现有生成树形成环路/if(n ! m){/将此边的结尾顶点放入下标为起点的parent中表示此顶点已经在生成树集合中/parent[n] m;printf((%d, %d, %d), edges[i].begin, edges[i].end, edges[i].weight);}} }/查找连线顶点的尾部下标/ int Find(int *parent, int f){while(parent[f] 0){f parent[f];}return f; }此算法的Find函数由边数e决定时间复杂度为 O ( l o g e ) O(loge) O(loge)而外面有一个for循环e次。所以克鲁斯卡尔算法的时间复杂度为 O ( e l o g e ) O(eloge) O(eloge)。 对比两个算法克鲁斯卡尔算法主要是针对边来展开边数少时效率会非常高所以对于稀疏图有很大的优势而普里姆算法对于稠密图即边数非常多的情况会更好一些。 最短路径 在网图和非网图中最短路径的含义是不同的。由于非网图它没有边上的权值所谓的最短路径其实就是指两顶点之间经过的边数最少的路径而对于网图来说最短路径是指两顶点之间经过的边上权值之和最少的路径并且我们称路径上的第一个顶点是源点最后一个顶点是终点。 一、迪杰斯特拉( Dijkstra )算法 Dijkstra算法用于构建单源点的最短路径—即图中某个点到任何其他点的距离都是最短的。例如构建地图应用时查找自己的坐标离某个地标的最短距离。可以用于有向图但是不能存在负权值。
我们以上图为例通俗点说这个迪杰斯特拉(Dijkstra) 算法它并不是一下子求出了 v 0 v_0 v0​到 v 8 v_8 v8​的最短路径而是一步步求出它们之间顶点的最短路径过程中都是基于已经求出的最短路径的基础上求得更远顶点的最短路径最终得到你要的结果。 Dijkstra算法设置一个集合S记录已求得的最短路径的顶点。 在构造的过程中还设置了个辅助数组: dist[]记录从源点 v 0 v_0 v0​到其他各顶点当前的最短路径长度它的初态为若从 v 0 v_0 v0​到 v i v_i vi​;有弧则dist[i]为弧上的权值否则置dist[i]为 ∞ ∞ ∞。 例如对图6.17中的图应用 Dijkstra算法求从顶点1出发至其余顶点的最短路径的过程如表6.1所示。算法执行过程的说明如下。 初始化集合S初始为 v 1 {v_1} v1​ v 1 v_1 v1​可达 v 2 v_2 v2​和 v 5 v_5 v5​ v 1 v_1 v1​不可达 v 3 v_3 v3​和 v 4 v_4 v4​因此dist[]数组各元素的初值依次设置为dist[2]10dist[3] ∞ ∞ ∞dist[4] ∞ ∞ ∞dist[5]5。第一轮选出最小值dist[5]将顶点 v 5 v_5 v5​并入集合 S S S,即此时已找到 v 1 v_1 v1​到 ν 5 ν_5 ν5​的最短路径。当 v 5 v_5 v5​加入 S S S后从 v 1 v_1 v1​到集合 S S S中可达顶点的最短路径长度可能会产生变化。因此需要更新dist[]数组。 v 5 v_5 v5​可达 v 2 v_2 v2​因 v 1 → v 5 → v 2 v_1→v_5→v_2 v1​→v5​→v2​的距离8比dist[2]10小更新dist[2]8 v 5 v_5 v5​可达 v 3 v_3 v3​ v 1 → v 5 → v 3 v_1→v_5→v_3 v1​→v5​→v3​的距离14更新dist[3]14 v 5 v_5 v5​可达 v 4 v_4 v4​ v 1 → v 5 → v 4 v_1→v_5→v_4 v1​→v5​→v4​的距离7更新dist[4]7。第二轮选出最小值dist[4]将顶点 ν 4 ν_4 ν4​并入集合 S S S。继续更新dist[]数组。 ν 4 ν_4 ν4​不可达 v 2 v_2 v2​dist[2]不变 v 4 v_4 v4​可达 v 3 v_3 v3​ v 1 → v 5 → v 4 → v 3 v_1→v_5→v_4→v_3 v1​→v5​→v4​→v3​的距离13比dist[3]小故更新dist[3]13。笫三轮选出最小值dist[2]将顶点 ν 2 ν_2 ν2​并入集合 S S S。继续更新dist[]数组。 v 2 v_2 v2​可达 ν 3 ν_3 ν3​ v 1 → v 5 → v 2 → v 3 v_1→v_5→v_2→v_3 v1​→v5​→v2​→v3​的距离9比dist[3]小更新dist[3]9。第四轮选出唯一最小值dist[3]将顶点 v 3 v_3 v3​并入集合 S S S此时全部顶点都已包含在 S S S中。 显然Dijkstra 算法也是基于贪心策略的。使用邻接矩阵或者带权的邻接表表示时时间复杂度为 O ( V 2 ) O(V^2) O(V2)。 人们可能只希望找到从源点到某个特定顶点的最短路径但这个问题和求解源点到其他所有顶点的最短路径一样复杂时间复杂度也为 O ( V 2 ) O(V^2) O(V2)。 二、弗洛伊德( Floyd )算法 定义一个n阶方阵序列 A ( − 1 ) , A ( 0 ) , … , A ( n − 1 ) A^{(-1)},A^{(0)},…,A^{(n-1)} A(−1),A(0),…,A(n−1)其中 A ( − 1 ) [ i ] [ j ] a r c s [ i ] [ j ] A^{(-1)}[i][j] arcs[i][j] A(−1)[i][j]arcs[i][j] A ( k ) [ i ] [ j ] M i n { A ( k − 1 ) [ i ] [ j ] , A ( k − 1 ) [ i ] [ k ] A ( k − 1 ) [ k ] [ j ] , k 0 , 1 , … , n − 1 } A^{(k)}[i][j] Min{A^{(k-1)}[i][j],A^{(k-1)}[i][k]A^{(k-1)}[k][j],k0,1,…,n-1} A(k)[i][j]Min{A(k−1)[i][j],A(k−1)[i][k]A(k−1)[k][j],k0,1,…,n−1}式中 A ( 0 ) [ i ] [ j ] A^{(0)}[i][j] A(0)[i][j]是从顶点 v i v_i vi​到 v j v_j vj​、中间顶点的序号不大于k的最短路径的长度。Floyd算法是一个迭代的过程每迭代一次在从 v i v_i vi​到 v j v_j vj​的最短路径上就多考虑了一个顶点经过 n n n次迭代后所得到的 A ( n − 1 ) [ i ] [ j ] A^{(n-1)}[i][j] A(n−1)[i][j]就是 v i v_i vi​到 v j v_j vj​的最短路径长度即方阵 A ( n − 1 ) A^{(n-1)} A(n−1)中就保存了任意一对顶点之间的最短路径长度。 上图所示为带权有向图 G G G及其邻接矩阵。算法执行过程的说明如下。 初始化方阵 A ( − 1 ) [ i ] [ j ] a r c s [ i ] [ j ] A^{(-1)}[i][j] arcs[i][j] A(−1)[i][j]arcs[i][j]。第一轮将 v 0 v_0 v0​作为中间顶点对于所有顶点 { i , j } {i, j} {i,j}如果有 A − 1 [ i ] [ j ] A − 1 [ i ] [ 0 ] A − 1 [ 0 ] [ j ] A^{-1}[i][j] A^{-1}[i][0] A^{-1}[0][j] A−1[i][j]A−1[i][0]A−1[0][j]则将 A − 1 [ i ] [ j ] A^{-1}[i][j] A−1[i][j]更新为 A − 1 [ i ] [ 0 ] A − 1 [ 0 ] [ j ] A^{-1}[i][0] A^{-1}[0][j] A−1[i][0]A−1[0][j]。有 A − 1 [ 2 ] [ 1 ] A − 1 [ 2 ] [ 0 ] A − 1 [ 0 ] [ 1 ] 11 A^{-1}[2][1] A^{-1}[2][0] A^{-1}[0][1] 11 A−1[2][1]A−1[2][0]A−1[0][1]11更新 A − 1 [ 2 ] [ 1 ] 11 A^{-1}[2][1] 11 A−1[2][1]11更新后的方阵标记为 A 0 A^0 A0。第二轮将 v 1 v_1 v1​作为中间顶点继续监测全部顶点对 { i , j } {i, j} {i,j}。有 A 0 [ 0 ] [ 2 ] A 0 [ 0 ] [ 1 ] A 0 [ 1 ] [ 2 ] 10 A^{0}[0][2] A^{0}[0][1] A^{0}[1][2] 10 A0[0][2]A0[0][1]A0[1][2]10更新后的方阵标记为 A 1 A^1 A1。第三轮将 v 2 v_2 v2​作为中间顶点继续监测全部顶点对 { i , j } {i, j} {i,j}。有 A 1 [ 1 ] [ 0 ] A 1 [ 1 ] [ 2 ] A 1 [ 2 ] [ 0 ] 9 A^{1}[1][0] A^{1}[1][2] A^{1}[2][0] 9 A1[1][0]A1[1][2]A1[2][0]9更新后的方阵标记为 A 2 A^2 A2。此时 A 2 A^2 A2中保存的就是任意顶点对的最短路径长度。 应用Floyd算法求所有顶点之间的最短路径长度的过程如下表所示。 从这个表中可以发下一些规律 可以看出矩阵中每一步中红线划掉的部分都不用考虑计算只需要计算红线外的部分节省了计算量。 Floyd算法的时间复杂度为 O ( V 3 ) O(V^3) O(V3)。不过由于其代码很紧凑且并不包含 其他复杂的数据结构因此隐含的常数系数是很小的即使对于中等规模的输入来说它仍然是相当有效的。 Floyd算法允许图中有带负权值的边但不允许有包含带负权值的边组成的回路。Floyd 算法同样适用于带权无向图因为带权无向图可视为权值相同往返二重边的有向图。 也可以用单源最短路径算法来解决每对顶点之间的最短路径问题。轮流将每个顶点作为源点并且在所有边权值均非负时运行一次 Dijkstra算法其时间复杂度为 O ( V 3 ) ∗ V O ( V 3 ) O(V^3)*V O(V^3) O(V3)∗VO(V3)。 拓扑排序 一、定义 在一个表示工程的有向图中用顶点表示活动用弧表示活动之间的优先关系这样的有向图为顶点表示活动的网我们称为AOV网( Activity On VertexNetwork)。 若用DAG图有向无环图表示一个工程其顶点表示活动用有向边 V i , V j V_i, V_j Vi​,Vj​表示活动 V i V_i Vi​必须先于活动 V j V_j Vj​进行的这样一种关系。在AOV网中活动 V i V_i Vi​是活动 V j V_j Vj​的直接前驱活动 V j V_j Vj​是活动 V i V_i Vi​的直接后继这种前驱和后继关系具有传递性且任何活动 V i V_i Vi​不能以它自己作为自己的前驱或后继。 设 G ( V , E ) G(V,E) G(V,E)是一个具有n个顶点的有向图 V V V中的顶点序列 V 1 , V 2 , … V n V_1, V_2, … V_n V1​,V2​,…Vn​满足若从顶点 V i V_i Vi​到 V j V_j Vj​有一条路径则在顶点序列中顶点 V i V_i Vi​必在顶点 V j V_j Vj​之前。则我们称这样的顶点序列为一个拓扑序列。 所谓拓扑排序其实就是对一个有向图构造拓扑序列的过程。每个AOV网都有一个或多个拓扑排序序列。 二、算法 对一个AOV网进行拓扑排序的算法有很多下面介绍比较常用的一种方法的步骤: ①从AOV网中选择一个没有前驱的顶点并输出。②从网中删除该顶点和所有以它为起点的有向边。③重复①和②直到当前的AOV网为空或当前网中不存在无前驱的顶点为止。如果输出顶点数少了哪怕是少了一个也说明这个网存在环(回路)不是AOV网。 上图所示为拓扑排序过程的示例。每一轮选择一个入度为0的顶点并输出然后删除该顶点和所有以它为起点的有向边最后得到拓扑排序的结果为 { 1 , 2 , 4 , 3 , 5 } {1,2, 4, 3,5} {1,2,4,3,5}。 拓扑排序算法的实现如下 bool TopologicalSort(Graph G){InitStack(S); //初始化栈存储入度为0的顶点for(int i0; iG.vexnum; i){if(indegree[i] 0){Push(S, i); //将所有入度为0的顶点进栈}}int count 0; //计数记录当前已经输出的顶点数while(!IsEmpty(S)){ //栈不空则存在入度为0的顶点Pop(S, i); //顶点元素出栈printf(%d , i); //输出顶点icount;for(pG.vertices[i].finstarc; p; pp-nextarc){//将所有i指向的顶点的入度减1并且将入度减为0的顶点压入栈Sv p-adjvex;if(!–indegree[v]){Push(S, v); //入度为0则入栈}}}if(count G.vexnum){return false; //输出顶点少了有向图中有回路排序失败}else{return true; //拓扑排序成功} }由于输出每个顶点的同时还要删除以它为起点的边故拓扑排序的时间复杂度为 O ( V E ) O(VE) O(VE)。 此外利用深度优先遍历也可实现拓扑排序。 用拓扑排序算法处理AOV网时应注意以下问题: ①入度为零的顶点即没有前驱活动的或前驱活动都已经完成的顶点工程可以从这个顶点所代表的活动开始或继续。 ②若一个顶点有多个直接后继则拓扑排序的结果通常不唯一但若各个顶点已经排在一个线性有序的序列中每个顶点有唯一的前驱后继关系则拓扑排序的结果是唯一的。 ③由于AOV网中各顶点的地位平等每个顶点编号是人为的因此可以按拓扑排序的结果重新编号生成AOV网的新的邻接存储矩阵这种邻接矩阵可以是三角矩阵但对于一般的图来说若其邻接矩阵是三角矩阵则存在拓扑序列反之则不一定成立。 关键路径 一、定义 拓扑排序主要是为解决一个工程能否顺序进行的问题但有时我们还需要解决工程完成需要的最短时间问题。 在带权有向图中以顶点表示事件以有向边表示活动以边上的权值表示完成该活动的开销(如完成活动所需的时间)称之为用边表示活动的网络简称AOE网。AOE网和AOV网都是有向无环图不同之处在于它们的边和顶点所代表的含义是不同的AOE网中的边有权值而AOV网中的边无权值仅表示顶点之间的前后关系。 AOE网具有以下两个性质 ①只有在某顶点所代表的事件发生后从该顶点出发的各有向边所代表的活动才能开始②只有在进入某顶点的各有向边所代表的活动都已结束时该顶点所代表的事件才能发生。 如上图的AOE网在AOE网中仅有一个入度为0的顶点称为开始顶点(源点)它表示整个工程的开始网中也仅存在一个出度为0的顶点称为结束顶点(汇点)它表示整个工程的结束。我们把路径上各个活动所持续的时间之和称为路径长度从源点到汇点具有最大长度的路径叫关键路径在关键路径上的活动叫关键活动。 完成整个工程的最短时间就是关键路径的长度即关键路径上各活动花费开销的总和。这是因为关键活动影响了整个工程的时间即若关键活动不能按时完成则整个工程的完成时间就会延长。因此只要找到了关键活动就找到了关键路径也就可以得出最短完成时间。 二、算法 在分析算法之前需要了解几个重要的参数 1.事件的最早发生时间 v e ve ve即顶点 V k V_k Vk​的最早发生时期。 2.事件的最晚发生时间 v l vl vl即顶点 V k V_k Vk​的最晚发生时间也就是每个顶点对应的事件最晚需要开始的时间超出此时间将会延误整个工期。 3.活动的最早开始时间 e e e即弧 a i a_i ai​的最早发生时间。 4.活动的最晚开始时间 l l l即弧 a i a_i ai​的最晚发生时间也就是不推迟工期的最晚开工时间。 5.一个活动 a i a_i ai​的最迟开始时间 l ( i ) l(i) l(i)和其最早开始时间 e ( i ) e(i) e(i)的差额 d ( i ) l ( i ) − e ( i ) d(i) l(i)- e(i) d(i)l(i)−e(i)它是指该活动完成的时间余量即在不增加完成整个工程所需总时间的情况下活动 a i a_i ai​可以拖延的时间。若一个活动的时间余量为零则说明该活动必须要如期完成否则就会拖延整个工程的进度所以称 l ( i ) − e ( i ) 0 l(i)- e(i) 0 l(i)−e(i)0即 l ( i ) e ( i ) l(i)e(i) l(i)e(i)的活动 a i a_i ai​是关键活动。 求关键路径的算法步骤如下: 从源点出发令 v e ( 源点 ) 0 ve(源点)0 ve(源点)0 按拓扑排序求其余顶点的最早发生时间 v e ( ) ve() ve()。从汇点出发令 v l ( 汇点 ) v e ( 汇点 ) vl(汇点) ve(汇点) vl(汇点)ve(汇点)按逆拓扑排序求其余顶点的最迟发生时间 v l ( ) vl() vl()。根据各顶点的 v e ( ) ve() ve()值求所有弧的最早开始时间 e ( ) e() e()。根据各顶点的 v l ( ) vl() vl()值求所有弧的最迟开始时间 l ( ) l() l()。求AOE网中所有活动的差额 d ( ) d() d() 找出所有 d ( ) 0 d()0 d()0的活动构成关键路径。 上图所示为求解关键路径的过程简单说明如下: 求 v e ( ) ve() ve()初始 v e ( 1 ) 0 ve(1)0 ve(1)0在拓扑排序输出顶点的过程中求得 v e ( 2 ) 3 ve(2)3 ve(2)3 v e ( 3 ) 2 ve(3)2 ve(3)2 v e ( 4 ) m a x { v e ( 2 ) 2 , v e ( 3 ) 4 } m a x { 5 , 6 } 6 ve(4)max{ve(2)2, ve(3)4} max{5, 6} 6 ve(4)max{ve(2)2,ve(3)4}max{5,6}6 v e ( 5 ) 6 ve(5) 6 ve(5)6 v e ( 6 ) m a x { v e ( 5 ) 1 , v e ( 4 ) 0 , v e ( 3 ) 3 } m a x { 7 , 8 , 5 } 8 ve(6) max{ve(5)1, ve(4)0, ve(3)3} max{7, 8, 5} 8 ve(6)max{ve(5)1,ve(4)0,ve(3)3}max{7,8,5}8。求 v l ( ) vl() vl()初始 v l ( 6 ) 8 vl(6)8 vl(6)8在逆拓扑排序出栈过程之中求得 v l ( 5 ) 7 vl(5)7 vl(5)7 v l ( 4 ) 6 vl(4)6 vl(4)6 v l ( 3 ) m i n { v l ( 4 ) − 4 , v l ( 6 ) − 3 } m i n { 2 , 5 } 2 vl(3)min{vl(4)-4, vl(6)-3} min{2, 5}2 vl(3)min{vl(4)−4,vl(6)−3}min{2,5}2 v l ( 2 ) m i n { v l ( 5 ) − 3 , v l ( 4 ) − 2 } m i n { 4 , 4 } 4 vl(2)min{vl(5)-3,vl(4)-2}min{4,4}4 vl(2)min{vl(5)−3,vl(4)−2}min{4,4}4 v l ( 1 ) vl(1) vl(1)必然为 0 0 0而无需再求。弧的最早开始时间 e ( ) e() e()等于该弧的起点的顶点的 v e ( ) ve() ve()求得结果如上表所示。弧的最迟开始时间 l ( i ) l(i) l(i)等于该弧的终点的顶点的 v l ( ) vl() vl()减去该弧持续的时间求得结果如上表所示。根据 l ( i ) − e ( i ) 0 l(i)-e(i)0 l(i)−e(i)0的关键活动得到的关键路径为 ( v 1 , v 3 , v 4 , v 6 ) (v_1,v_3,v_4,v_6) (v1​,v3​,v4​,v6​)。 对于关键路径需要注意以下几点: ①关键路径上的所有活动都是关键活动它是决定整个工程的关键因素因此可通过加快关键活动来缩短整个工程的工期。但也不能任意缩短关键活动因为一旦缩短到一定的程度该关键活动就可能会变成非关键活动。 ②网中的关键路径并不唯一 且对于有几条关键路径的网只提高一条关键路径上的关键活动速度并不能缩短整个工程的工期只有加快那些包括在所有关键路径上的关键活动才能达到缩短工期的目的。 总结 图是计算机科学中非常常用的一类数据结构同时也是最复杂的数据结构了对它的学习涉及到顺序表、链表、栈、队列、树等之前学的几乎所有数据结构所以学习图之前要对这几种数据结构都要有所了解才行。 附录 上文链接 数据结构树 下文链接 数据结构查找 专栏 数据结构专栏 参考资料 1、严蔚敏、吴伟民《数据结构C语言版》 2、程杰《大话数据结构》 3、王道论坛《数据结构考研复习指导》 4、托马斯·科尔曼等人《算法导论》