数据结构李秀坤图集相关算法

1、第4结构及其应用算法图论1707年出生在的巴塞尔城，岁开始发表 看到的，直到76岁。几乎每一个数学领域都可以的名字，从初等几何的线，多面体变换公式，四函数，微分方定理，几何的次方程的解法到数论中的程的方程，级数论的常数，变分学的欧拉方程，复变函数的公式等等。据统计他那不倦的一生，共写下了886本书籍和，其中分析、代数、数论占40%，几何占18%，物理和力学占28%，天文学占11%，弹道学、航海学、学等占3%。 1733年，年仅26岁的了彼得堡担任学院物理数学所，直到1766年，重回彼得堡，没有多久，完全失明。在数学上的建树很多，对著名的哥研究。七桥的解答开创了图论的2013/4/15哈工大计算

2、机科学与技术学院Slide 4-2第4结构及其应用算法哥七桥从某个陆地区域出发，是否回到出发地?一条能够经过每座桥一次且仅一次，最后2013/4/15哈工大计算机科学与技术学院Slide 4-3第4结构及其应用算法学习目标图结构是一种非线性结构，反映了数据对象之间的任意 计算机科学、数学和工程中有着非常广泛的应用。，在了解图的定义及相关的术语，掌握图的逻辑结构及其特点 ；了解图的掌握图的遍历，重点掌握图的邻接矩阵和邻接表，重点掌握图的遍历算法的实现；结构；了解图的应用，重点掌握最小生算法、最短路径算法、拓扑排序和径算法的基本思想、算法原理和实现过程。2013/4/15哈工大计算机科学与技术学院

3、Slide 4-4第4结构及其应用算法主要内容图的基本概念4.14.24.34.44.54.64.7图的结构图的遍历最小生算法最短路径算法拓扑排序算法径算法本章小结2013/4/15哈工大计算机科学与技术学院Slide 4-5第4结构及其应用算法4.1 基本定义定义1 图(Graph)图是由顶点（vertex）的有穷非空集合和顶点之间 合组成的一种数据结构，通常表示为：G = (V，E)（edge）的集其中：G表示一个图，V是图G中顶点的集合，E是图G中顶点之间 的集合。顶点表示数据对象；示数据对象之间的。v1v2v1v2v3v3v4v5v4v52013/4/15哈工大计算机科学与技术学院Sl

4、ide 4-6第4结构及其应用算法4.1 基本定义(cont.)定义1 图无：若顶点vi和vj之间的vv21没有方向，则称这条，表示为(vi,vj)。为无v3如果图的任意两个顶点之间的是无，则称该图为无。v4v5有：若顶点vi和vj之间的有方向，则称这条vv(弧)，表示为。12为有如果图的任意两个顶点之间的是有v3，则称该图为有。v4v52013/4/15哈工大计算机科学与技术学院Slide 4-7第4结构及其应用算法4.1 基本定义(cont.)无向完全图：在无无向完全图。有向完全图：在有，如果任意两个顶点之间都，则称该图为，如果任意两个顶点之间都方向相反的两条弧，则称该图为有向完全图。v1

5、v2v1v2v3v4v4v3含有n个顶点的无向完全图有多少条？含有n个顶点的有向完全图有多少条弧？2013/4/15哈工大计算机科学与技术学院Slide 4-8第4结构及其应用算法4.1 基本定义(cont.)邻接、依附定义1 图，对于任意两个顶点vi和顶点vj，在无若v1v2(vi，vj)，则称顶点vi和顶点vj相邻，互为邻接点，同时称 (vi，vj)依附于顶点vi和顶点vj。如：v2的邻接点： v1 , v3 ,v5v3v4v1v5v2在有若，对于任意两个顶点v 和顶点v ，ij有，则称顶点vi邻接到顶点vj，顶点vj邻接于顶点vi，同时称弧 依附于顶点vi和顶点vj 。如：v1邻接到v2

