第8章 图电子课件

第8章图本章讲解图。要求理解图的基本概念；掌握图的存储结构；掌握图的遍历；掌握最小生成树相关的Prim算法和Kruskal算法；掌握求最短路径相关的Dijkstra算法和Floyd算法；理解拓扑排序；灵活应用图。到古镇游最喜欢点石磨豆花这道菜了，配上调料碟子，以及其他小吃和米饭，一桌子还是挺丰盛的又不浪费。如果把桌子上的碗、盘、碟看作顶点，把吃货们在用餐时筷子夹菜的轨迹当作画边，其实就是在编织图。提纲8.1图基本概念8.2图存储结构8.3图遍历8.4生成树和最小生成树8.5最短路径8.6拓扑排序8.7关键路径8.8图应用8.9图学习总结8.1图基本概念图在日常生活中常见，如城市轨道交通图、高德导航地图、卫星轨道图、工程项目进度图、校园地理图，等等。不同于前面介绍的线性表和树，图的逻辑结构是多对多的关系。8.1图基本概念定义图G（Graph）由两个集合V（Vertex）和E（Edge）组成，记为G=(V，E)。V是顶点的有限集合，记为V(G)。E是连接V中两个不同顶点（顶点对）的边的有限集合，记为E(G)。8.1图基本概念顶点集V={v0,v1,v2,v3,v4,v5,v6,v7,v8}，边集E={(v0,v1),(v0,v2),(v1,v2)...(v6,v8),(v7,v8)}，其中边上的数字代表该边的权值。8.1图基本概念2.分类图分为无向图和有向图2大类。8.1图基本概念基本术语邻接点：在一个无向图中，若存在一条边(i，j)，则称顶点i和顶点j为该边的两个端点，它们互为邻接点。出边：在一个有向图中，若存在一条边<i,j>，则称此边是顶点i的1条出边。入边：在一个有向图中，若存在一条边<i,j>，则称此边是顶点j的1条入边。起点：在一个有向图中，若存在一条边<i,j>，则称i为起点。终点：在一个有向图中，若存在一条边<i,j>，则称j为终点。顶点的度：在无向图中，顶点所连接的边数。8.1图基本概念入度：在有向图中，以顶点j为终点的入边的数目。出度：在有向图中，以顶点i为起点的出边的数目。完全无向图：图中每2个顶点之间都存在着1条边。含有n个顶点的完全无向图有n(n-1)/2条边。如图8.3（1）所示。完全有向图：图中每2个顶点之间都存在着方向相反的2条边。含有n个顶点的完全有向图包含有n(n-1)条边。如图8.3（2）所示。8.1图基本概念稠密图：1个图接近完全图。稀疏图：1个图含有较少的边数（即无向图有e<<n(n-1)/2，有向图有e<<n(n-1)）。子图：设有两个图G=(V，E)和G'=(V'，E')，若V'是V的子集，且E'是E的子集，则称G'是G的子图。如图8.4所示。8.1图基本概念路径：在一个图G=(V，E)中，从顶点i到顶点j的一条路径是一个顶点序列(i，i1，i2，…，im，j)，若此图G是无向图，则边(i，i1)，(i1，i2)，…，(im-1，im)，(im，j)属于E(G)；若此图是有向图，则<i，i1>，<i1，i2>，…，<im-1，im>，<im，j>属于E(G)。路径长度：是指一条路径上经过的边的数目。简单路径：若一条路径上除开始点和结束点可以相同其余顶点均不相同的路径。如图8.5所示。8.1图基本概念回路或环：1条路径上的开始点与结束点为同一个顶点的路径。简单回路或简单环：开始点与结束点相同的简单路径。如图8.6所示。连通的：在无向或有向图G中，若从顶点i到顶点j有路径，则i和j是连通的。连通图和非连通图：若图G中任意两个顶点都连通，则称G为连通图，否则称为非连通图。连通分量：无向图G中的极大连通子图。显然，任何连通图的连通分量只有一个即本身，而非连通图有多个连通分量。8.1图基本概念强连通图：若有向图G中的任意两个顶点i和j都连通，即从顶点i到顶点j和从顶点j到顶点i都存在路径，则称图G是强连通图。强连通分量：有向图G中的极大强连通子图。显然，强连通图只有1个强连通分量即本身，非强连通图有多个强连通分量。一般地单个顶点自身就是一个强连通分量。如图8.6所示。8.1图基本概念权：图中每一条边都可以附有一个对应的数值。权可以表示从一个顶点到另一个顶点的距离或花费的代价。网或带权图：边上带有权的图。如图8.7所示。8.1图基本概念

