ch7复习及习题.ppt

图是一种更为复杂的数据结构，在图中，顶点之间的关系是任意的。本章主要介绍图的存储结构以及若干图操作的实现，给出图的一些应用实例。 重点 图的定义和术语，图的数组表示法和邻接矩阵表示法存储结构以及图的两种遍历方法，图的连通性问题，构造最小生成树的两种方法。 难点 图的两种存储结构以及两种遍历方法，图的最小生成树和最短路径问题。,第7章 图,图,定义与概念,算 法,存储结构,有向图,无向图,数组,邻接表,十字链表,邻接多重表,DF S,B F S,遍历,最小生成树,最短路径,DAG,PR IM,KRUSKAL,FLOYD,DI J,拓扑排序,关键路径,ch7知识结构图,图的数组表示法小结,优点 易查找任一顶点的第一个邻接点和下一个邻接点。 易判定任两个顶点之间是否有边或弧存在。 缺点：在边稀疏的情况下,浪费存储空间 时间复杂度讨论：有n个顶点和e条边的图 邻接矩阵初始化的时间复杂度为O（n2） 输入顶点编号，建立邻接矩阵的时间复杂度为O（e） 输入顶点值，建立邻接矩阵的时间复杂度为O（n*e） 总的时间复杂度为：O（n2+n*e） 适合：有向图、无向图（有向网、无向网）,图的邻接表存储结构小结,优点：易找到任一顶点的第一个邻接点和下一个邻接点 缺点：难以判定任意两个顶点之间是否有边或弧相连。也有办法：搜索第i和第j个单链表。不及邻接矩阵方便。 时间复杂度的讨论： 邻接表头结点初始化的时间复杂度为O（n） 输入顶点编号，建立邻接表的时间复杂度为O（n+e） 输入顶点值，建立邻接表的时间复杂度为O（n*e） 总的时间复杂度为：O（n+n*e） 适合：有向图（网）、无向图（网）,深度优先搜索举例,深度遍历：V1,V3 ,V7 ,V6 ,V2 ,V5 ,V8 ,V4,给定存储结构，图的遍历序列唯一!,广度优先搜索举例,广度遍历：V1 V3 V2 V7 V6 V5 V4 V8,给定存储结构，图的遍历序列唯一!,应掌握的习题及类型： 一、图的术语和性质、图的存储结构 二、深度、广度优先遍历图的算法及应用 三、最小生成树的2种构造方法 四、拓扑排序和关键路径 五、最短路径,ch7类型题,1. 一个有n个顶点的无向图若是连通图，则至少有_条边。 A. n B. n+1 C. n-1 D. n/2 2. 图的广度优先遍历算法类似于二叉树的_。 A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 层序遍历 3. 图的深度优先遍历算法类似于二叉树的_。 A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 层序遍历 4. 无向图的邻接矩阵是一个_。 A. 对称矩阵 B. 零矩阵 C. 对角矩阵 D. 上三角矩阵 5. 一个无向连通图的生成树是含有该连通图所有顶点的_。 A.极大连通子图 B. 极大子图 C. 极小连通子图 D. 极小子图 6. 如果从无向图的任意顶点出发进行一次深度优先遍历就能访问到图中所有顶点，则该图一定是_。 A. 完全图 B. 连通图 C. 有回路 D. 一棵树,Ch7 复习题,7. 一个以AOE网描述的工程，其关键路径的长度是指从 源点到汇点的_。 A. 任意路径长度 B. 最短路径长度 C. 最长路径长度 8. 对_，用Kruskal算法求最小生成树较为合适。 A. 完全图 B. 连通图 C. 稀疏图 D.稠密图 9. 对_，用Prim算法求最小生成树较为合适。 A. 完全图 B. 连通图 C. 稀疏图 D.稠密图 10. 对一个以邻接表为存储结构、有n个顶点e条边的无向连通图，深度优先遍历图的时间复杂度是_。 A. O(n) B. O(n2) C. O(n+e) D. O(n*e),11. 对一个以数组表示法为存储结构、有n个顶点e条边的无向连通图，广度优先遍历图的时间复杂度是_。 A. O(n) B. O(n2) C. O(n+e) D. O(n*e),判断： 连通网的最小生成树是唯一的。 利用拓扑排序，可检测一个有向图中是否存在环。 一个有向图的邻接表和逆邻接表中结点个数可能不等。 一棵有n个顶点的生成树有且仅有n-1条边。 有n个顶点和n-1条边的无向图是生成树。 如果一个无向图有n个顶点和小于n-1条边，是非连通图。 在n个顶点的无向图中，若边数大于n-1，则该图一定是连通图 如果n个顶点的无向图有多于n-1条边，必有环存在。 任何有向图的顶点都可以排成拓扑有序序列，而且拓扑序列 不唯一。 AOE 网中的关键路径只有一条。,当改变AOE 网上某一关键路径上的任意活动后，必将产生不同的关键路径。 只要能提高关键活动的速度，就能缩短整个工程的工期。 有向图的拓扑排序序列唯一，则其弧数必为n-1（n为图中顶点数）。 从某顶点开始对有向图进行深度优先遍历，若所得的遍历序列唯一，则可断定其弧数为n-1（n为图中顶点数）。 若有向图的拓扑排序序列唯一，则图中必定仅有一个顶点的入度为0，一个顶点的出度为0。 若n个顶点的无向连通图的最小生成树不唯一，则图中的边数一定多于n-1, 并且权值最小的边有多条。,在对有向无环图执行拓扑排序算法之后，入度数组中所有元素的值均为0。（ ） 若从无向图的一个顶点出发进行广度优先遍历可访问到图中的所有顶点，则该图一定是连通图。 （ ） 下列关于最短路径的说法中，正确的有_。 A. Dijkstra算法是按路径长度递增的顺序依次产生从某一固定源点到其他各顶点之间的最短路径。 B. 若仅求单一源点到某一特定顶点之间的最短路径，则其算法的时间复杂度可以达到O(n)。 C. 求图中每一对顶点间最短路径的Floyd算法的时间复杂度为O(n3)。 D. 求图中每一对顶点间的最短路径也可用Dijkstra算法实现。,对于下图表示的有向图，可能的拓扑有序序列有_。 A. 123564 B. 152634 C. 561234 D.516234 下列说法中不正确的有_。 A. n个顶点的无向连通图的边数为n(n-1) B. 图的广度优先遍历过程是一个递归过程 C. n个顶点的有向完全图的弧数为n(n-1) D. 有向图的强连通分量是有向图的极大强连通子图,G是非连通无向图，有28条边，则该图至少有 个顶点 无向图中，所有顶点的度数之和等于所有边数的 倍。 一个具有n个顶点的无向完全图包含 条边，一个 具有n个顶点的有向完全图包含 条弧。 如果G1是一个具有n个顶点的连通无向图，则G1最多有 条边，最少有 条边。 具有4个顶点的无向完全图有 条边。 若一个有向图的邻接矩阵中对角线以下元素为，则该图的拓扑有序序列必定存在（对错） 判断一个有向图是否存在回路除了可用拓扑排序方 法以外，还可用 。,邻接矩阵A= ，该图有 个顶点，如果是有向图， 该图共有 条弧，如果是无向图，该图共有 条边。 n个顶点的无向图采用邻接矩阵表示，图中的边数等于邻接矩 阵中非零元素之和的一半。（对/错） 有向图的邻接矩阵中第i行“1”的个数是第i个顶点的 ，第i列“1” 的个数是第i个顶点的 。在无向图的邻接矩阵中，第i行(列)中 ”1”的个数是第i个顶点的 。 一个有1000个顶点、1000条边的有向图的邻接矩阵有 个矩阵元素，（是/否）稀疏矩阵。 一个连通图的生成树是该图的 连通子图，n个顶点的无向 连通图的邻接矩阵至少有 个非零元素。 在含n个顶点和e条边的有向图的邻接矩阵中，零元素的个数为 。 A.e B.2e C.n2-e D.n2-2e,0 1 0 1 0 1 0 1 0,6 如图的连通图，请画出以顶点1为根的深度优先和广度优先生成树。从顶点1出发，对它进行深度优先遍历和广度优先遍历得到的顶点序列分别是 。,深度优先遍历序列：,1-2 - 4 - 8 - 9 - 3 - 10 - 7 - 6 - 5,1- 2 -3 - 8 - 4 - 10 - 9 - 7 - 5 - 6,广度优先遍历序列：,画出上图的邻接表表示,以此为存储结构,写出从A出发对图进行深度优先遍历和广度优先遍历所得的序列. 注意:给定存储结构，图的遍历序列唯一,深度优先遍历序列:ABDEC,广度优先遍历序列:ABCDE,第7章 作业讲评,7.1 已知右示有向图，给出该图的： 1） 每个顶点的入/出度 2） 邻接矩阵 3） 邻接表 4） 逆邻接表 5） 强连通分量,7. 7 对右图所示的无向带权图， 1） 写出它的邻接矩阵，并按Prim算法求其最小生成树 2） 写出它的邻接表，并按Kruskal算法求其最小生成树。,a,c,b,d,h,g,f,e,a,c,b,d,h,g,f,e,7.9 试列出下示图中全部可能的拓扑有序序列，并指出用算法7.12求得的是哪个序列（注意：应先确定其存储结构）。,3 6 4,5,2,6 3 4,6,2 3 4,1,5,1,6,2,6,3 6 4,6 3 4,2 3 4,1 2 3 4,7.10 对于下图所示的AOE网,计算各活动弧的e(ai)和l(ai) 值、各事件的ve(vi)和vl(vj) 值，列出各条关键路径。,关键路径是(a,G,H,K,J,E,w) 注：关键路径可有多条。 缩短工期必须缩短关键活动所需的时间,Ve(k) = MaxVe(j)+dut() Vl(j)=MinVl(k)-dut() 各事件的最早和最迟开始时间：,e(i) = Ve(j); l(i) = Vl(k) dut(); 各活动的最早和最迟开始时间：,0,1,6,3,4,3,1,13,22,17,31,34,44,44,34,31,26,22,13,20,24,19,8,3,7,0,0 19,0 18,1 20,31 32,34 34,邻接矩阵,7.11利用Dijkstra算法求下图中从顶点a到其余各顶点间的最短路径.,a b c d e f g,a b c d e f g,15 (a,b) 2 (a,c) 12 (a,d) ,c (a,c),10 (a,c,e),6 (a,c,f),15 (a,b) 12 (a,d) ,f (a,c,f),15 (a,b) 10 (a,c,e),11 (a,c,f,d),16 (a,c,f,g),e (a,c,f,e),15 (a,b) 11 (a,c,f,d) 16 (a,c,f,g),d (a,c,f, e,d),15 (a,b),14 (a,c,f,d,g),g (a,c,f, e,d,g),15 (a,b),b (a,c,f, e,d,g,b),7.14 编写算法，由依次输入的顶点数目、弧的数目、各顶 点的信息和各条弧的信息建立有向图的邻接表。,Status createDG(AlGraph /createDG,7.22 是基于图的深度优先策略写一算法，判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径(ij)。,Boolean visitedMAX; Boolean search(AlGraph G, VexType vi, VexType vj) for(k=0; knextarc) if(!visitedp-adjvex ,7.23广度优先遍历判断有向图G中顶点i到j是否有路径,int path_BFS(ALGraph G,int i,int