6、 ， v1 邻接于v4v3v4v52013/4/15哈工大计算机科学与技术学院Slide 4-9第4结构及其应用算法4.1 基本定义(cont.)定义2 度(Dgree)v1v2v2v1v3v3v5v5v4v4顶点的度：在无为D (v)。顶点的入度：在有数目，记为ID (v)；顶点的出度：在有数目，记为OD (v)。，顶点v的度是指依附于该顶点的，通常记，顶点v的入度是指以该顶点为弧头的弧的，顶点v的出度是指以该顶点为弧尾的弧的， D (v)= ID (v) + OD (v)在有2013/4/15哈工大计算机科学与技术学院Slide 4-10第4结构及其应用算法4.1 基本定义(cont.)定

7、义2 度(Dgree)v1v2v2v1v3v3v5在具有n个顶点、e条？v5v4v4G中，各顶点的度之和与的无之和的nD ( vi ) =2ei=1在具有n个顶点、e条G中，各顶点的入度之和与各顶点的的有出度之和的？与之和的？nni=1= OD ( vi ) = eID ( vi )i=12013/4/15哈工大计算机科学与技术学院Slide 4-11第4结构及其应用算法4.1 基本定义(cont.)定义3 路径（Path）和路径长度、简单简单回路G=( V, E ) 中，若一个顶点序列vp ,vi1 , vi2 , vim ,vq ，在无使得（vp ,vi1）,（vi1 ,vi2）, ,（v

8、im ,vq）E(G)，则称顶点vp路到vq有一条路径。G =( V, E )中，若一个顶点序列vp ,vi1 ,vi2 , vim ,vq ，使在有得有, ,E(G)，则称顶点vp路到vq有一条有向路径。非带带的路径长度是指此路径上的条数。的路径长度是指路径上各的权之和。简单路径：若路径上各顶点 v1,v2,.,vm 均互不相同, 则称这样的路径为简单路径。简单回路：若路径上第一个顶点 v1与最后一个顶点vm重合, 则称这样的简单路径为简单回路或环。2013/4/15哈工大计算机科学与技术学院Slide 4-12第4结构及其应用算法4.1 基本定义(cont.)定义4 图的连通性连通图与连通

9、分量顶点的连通性：在无vi与vj是连通的。连通图：如果一个无通图。, 若从顶点vi到顶点vj (ij)有路径, 则称顶点任意一对顶点都是连通的, 则称此图是连连通分量：非连通图的极大连通子图叫做连通分量。v1v2v1v1v1v4v32013/4/15哈工大计算机科学与技术学院Slide 4-13第4结构及其应用算法4.1 基本定义(cont.)定义4 图的连通性强连通图与强连通分量顶点的强连通性：在有, 若对于每一对顶点vi和vj (ij), 都一条从vi到vj和从vj到vi的有向路径,则称顶点vi与vj是强连通的。任意一对顶点都是强连通的, 则称此有强连通图：如果一个有是强连通图。强连通分量

10、:连通图的极大强连通子图叫做强连通分量v1v2v3v5v42013/4/15哈工大计算机科学与技术学院Slide 4-14第4结构及其应用算法4.1 基本定义(cont.)图的操作设图G=(V,E)，图上定义的基本操作如下：NewNode ( G )：建立一个新顶点，V=Vv DelNone ( G, v )：删除顶点v以及与之相关联的所有SetSucc ( G, v1, v2 ):增加一条，E = E(v1,v2) ,V=VDelSucc ( G, v1, v2 )：删除（v1,v2）,V不变Succ ( G, v1, v2 )：求出v的所有直接后继结点Pred ( G, v)：求出v的所有

11、直接前导结点IsEdge ( G, v1, v2 )：（v1,v2）EFirstAdjVex( G , v ): 顶点v 的第一个邻接顶点NextAdjVex( G, v, w)：顶点v 的某个邻接点w的下一个邻接顶点。2013/4/15哈工大计算机科学与技术学院Slide 4-15第4结构及其应用算法4.1 基本定义(cont.)不同逻辑结构之间的比较ABEFCDAv1v2BCv3v4v5DEF(1:1)；性结构中，数据元间仅具有线性在结构中，结点之间具有层次(1:m)；(m:n)。在图型结构中，任意两个顶点之间都可能有2013/4/15哈工大计算机科学与技术学院Slide 4-16第4结构