8.2图存储结构图的存储结构分为顺序存储结构和链式存储结构，前者为邻接矩阵，后者为邻接表。8.2.1邻接矩阵

8.2.1邻接矩阵【思考与练习8.2】写出图8.9所示的1个带权有向图的邻接矩阵。答：

8.2.1邻接矩阵图的邻接矩阵类MatGraph描述8.2.1邻接矩阵【算法8.3】1个含有n个顶点e条边的图采用邻接矩阵g存储，设计以下算法：（1）若图为无向图，求每个顶点的度。（2）若图为有向图，求每个顶点的出度和入度。思路：（1）对于无向图，用1个计数器统计邻接矩阵某1行的非零元素个数。（2）对于有向图，统计邻接矩阵某1行的非零元素个数即得出度；统计邻接矩阵某1列的非零元素个数即得入度。代码见算法8.38.2.2邻接表

8.2.2邻接表【思考与练习8.3】画出下图所示的无向图的邻接表，并指出顶点b的度。答：

8.2.2邻接表图的邻接表的表头节点类VNode描述图的邻接表的边节点类ArcNode描述图的邻接表类AdjGraph描述8.2.2邻接表【算法8.6】1个含有n个顶点e条边的图采用邻接表存储，设计以下算法：（1）若图为无向图，求每个顶点的度。（2）若图为有向图，求每个顶点的出度和入度。思路：（1）对于无向图，某个顶点的度就是该顶点为头节点的单链表的节点个数。通过遍历单链表并计数可以得到。（2）对于有向图，某个顶点的出度就是该顶点为头节点的单链表的节点个数；某个顶点的入度就是该顶点在单链表组（不含头节点）中出现的次数。通过遍历和比较以及计数可以得到。代码见算法8.68.3图遍历从给定图中任意指定的顶点（称为初始点）出发，按照某种搜索方法沿着图的边访问图中的所有顶点，使每个顶点仅被访问1次，这个过程称为图遍历。图的遍历分为深度优先搜索/遍历（DFS，DepthFirstSearch）和广度优先搜索/遍历(BFS，BreadthFirstSearch)。8.3图遍历举例：上课之前，课代表要将手上的一摞作业本发给包含自己在内的每个同学，这个过程实质上课代表在进行遍历，全班同学构成了图的顶点，课代表对所有顶点进行了访问且只访问了1次。8.3.1深度优先遍历（1）首先访问初始顶点v。（2）选择1个与顶点v邻接且没被访问过的顶点w，再从w出发进行深度优先搜索。（3）递归上述过程，直到所有顶点遍历完。8.3.1深度优先遍历

