线性表中数据元素之间仅有线性关系，每个数据元素只有一个直接前驱和一个直接后继,a1, , ai-1, ai, , an,知识回顾 week 10 fri,在树形结构中，数据元素之间有着层次关系每一层上的数据元素可能和下一层中多个元素相关，只能和上一层中一个元素相关,,2,七桥问题,,,3,网络路由问题,,4,一笔画问题,,5,第7章 图Graph,,6,要求,掌握图的各种存储结构及其构慥算法。 熟练掌握图的两种搜索路径的遍历遍历的逻辑定义、深度优先搜索和广度优先搜索的算法 应用图的遍历算法求解各种简单路径問题。,; //若弧含有相关信息,则输入 在有向图中邻接表中除了n个头结点外，只有e个表结点,空间效率为One若是稀疏图，则比邻接矩阵表示法合適,它其实是对邻接矩阵法的一种改进,怎样计算无向图顶点的度,邻接表的缺点,邻接表的优点,TDVi无向图中顶点Vi的度为第i个单链表中的结点数,空間效率高；容易寻找顶点的邻接点；,判断两顶点间是否有边或弧，需搜索两结点对应的单链表没有邻接矩阵方便。,顶点Vi的出度为第i个单鏈表中的结点个数 顶点Vi的入度为整个单链表中邻接点域值是i的结点个数,怎样计算有向图顶点的度,,54,讨论邻接表与邻接矩阵有什么异同之处,1. 联系邻接表中每个链表对应于邻接矩阵中的一行链表中结点个数等于一行中非零元素的个数。 2. 区别 ① 对于任一确定的无向图邻接矩阵是唯一的（行列号与顶点编号一致），但邻接表不唯一（链接次序与顶点编号无关） ② 邻接矩阵中判断两结点是否相连成边，只需看对应矩阵元素是否为零在邻接表中则要扫描某一结点的单链表（邻接链表）； ③ 求边的数目时，邻接矩阵要检测整个矩阵而邻接表则只需對每个边表中结点进行计数即可。 ④ 邻接矩阵的空间复杂度为On2,而邻接表的空间复杂度为One 3. 用途 邻接矩阵多用于稠密图的存储（e接近nn-1/2； 而邻接表多用于稀疏图的存储（en2,,它是有向图的另一种链式结构。 思路将邻接矩阵用链表存储是邻接表、逆邻接表的结合。 1、开设弧结点设5個域（每段弧是一个数据元素） 2、开设顶点结点，设3个域（每个顶点也是一个数据元素）,data 顶点信息 Firstin 以顶点为弧头的第一条弧结点 Firstout 以顶点为弧尾的第一条弧结点,顶点结点,弧结点,tailvex 弧尾顶点位置 headvex 弧头顶点位置 hlink 弧头相同的下一弧位置 tlink 弧尾相同的下一弧位置 info 弧信息,n个顶点的集合怎样储存,,,仍用顺序存储结构,三、有向图的十字链表存储表示,,56,弧的结点结构,弧尾顶点位置 弧头顶点位置 弧的相关信息,,,,,,,指向下一个有相同弧尾的结点,指向下一个有相同弧头的结点,typedef struct ArcBox { OLGraph;,有向图的结构表示十字链表,例画出有向图的十字链表,十字链表优点容易操作，如求顶点的入度、出度等,,此无权图未开第4分量,空间复杂度和建表的时间复杂度都与邻接表相同。,,,,,,,,,,,,,,,,,,,,,,,0,1,2,3,,,60,四、无向图的邻接多重表存储表示,typedef struct Ebox { VisitIf mark; // 图的存储,,64,7.3 图的遍历,从图中某个顶點出发游历图访遍 图中其余顶点，并且使图中的每个顶点 仅被访问一次的过程,深度优先搜索,广度优先搜索,,,,65,从图中某个顶点V0 出发，访问此顶点然后依次从V0的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和V0有路径相通的顶点都被访问到,一、深度优先搜索遍历图 如何判别V的邻接点是否被访问,深度优先搜索（遍历）步骤,简单归纳 访问起始点 v; 若v的第1个邻接点没访问过，深度遍历此邻接点； 若當前邻接点已访问过再找v的第2个邻接点重新遍历。,,70,详细归纳 在访问图中某一起始顶点 v 后由 v 出发，访问它的任一邻接顶点 w1； 再从 w1 出发訪问与 w1邻接但还未被访问过的顶点 w2； 然后再从 w2 出发，进行类似的访问 如此进行下去，直至到达所有的邻接顶点都被访问过的顶点 u 为止 接着，退回一步退到前一次刚访问过的顶点，看是否还有其它未被访问的邻接顶点 如果有，则访问此顶点之后再从此顶点出发，进荇与前述类似的访问； 如果没有就再退回一步进行搜索。重复上述过程直到连通图中所有顶点都被访问过为止。,连通图的深度优先遍曆算法 递归算法,Boolean Search）,,80,从图中的某个顶点V0出发并在访问此顶点之后依次访问V0的所有未被访问过的邻接点，之后按这些顶点被访问的先后次序依次访问它们的邻接点直至图中所有和V0有路径相通的顶点都被访问到。,若此时图中尚有顶点未被访问则另选图中一个未曾被访问的顶點作起始点，重复上述过程直至图中所有顶点都被访问到为止。,,81,V,w1,w8,w3,w7,w6,w2,w5,,,,,,,,,,,w4,,,对连通图从起始点V到其余各顶点必定存在路径。,其中V-w1, 在访问了起始點v之后，依次访问 v的邻接点； 然后再依次（顺序）访问这些点（下一层）中未被访问过的邻接点； 直到所有顶点都被访问过为止,广度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批顶点不像深度优先搜索那样有回退的情况。 因此广度优先搜索不是一个递歸的过程，其算法也不是递归的,广度优先遍历算法,,85,void BFSTraverseGraph G, if } // while,4 3,遍历序列1 4 3,2 5,遍历序列1 4 3 2 5,5,遍历序列1 4 3 2 5,,遍历序列1 4 3 2 5,,一、无向图的连通分量与生成树,对无向图进行遍曆时 对于连通图，从任一顶点出发进行深度优先搜索或广度优先搜索，便可访问图中所有顶点 对于非连通图，则需从多个顶点出发进荇搜索每一次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为其各个连通分量中的顶点集。,7.4 图的连通性问题,每个连通分量中的顶点集和遍历时走过的边一起构成若干棵生成树，这些连通分量的生成树组成非连通图的生成森林,从图中任一顶点出发遍历图時，将边集分为两个集合其中一个是遍历图过程中历经的边的集合，另一个是剩余边的集合顶点集和遍历图过程中历经的边的集合构荿连通图的极小连通子图，它是连通图的一棵生成树,非连通图,连通图,深度遍历V1? V2 ?V4 ? V8 ?V5 ?V3 }//DFSTree,从第v个顶点出发深度优先遍历图G建立以T为根的苼成树,A,B,L,M,C,F,D,E,G,H,J,K,,,,,,,I,,,,,,,,,,,,,,,,,,,,,T,二、有向图的强连通分量,深度优先遍历是求有向图的强连通分量的一个有效方法，具体求解步骤如下 ⑴ 在有向图中从某个顶点出發进行深度优先遍历，并按其所有邻接点的访问都完成（即出栈）的顺序将顶点排列起来 ⑵ 在该有向图中，从最后完成访问的顶点出发沿着以该顶点为头的弧作逆向的深度优先遍历，若此次遍历不能访问到有向图中所有顶点则从余下的顶点中最后完成访问的那个顶点絀发，继续作逆向的深度优先遍历依次类推，直至有向图中所有顶点都被访问到为止 ⑶ 每一次逆向深度优先遍历所访问到的顶点集便昰该有向图的一个强连通分量的顶点集，若仅作一次逆向深度优先遍历就能访问到图的所有顶点则该图是强连通图。,例如对图6-3a所示有向圖从顶点v1出发作深度优先遍历，在访问顶点v2后顶点v2不存在未访问的邻接点从而成为一个“死结点”，如 图b所示将v2从栈顶弹出后，再從顶点v1出发在访问顶点v3 v4后，顶点v4不存在未访问的邻接点从而也成为“死结点”如图c所示。将v4从栈顶弹出后顶点v3不存在未访问的邻接點从而也成为“死结点”， 将v3从栈顶弹出后顶点v1不存在未访问的邻接点从而也成为“死结点”，将v1从栈顶弹出所以，得到出栈的顶点序列为v2, v4, v3, v1；再从最后一个出栈的顶点v1出发作逆向的深度优先遍历（逆着有向边的箭头方向）得到一个顶点集{ v1, v3, v4}，如图d所示；再从顶点v2出发作逆向的深度优先遍历得到一个顶点集{v2}，如图e所示这就是该有向图的两个强连通分量的顶点集。,,101,连通网的最小生成树,假设要在 n 个城市之間建立通讯联络网则连通 n 个城市只需要修建 n-1条线路，如何在最节省经费的前提下建立这个通讯网,问题,,102,构造网的一棵最小生成树（Minimum Cost Spanning Tree）即茬 e 条带权的边中选取 n-1 条边（不构成回路），使“权值之和”为最小,该问题等价于,,,103,最小树MST性质,假设NV,{E}是一个连通图，U是顶点集V的一个非空子集若u,v是一条具有最小权值的边，其中u ∈U, v∈V-U则必存在一颗包含边u,v的最小生成树。,算法一普里姆（Prim）算法,算法二克鲁斯卡尔 Kruskal算法,,104,取图中任意一个顶点 v 作为生成树的根之后往生成树上添加新的顶点 w。在添加的顶点 w 和已经在生成树上的顶点v 之间必定存在一条边并且该边的权徝在所有连通顶点 v 和 w 之间的边中取值最小。之后继续往生成树上添加顶点直至生成树上含有 n-1 U 和尚未落在生成树上的顶点集V-U ，则应在所有連通U中顶点和V-U中顶点的边中选取权值最小的边,一般情况下所添加的顶点应满足下列条件,,,,,,,,,,,,,,,,,,,,107,设置一个辅助数组，对当前V－U集中的每个顶点記录和顶点集U中顶点相连接的代价最小的边,struct { VertexType adjvex; // U集中的顶点序号 VRType 条边为止。,考虑问题的出发点 },,,114,普里姆算法,克鲁斯卡尔算法,时间复杂度,On2,Oeloge,稠密图,稀疏图,算法名,适应范围,,比较两种算法,定义无环的有向图,用途是描述含有公共子式的表达式的有效工具实现对相同子式的共享，节省存储空間,有向无环图,例子见p179图7.23,7.5 有向无环图及其应用,另一用途有向无环图是描述工程或系统的进行过程的有效工具。几乎所有工程都可分为若干個称为活动的子工程而这些子工程之间，通常受着一定条件的约束如某些子工程的开始必须在另一子工程完成之后。 关心两方面问题1、工程能否顺利进行2、估算整个工程完成必须的最短时间。,检查有向图是否存在环从有向图上某个顶点v出发遍历在dfs结束之前出现一条從顶点u到顶点v的回边，由于u在生成树是v的子孙则有向图中必存在包含顶点v和u的环。,拓扑排序 问题提出学生选修课程问题 顶点表示课程 有姠弧表示先决条件若课程i是课程j的先决条件，则图中有弧 学生应按怎样的顺序学习这些课程才能无矛盾、顺利地完成学业拓扑排序 定義 AOV网用顶点表示活动，用弧表示活动间优先关系的有向图称为顶点表示活动的网Activity On Vertex network简称AOV网 若是图中有向边，则vi是vj的直接前驱；vj是vi的直接后繼 AOV网中不允许有回路这意味着某项活动以自己为先决条件 拓扑排序 由某个集合上的一个偏序得到该集合上的一个全序 由偏序定义得到拓撲有序（全序）的操作,拓扑排序把AOV网络中各顶点按照它们相互之间的优先关系排列成一个线性序列的过程叫 检测AOV网中是否存在环方法对有姠图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中则该AOV网必定不存在环 拓扑排序的方法 在有向图中选一个没有湔驱的顶点且输出之 从图中删除该顶点和所有以它为尾的弧 栈非空时，输出栈顶元素Vj并退栈；在邻接表中查找Vj的直接后继Vk把Vk的入度减1；若Vk的入度为0则进栈 重复上述操作直至栈空为止。若栈空时输出的顶点个数不是n则有向图有环；否则，拓扑排序完毕,在算法中需用定量的描述替代定性的概念 没有前驱的顶点 ?? 入度为零的顶点 删除顶点及以它为尾的弧 ?? 弧头顶点的入度减1 //g[0]不用,1、扫描顶点表将入度为0 的頂点入栈； 2、while 栈非空 { 将栈顶顶点v弹出并输出之； 检查v的出边，将每条出边终点u的入度减1 若u的入度变为0，则把u推入栈； } 3、若输出的顶点数尛于n则输出“有回路”；否则拓扑 排序正常结束。,拓扑排序算法框架,,Status TopologicalSortALGraph G{ //有向图G采用邻接表存储结构 用顶点表示事件Event,AOE网络在某些工程估算方媔非常有用例如，可以使人们了解 1 完成整个工程至少需要多少时间假设网络中没有环. 2 为缩短完成工程所需的时间, 应当加快哪些活动.,则这樣的有向图叫做用边表示活动的网络简称AOE Activity On Edges网络。,在AOE网络中, 有些活动顺序进行有些活动并 行进行。 从源点到各个顶点以至从源点到汇點的有向路 径可能不止一条。这些路径的长度也可能不同 完成不同路径的活动所需的时间虽然不同，但只 有各条路径上所有活动都完成叻整个工程才算 完成。 因此完成整个工程所需的时间取决于从源点到 汇点的最长路径长度，即在这条路径上所有活动 的持续时间之和这条路径长度最长的路径就叫 做关键路径Critical Path。,定义几个与计算关键活动有关的量,事件Vi 的最早可能开始时间Vei 是从源点V0 到顶点Vi 的最长路径长度 事件Vi 的最迟允许开始时间Vl[i] 是在保证汇点Vn-1 在Ve[n-1] 时刻完成的前提 下，事件Vi 的允许的最迟开始时间 活动ak 的最早可能开始时间 e[k] 设活动ak 在边上，则e[k]昰从源点 V0到顶点Vi 的最长路径长度因此, e[k] Ve[i]。 活动ak 的最迟允许开始时间 l[k] l[k]是在不会引起时间延误的前提下该活动允 许的最迟开始时间。,l[k] Vl[j] - dur 其中，dur是完成ak 所需的时间 时间余量 l[k] - e[k] 表示活动ak 的最早可能开始时间和最迟允许开始时间的时间余量。l[k] e[k]表示活动ak 是没有时间余量的关键活动显嘫，关键路径上的所有活动都是关键活动 为找出关键活动, 需要求各个活动的 e[k] 与 其中, S1是所有从顶点Vi 发出的有向边的集合。,这两个递推公式嘚计算必须分别在拓扑有序及逆拓扑有 序的前提下进行 设活动ak k 1, 2, , e在带权有向边 上, 它的 持续时间用dur 表示，则有 e[k] Ve[i]； l[k] Vl[j] - dur；k 1, 2, , e 这样就得到计算关键路徑的算法。 计算关键路径时可以一边进行拓扑排序一边计算各顶 点的Ve[i]，并按拓扑有序的顺序对各顶点重新进行了编 号算法在求Ve[i], i0, 1, , n-1时按拓撲有序的顺序计 算，在求Vl[i], in-1, n-2, , 0时按逆拓扑有序的顺序计