12、及其应用算法4.1 基本定义(cont.)不同逻辑结构之间的比较ABEFCDAv1v2BCv3v4v5DEF性结构中，元间的为前驱和后继；为双亲和孩子； 为邻接。在结构中，结点之间的在图型结构中，顶点之间的2013/4/15哈工大计算机科学与技术学院Slide 4-17第4结构及其应用算法4.2 图的结构图(一维数组）?是m:n，即任何两个顶点之间都可能是否可以采用顺序结构图的特点：顶点之间的（），无法通过位置表示这种任意的逻辑，所以，图无法采用顺序结构。如何图？考虑图的定义，图是由顶点和组成的；-顶点之间的如何顶点、如何。v1v2v1v2v3v3v5v4v5v42013/4/15哈工大计算机

13、科学与技术学院Slide 4-18第4结构及其应用算法4.2 图的结构(cont.)邻接矩阵 （Adjacency Matrix）表示（数组表示法）基本思想：用一个一维数组图中顶点的信息，用一个二维数组（称为邻接矩阵）图中各顶点之间的邻接。假设图G(V，E)有n个顶点，则邻接矩阵是一个nn的方阵，定义为：10若 ( i , j ) E 或 E否则edge i j =v2v1v2v1v3v3v4v5v4v52013/4/15哈工大计算机科学与技术学院Slide 4-19第4结构及其应用算法4.2 图的结构(cont.)邻接矩阵 （Adjacency Matrix）表示（数组表示法）无的邻接矩阵：

14、vertex=v1v2v1v2v3v4v5v1 v2 v3 v4 v5v3edge =v5v4结构特点：主对角线为 0 且一定是对称矩阵；：1. 如何求顶点vi的度？2.如何顶点 vi和 vj 之间是否？3.如何求顶点 vi的所有邻接点？2013/4/15哈工大计算机科学与技术学院Slide 4-200101010101010111001110000v1v2v3v4v5第4结构及其应用算法4.2 图的结构(cont.)邻接矩阵 （Adjacency Matrix）表示（数组表示法）有的邻接矩阵：vertex=vv12v1v2v3v4v5v1 v2 v3 v4 v5v3v4v5edge =结构特

15、点：有的邻接矩阵一定不对称吗？：1.如何求顶点vi的出度？2. 如何顶点 vi和 vj 之间是否有？3. 如何求邻接于顶点 vi的所有顶点？4. 如何求邻接到顶点 vi的所有顶点？2013/4/15哈工大计算机科学与技术学院Slide 4-210100000100000111001100110v1v2v3v4v5第4结构及其应用算法4.2 图的结构(cont.)邻接矩阵 （Adjacency Matrix）表示（数组表示法）结构定义：typedef struct VertexData verlist NumVertices;/顶点表EdgeData edgeNumVerticesNumVert

16、ices;/邻接矩阵, 可视为之间的int n, e; /图的顶点数与 MTGraph;v100010v210001v301010v400101v500110v1 v2 v3 v4 v5v1v2edge=v3vertexvv452013/4/15哈工大计算机科学与技术学院Slide 4-22v1v2v3v4v5假设图G有n个顶点e条 ，则该图的需求为O(n+n2) = O(n2) ，与 的条数e无关。第4结构及其应用算法4.2 图的结构(cont.)结构的建立算法实现的步骤：1.确定图的顶点个数n和e；2.输入顶点信息在一维数组vertex中；3. 初始化邻接矩阵；4. 依次输入每条在邻接矩阵

17、edge中；4.1 输入依附的两个顶点的序号i, j；4.2 将邻接矩阵的第i行第j列的元素值置为1；4.3 将邻接矩阵的第j行第i列的元素值置为1。v100010v210001v301010v400101v500110v1 v2 v3 v4 v5v1v2edge=v3vertexvv452013/4/15哈工大计算机科学与技术学院Slide 4-23v1v2v3v4v5第4结构及其应用算法4.2 图的结构的建立算法的实现：结构(cont.)void CreateMGragh (MTGragh *G) /建立图的邻接矩阵int i, j, k, w; cinGnGe; for (i=0; iG

18、n; i+)/1.输入顶点数和/2.读入顶点信息，建立顶点表Gvertlisti=getchar( ); for (i=0; iGn; i+)for (j=0;jGn;j+) Gedgeij=0;for (k=0; kijw;/ 输入（i,j）上的wG edgeij=w; G edgeji=w; /时间复杂度：T = O( n+ n2 +e) 。当e G.n G.e;for ( int i = 0; i G.vexlisti.vertex;/1.输入顶点个数和/2.建立顶点表/2.1输入顶点信息v2v3v4G.vexlisti.firstedge = NULL; /2.2置为空表输入,建立fo

19、r ( i = 0; i tail head weight;/3.逐条/3.1输入/3.2建立EdgeNode * p = new EdgeNode;结点结点padjvex = head;pcost = weight; /3.3设置pnext = G.vexlisttail.firstedge; G.vexlisttail.firstedge = p;p = new EdgeNode;/3.4链入第tail 号链表的前端padjvex = tail;pcost = weight;pnext = G.vexlisthead.firstedge; /链入第 head 号链表的前端G.vexlist

20、head.firstedge = p; /时间复杂度：O(2e+n)2013/4/15哈工大计算机科学与技术学院Slide 4-34第4结构及其应用算法4.2 图的结构(cont.)结构的比较邻接矩阵和邻接表图的2013/4/15哈工大计算机科学与技术学院Slide 4-35空间性能时间性能适用范围唯一性邻接矩阵O（n2）O（n2）稠密图唯一？邻接表O（n+e）O（n+e）稀疏图不唯一？第4结构及其应用算法u 十字链表(有)十字链表是有的另一种链式结构。将有的邻接表和逆邻接表结合起来的结构。在十字链表中有两种结点：u 弧结点：每一条弧的信息，用链表在一起。弧结点结构:u 顶点结点：每一个顶点的

21、信息，使用一维数组来。顶点结点结构:2013/4/15哈工大计算机科学与技术学院Slide 4-36datafirstinfirstoutivexjvexjlinkilinkinfo第4结构及其应用算法V1V2V3V4弧结点顶点结点01002V11V2220V33V42013/4/15哈工大计算机科学与技术学院Slide 4-3723323130第4结构及其应用算法BC 十字链表中既容易找到以vi为尾的弧，也容易找到以vi为头的弧，因而容易求得顶点 的出度和入度。ADFE01012345BCDEF512013/4/15哈工大计算机科学与技术学院Slide 4-385332251404A第4结构

22、及其应用算法u 邻接多重表(无)邻接多重表是无的另一种链式表示结构。和十字链表类似。邻接多重表中，每一条 用一个结点表示。在邻接多重表中有两种结点：结点：结点结构:每一条的信息，用链表在一起。uu 顶点结点：每一个顶点的信息，使用一维数组来。顶点结点结构:2013/4/15哈工大计算机科学与技术学院Slide 4-39datafirstedgemarkivexilinkjvexjlinkinfo第4结构及其应用算法V1V2V3V4V5030123401V1V223V321V4V5412013/4/15哈工大计算机科学与技术学院Slide 4-4024第4结构及其应用算法BCAD01040FE1

23、4151C232523E4F52013/4/15哈工大计算机科学与技术学院Slide 4-41D35BA第4结构及其应用算法4.3 图的搜索（遍历）1986年图灵奖获得者1939年生于西雅图。美国学智能和工程院、人。1962和1964年和博士学位。先后在普获斯坦福大学大学、斯坦福大学等工作，也曾任职于一些科学研究机构如NSF和NRC。著作很多如算法设计与分析基础 数据结构与算法自理论、语言和计算导论形式语言及其与自的John Edward HopcroftRobert Endre Tarjan普大学计算机科学系教授，1948年4月30日生于加利福尼亚州。1969年本科毕业，进入斯坦福大学研究生

24、院，1972年获得博士学位。平面图测试的高效算法 ；合并-搜索；“分摊”算法的概念；八字形树；持久性数据结 构2013/4/15哈工大计算机科学与技术学院Slide 4-42第4结构及其应用算法4.3 图的搜索（遍历） (cont.)图的遍历（图的搜索）从图中某一顶点出发，对图中所有顶点一次且仅一次。：抽象操作，可以是对结点进行的各种处理图结构的复杂性性表中，数据元素在表中的编号就是元素在序列中的位置，因而 其编号是唯一的；在树结构中，将结点按层序编号，由于树具有层次性，因而其层序编 号也是唯一的；在图结构中，任何两个顶点之间都可能后次序的，所以，顶点的编号不唯一。，顶点是没有确定的先2013

25、/4/15哈工大计算机科学与技术学院Slide 4-43第4结构及其应用算法4.3 图的搜索（遍历） (cont.)图的遍历要解决的关键在图中，如何选取遍历的起始顶点？ 解决办法：从编号小的顶点开始。从某个起点始可能到达不了所有其它顶点，怎么办？解决办法：多次调用从某顶点出发遍历图的算法。图中可能回路，且图的任一顶点都可能与其它顶点“相通”，在完某个顶点之后可能会沿着某些又回到了曾经？过的顶点。如何避免某些顶点可能会被重复解决办法：附设标志数组visitedn 。在图中，一个顶点可以和其它多个顶点相连，当这样的顶点过后，如何选取下一个要的顶点？解决办法：深度优先搜索（Depth First S

26、earch）和广度优先搜索（Breadth First Search）。2013/4/15哈工大计算机科学与技术学院Slide 4-44第4结构及其应用算法4.3 图的搜索（遍历） (cont.)深度优先遍历类似于树结构的先序遍历设图G的初态是所有顶点都“未过（False）”，在G中任选一个顶点 v 为初始出发点(源点)，则深度优先搜索可定义为:出发点 v，并将其标记为“过 （True） ”;首先然后，从 v 出发，依次与 v 相邻的顶点 w ；若 w“未过（False）”，则以 w 为新的出发点递归地进行深度优先搜索， 直到图中所有与源点 v 有路径相通的顶点（亦称从源点可到达的顶点）均被为

27、止；若此时图中仍有未被过的顶点，则另选一个“未过”的顶点作为新的搜索起点，重复上述过程，直到图中所有顶点都被 过为止。2013/4/15哈工大计算机科学与技术学院Slide 4-45第4结构及其应用算法4.3 图的搜索（遍历） (cont.)深度优先遍历示例深度优先遍历序列?入栈序列?出栈序列?v1v1v2v3v2v3v4v5v6v7v4v5v6v7栈生成森林v8v3v8遍历序列：v1v6v2v5v8v4v72013/4/15哈工大计算机科学与技术学院Slide 4-46v578v64v23v1第4结构及其应用算法4.3 图的搜索（遍历） (cont.)深度优先遍历特点：是递归的定义，是尽可能

28、对纵深方向上进行搜索，故称先深或深 度优先搜索。先深或深度优先编号。搜索过程中，根据优先编号。先深序列或DFS序列：顺序给顶点进行的编号，称为先深或深度先深搜索过程中，根据或DFS序列。生成森林（树）：顺序得到的顶点序列，称为先深序列有原图的所有顶点和搜索过程中所经过的先深搜索结果不唯一即图的DFS序列、先深编号和生成森林不唯一。的子图。2013/4/15哈工大计算机科学与技术学院Slide 4-47第4结构及其应用算法4.3 图的搜索（遍历） (cont.)深度优先遍历主算法：bool visitedNumVertices; /标记数组是全局变量int dfnNumVertices; /顶点

29、的先深编号void DFSTraverse (AdjGraph G)/主算法/ 先深搜索一邻接表表示的图G；而以邻接矩阵表示G时，算法完全相同int i , count = 1;for ( int i = 0; i G.n; i+ )visited i =False;/标志数组初始化for ( int i = 0; i G.n; i+ ) if ( ! visitedi )DFSX ( G, i ); /从顶点i 出发的一次搜索，BFSX(G, i )2013/4/15哈工大计算机科学与技术学院Slide 4-48第4结构及其应用算法4.3 图的搜索（遍历） (cont.)从一个顶点出发的一次

30、深度优先遍历算法：实现步骤：1.顶点v; visitedv=1;2. w=顶点v的第一个邻接点；3. while (w)3.1 if (w未被) 从顶点w出发递归执行该算法;3.2 w=顶点v的下一个邻接点;2013/4/15哈工大计算机科学与技术学院Slide 4-49第4结构及其应用算法4.3 图的搜索（遍历） (cont.)从一个顶点出发的一次深度优先遍历算法：void DFS1 (AdjGraph* G, int i)/以vi为出发点时对邻接表表示的图G进行先深搜索EdgeNode *p; coutadjvexif( !visited padjvex )/若vj尚未DFS1(G, pa

31、djvex); p=pnext;/则以vj为出发点先深搜索 /DFS12013/4/15哈工大计算机科学与技术学院Slide 4-50第4结构及其应用算法4.3 图的搜索（遍历） (cont.)从一个顶点出发的一次深度优先遍历算法：void DFS1 (AdjGraph* G, int i)/以vi为出发点时对邻接表表示的图G进行先深搜索EdgeNode *p; coutGvexlisti.vertex; visitedi=True; dfni=count+; p=Gvexlisti.firstedge; while( p ) if( !visited padjvex ) DFS1(G, pa

32、djvex);p=pnext;v1v0v2v3adjvexv4nextvertexfirstedge012 /DFS134顶点表2013/4/15哈工大计算机科学与技术学院Slide 4-513v0v1v2v3v4第4结构及其应用算法4.3 图的搜索（遍历） (cont.)从一个顶点出发的一次深度优先遍历算法：void DFS2(MTGraph *G, int i)v001010v110101v201011v310100v401100/以vi为出发点对邻接矩阵表示的图G进行深度优先搜索v0int j; coutGvexlisti; visiti=True; dfni=count;count +

33、;v1 v/定点vi/标记vi已2v3 v4/对vi进行编号/下一个顶点的编号for( j=0; jGn; j+ ) /依次搜索vi的邻接点if ( (Gedgeij = 1)&！visitedj ) /若vj尚未DFS2( G, j );/DFS2v1v0v2v3v42013/4/15哈工大计算机科学与技术学院Slide 4-52第4结构及其应用算法4.3 图的搜索（遍历） (cont.)广度优先遍历类似于树结构的层序遍历设图G的初态是所有顶点都“未过（False）”，在G中任选一个顶点v 为源点，则广度优先搜索可定义为:首先出发点v，并将其标记为“过（True）”;所有与v 相邻的顶点w1，w2wt；接着依次然后依次与w1，w2 wt相邻的的顶点;依次类推，直至图中所有与源点v有路相通的顶点都已 为止；此时，从v 开始的搜索结束，若G是连通的，则遍历完成；否过则在G中另选一个尚未的顶点作为新源点，继续上述搜索过程，直到G中的所有顶点均已为止。2013/4/15哈工大计算机科学与技术学院Slide 4-53第4结构及其应用算法4.3 图的搜索（遍历） (cont.)广度优先遍历示例广度优先遍历序列?入队序列?出队序列?v1v0v4v3v2遍历序列：v0v6v6v