8.3.1深度优先遍历【算法8.8】图G采用邻接表存储，设计1个深度优先遍历算法。思路：同算法8.7。只是将邻接矩阵换成了邻接表。代码见算法8.88.3.2广度优先遍历（1）访问起始点v。（2）访问顶点v的所有未被访问过的邻接点v1、v2、…、vt。（3）再按照v1、v2、…、vt的次序，访问每1个顶点的所有未被访问过的邻接点。（4）依次类推，直到图中所有顶点都被访问过为止。8.3.2广度优先遍历【算法8.9】图G采用邻接矩阵存储，设计1个广度优先遍历算法。思路：与二叉树层次遍历类同，图的广度优先遍历也可以借助1个队列用非递归算法实现。（1）访问起始顶点v，置visited[v]=1，将v入队列qu。（2）若队列非空，则出队列。（3）访问以出队列元素所在行的所有非0非∞且visited标志为0的元素，置它们的visited标志为1，将它们入队列qu。（4）重复（2）、（3），直到队列为空。代码见算法8.98.3.2广度优先遍历【算法8.10】图G采用邻接表存储，设计1个广度优先遍历算法。思路：（1）访问起始顶底v，置visited[v]=1，将v入队列qu。（2）若队列非空，则出队列。（3）访问以出队列为头节点的单链表中visited标志为0的所有节点，置它们的visited标志为1，将它们入队列qu。（4）重复（2）、（3），直到队列为空。代码见算法8.108.4生成树和最小生成树通常生成树是针对无向图的，最小生成树是针对带权无向图的。8.4.1生成树和最小生成树基本概念1.定义1个有n个顶点的连通图的生成树是1个极小连通子图。1个带权连通图G可能有多棵生成树,其中边上的权值之和最小的生成树称为图的最小生成树。8.4.1生成树和最小生成树基本概念2.特点生成树含有图中全部顶点，但只包含构成1棵树的n-1条边。如果在1棵生成树上添加1条边，必定构成一个环：因为这条边使得它依附的那两个顶点之间有了第2条路径。1个图的最小生成树不一定是唯一的。8.4.1生成树和最小生成树基本概念留意：n个顶点的无向图，含有n-1条边，不一定是生成树；少于n-1条边为非连通图；多于n-1条边则有回路。8.4.1生成树和最小生成树基本概念3.生成树生成算法1个图的生成树可以采用深度优先遍历和广度优先遍历来产生。8.4.1生成树和最小生成树基本概念【思考与练习8.4】如右图的无向图G的顶点集合按{A,B,C,D,E,F}次序存储，分别画出从所有顶点出发的深度优先遍历和广度优先遍历生成树，并写出相应的遍历序列。答：8.4.2Prim算法Prim算法是选顶点法。每次在U和V-U两个集合之间产生的割集中选最小边，再将该边在V-U中的顶点加入U,直到U=V或者V-U为空。8.4.2Prim算法【思考与练习8.5】如图8.18所示的带权无向图及其最小生成树，请简明给出Prim算法求解的过程。答：Prim算法不断扩充U，扩充次序为AGBCDEF。8.4.2Prim算法【算法8.11】从起点v出发求图的最小生成树的Prim算法。思路：（1）顶点v加入U。（2）在U和V-U顶点集之间的割集中，找出最小边（v,k）并修改lowcost数组和closest数组。（3）将顶点k加入U。（4）重复（2）、（3），直到全部顶点到U或者V-U为空。代码见算法8.118.4.3Kruskal算法Kruskal算法是选边法。每次从所有没被选的边中选择权值最小的边，在不构成环的情况下连接顶点，直到所有顶点相连或n-1条边选完。8.4.3Kruskal算法【思考与练习8.6】如图8.18所示的带权无向图及其最小生成树，请简明给出Kruskal算法求解的过程。答：Kruskal算法不断合并树，依次选择边（B,G），（C,D），（A,G），（E,F），（D,E），（B,C）。8.4.3Kruskal算法【算法8.12】求图的最小生成树Kruskal算法。思路：（1）置U的初值等于V（即包含有G中的全部顶点），TE的初值为空集。（2）将图G中的边按权值从小到大的顺序依次选取：若选取的边未使生成树T形成回路，则加入TE；否则舍弃，直到TE中包含n-1条边为止。（3）为了不形成回路，可以用vset顶点编号集来区别，不同时才能加边。代码见算法8.128.5最短路径在图中从某个始点出发到终点，可能存在多条路径，其中最短的路径就是最短路径。8.5最短路径举例：将军饮马，如右图所示，将军从A点出发，要到前面的一条河流饮马，再折返到B点。可以用数学证明将军在图中C点饮马再折返到B点，是最短的路径。在其它点饮马都不是最短路径，这样给将军节省了很多宝贵军事时间。8.5.1最短路径基本概念无向不带权图最短路：分支数最少的路径。如图8.22，A-E-B有向带权图最短路径：权值之和最小的路径。如图8.23，v0->v4->v38.5.2Dijkstra算法Dijkstra算法是求单源最短路径算法，即求图中某个顶点到另一个顶点的最短路径算法。思路：8.5.2Dijkstra算法举例：如图8.25所示，求顶点0到顶点6的最短路径和最短路径长度。由最后一轮的path[]:求前驱顶点：path[6]=4，path[4]=5，path[5]=2，path[2]=1，path[1]=0。逆序路径得：0->1->2->5->4->6即为所求最短路径，长度为4+1+4+1+6=16。8.5.2Dijkstra算法【算法8.13】图g中从源点v出发到其它各顶点的最短路径的Dijkstra算法。思路：（1）初始化dist[]、path[]和S[]。（2）在dist[]中找最小值和对应的索引号（顶点号）。（3）加入u后新旧路径比较（如图8.24（2）），更新dist[]和path[]。（4）求最短路径长度：遍历最后的dist[]。（5）求最短路径：1）反复path[]找前驱并加入到apath[]，直到源点v；2）逆向输出apath[]。代码见算法8.138.5.3Floyd算法Floyd算法是求多源最短路径算法，即求图中某个顶点到所有顶点的最短路径算法。思路：8.5.3Floyd算法举例：如图8.27所示1个带权有向图及其邻接矩阵，求任意2个顶点的最短距离。8.5.3Floyd算法求解过程如下面的表格：求A-1和path-18.5.3Floyd算法求A0和path0（加入顶点0）8.5.3Floyd算法求A1和path1（加入顶点1）8.5.3Floyd算法求A2和path2（加入顶点2）8.5.3Floyd算法求A3和path3（加入顶点3）由最后所求的A和path分别求最短路径长度和最短路径。例如，求顶点1到顶点0的最短路径长度和最短路径：由A3得，A3[1][0]=6。有path3得，path[1][0]=2，path[1][2]=3，path[1][3]=1（找到起点），故最短路径为1→3→2→0。8.5.3Floyd算法【算法8.14】图g中任意2个顶点的最短路径的Floyd算法。思路：（1）初始化A[][]和path[][]。（2）加入顶点k之后，比较新旧路径长度（如图8.26（1）），更新A[][]和path[][]。（3）求最短路径长度：遍历最后的A[][]。（4）求最短路径：1）反复path[][]求前驱并加到apath[]；2）逆向输出apath[]。代码见算法8.148.6拓扑排序概念设G=(V，E)是一个具有n个顶点的有向图，V中顶点序列v1、v2、…、vn称为一个拓扑序列，当且仅当该顶点序列满足下列条件：若<vi，vj>是图中的有向边或者从顶点vi到顶点vj有一条路径，则在序列中顶点vi必须排在顶点vj之前。在一个有向图G中找一个拓扑序列的过程称为拓扑排序。8.6拓扑排序对有向图的拓扑排序基本思想为：（1）从有向图中选择一个没有前驱（即入度为0）的顶点并且输出它。（2）从图中删去该顶点，并且删去从该顶点发出的全部有向边。（3）重（1）、（2），直到剩余的图中不再存在没有前驱的顶点为止。8.6拓扑排序2.举例学生修学分课程的先后顺序如表8.7所示。8.6拓扑排序用一个有向图表示，可得排课方案。拓扑排序序列不一定唯一！8.6拓扑排序【思考与练习8.7】给出图8.27有向图的全部拓扑排序序列。答：从入度为0的顶点入手，得到所有的拓扑排序序列有：041253、041523、045123、450123、401253、405123、401523。8.6拓扑排序3.算法【算法8.15】对邻接表存储的有向图G进行拓扑排序，输出拓扑排序序列。思路：（1）将入度为0的顶点入栈st。（2）出栈并输出该顶点i，同时删除顶点i的所有边（将顶点i的所有出边邻接点的入度减1）。（3）重复（1）、（2），直到栈为空。代码见算法8.158.7关键路径基本术语AOE网：若用一个带权有向图描述工程的预计进度，以顶点表示事件，有向边表示活动，边e的权c(e)表示完成活动e所需的时间（比如天数），或者说活动e持续时间。源点：AOE网中入度为0的顶点。汇点：AOE网中出度为0的顶点。关键路径：在AOE网中，从源点到汇点的所有路径中，具有最大路径长度的路径。关键活动：关键路径上的活动，或者说关键路径是由关键活动构成的。8.7关键路径留意：完成整个工程的最短时间就是网中关键路径的长度。只要找出AOE网中的全部关键活动，也就找到了全部关键路径了。源点：A汇点：I关键路径：A→B→E→F→I，A→B→E→G→I关键事件：ABEFGI8.7关键路径2.公式事件v的最早开始时间（ee）：

ee(v)=0 当v为源点时

ee(v)=MAX{ee(x)+a，ee(y)+b，ee(z)+c} 否则事件v的最迟开始时间（le）： le(v)=ee(v) 当v为汇点时 le(v)=MIN{le(x)-a，le(y)-b，le(z)-c} 否则活动a的最早开始时间e(a)：e(a)=ee(x)活动a的最迟开始时间l(a)：l(a)=le(y)-c8.7关键路径3.举例求图8.28的关键路径。求解步骤如下：（1）求出1个拓扑排序序列：ABCDEFGHI。（2）计算各事件的ee(v)：ee(A)=0ee(B)=ee(A)+c(a1)=6ee(C)=ee(A)+c(a2)=4ee(D)=ee(A)+c(a3)=5ee(E)=MAX(ee(B)+c(a4)，ee(C)+c(a5)}=MAX{7，5}=7ee(F)=ee(E)+c(a7)=16ee(G)=ee(E)+c(a8)=14ee(H)=ee(D)+c(a6)=7ee(I)=MAX{ee(F)+c(a10)，ee(G)+c(a11)，ee(H)+c(a9)}=MAX(18，18，11}=18（3）按拓扑逆序IHGFEDCBA计算各事件的le(v)：le(I)=ee(I)=18le(H)=le(I)-c(a9)=14le(G)=le(I)-c(a11)=14le(F)=le(I)-c(a10)=16le(E)=MIN(le(F)-c(a7)，le(G)-c(a8)}={7，7}=7le(D)=le(H)-c(a6)=12le(C)=le(E)-c(a5)=6le(B)=le(E)-c(a4)=6le(A)=MIN(le(B)-c(a1)，le(C)-c(a2)，le(D)-c(a3)}={0，2，7}=0（4）计算各活动的e(a)、l(a)和d(a)：活动a1：e(a1)=ee(A)=0， l(a1)=le(B)-6=0，d(a1)=0 活动a2：e(a2)=ee(A)=0， l(a2)=le(C)-4=2，d(a2)=2 活动a3：e(a3)=ee(A)=0， l(a3)=le(D)-5=7，d(a3)=7活动a4：e(a4)=ee(B)=6， l(a4)=le(E)-1=6，d(a4)=0 活动a5：e(a5)=ee(C)=4， l(a5)=le(E)-1=6，d(a5)=2 活动a6：e(a6)=ee(D)=5， l(a6)=le(H)-2=12，d(a6)=7活动a7：e(a7)=ee(E)=7， l(a7)=le(F)-9=7，d(a7)=0 活动a8：e(a8)=ee(E)=7， l(a8)=le(G)-7=7，d(a8)=0 活动a9：e(a9)=ee(H)=7， l(a9)=le(I)-4=14，d(a9)=7活动a10：e(a10)=ee(F)=16，l(a10)=le(I)-2=16，d(a10)=0 活动a11：e(a11)=ee(G)=14， l(a11)=le(I)-4=14，d(a11)=0（4）求出关键路径：关键活动有a11、a10、a8、a7、a4、a1，因此关键路径有两条：A－B－E－F－I和A－B－E－G－I。8.7关键路径4.算法【算法8.16】求邻接表存储的AOE网中关键路径的算法。思路：（1）将AOE网拓扑排序，产生拓扑排序序列。（2）按照该序列正序求出顶点的最早开始时间，存入数组ve；按照该序列逆序求出顶点的最迟开始时间，存入数组vl。（3）若ve[i]与vl[p.adjvex]-p.weight相等，则该边为关键活动。（4）求出所有关键活动构造所有关键路径。代码见算法8.168.8图应用【例8.1】图G