8-1画出1个顶点、2个顶点、3个顶点、4个顶点和5个顶点的无向完全图。试证 明在n个顶点的无向完全图中,边的条数为m(n1)/2。 8-2右边的有向图是强连通的吗?请列出所有的简单路径。A 8-3给出右图的邻接矩阵、邻接表和邻接多重表表示 8.4用邻接矩阵表示图时,若图中有1000个顶点,100条C0 边,则形成的邻接矩阵有多少矩阵元素?有多少非零元素? 否稀疏矩阵? 【解答】一个图中有1000个顶点,其邻接矩阵中的矩阵元素有1000=1000000个。它 有1000个非零元素(对于有向图)或2000个非零元素(对于无向图),因此是稀疏矩阵 8-5用邻接矩阵表示图时,矩阵元素的个数与顶点个数是否相关?与边的条数是否相 【解答】用邻接矩阵表示图,矩阵元素的个数是顶点个数的平方,与边的条数无关。矩 阵中非零元素的个数与边的条数有关。 8-6有n个顶点的无向连通图至少有多少条边?有n个顶点的有向强连通图至少有多少 条边?试举例说明 【解答个顶点的无向连通图至少有n1条边,n个顶点的有向强连通图至少有n条边 例如: 无向图 有向图 ① 8-7对于有n个顶点的无向图,采用邻接矩阵表示,如何判断以下问题:图中有多少条 边?任意两个顶点和j之间是否有边相连?任意一个顶点的度是多少? 【解答】用邻接矩阵表示无向图时,因为是对称矩阵,对矩阵的上三角部分或下三角部 分检测一遍,统计其中的非零元素个数,就是图中的边数。如果邻接矩阵中A[i][i不为 零,说明顶点ⅰ与顶点j之间有边相连。此外统计矩阵第i行或第i列的非零元素个数, 就可得到顶点i的度数。 8-8对于如右图所示的有向图,试写出: (1)从顶点①出发进行深度优先搜索所得到的 深度优先生成树 (2)从顶点②出发进行广度优先搜索所得到的 广度优先生成树
8-1 画出 1 个顶点、2 个顶点、3 个顶点、4 个顶点和 5 个顶点的无向完全图。试证 明在 n 个顶点的无向完全图中，边的条数为 n(n-1)/2。 8-2 右边的有向图是强连通的吗？请列出所有的简单路径。 8-3 给出右图的邻接矩阵、邻接表和邻接多重表表示。 8-4 用邻接矩阵表示图时，若图中有 1000 个顶点，1000 条 边，则形成的邻接矩阵有多少矩阵元素？有多少非零元素？ 是否稀疏矩阵？ 【解答】一个图中有 1000 个顶点，其邻接矩阵中的矩阵元素有 10002 = 1000000 个。它 有 1000 个非零元素（对于有向图）或 2000 个非零元素（对于无向图），因此是稀疏矩阵。 8-5 用邻接矩阵表示图时，矩阵元素的个数与顶点个数是否相关？与边的条数是否相 关？ 【解答】用邻接矩阵表示图，矩阵元素的个数是顶点个数的平方，与边的条数无关。矩 阵中非零元素的个数与边的条数有关。 8-6 有 n 个顶点的无向连通图至少有多少条边？有 n 个顶点的有向强连通图至少有多少 条边？试举例说明。 【解答】n 个顶点的无向连通图至少有 n-1 条边，n 个顶点的有向强连通图至少有 n 条边。 例如： 8-7 对于有 n 个顶点的无向图，采用邻接矩阵表示，如何判断以下问题： 图中有多少条 边？任意两个顶点 i 和 j 之间是否有边相连？任意一个顶点的度是多少？ 【解答】用邻接矩阵表示无向图时，因为是对称矩阵，对矩阵的上三角部分或下三角部 分检测一遍，统计其中的非零元素个数，就是图中的边数。如果邻接矩阵中 A[i][j] 不为 零，说明顶点 i 与顶点 j 之间有边相连。此外统计矩阵第 i 行或第 i 列的非零元素个数， 就可得到顶点 i 的度数。 8-8 对于如右图所示的有向图，试写出： (1) 从顶点①出发进行深度优先搜索所得到的 深度优先生成树； (2) 从顶点②出发进行广度优先搜索所得到的 广度优先生成树；
8-9试扩充深度优先搜索算法,在遍历图的过程中建立生成森林的左子女-右兄弟链表 算法的首部为 viod Graph:DFS( const int y, int visited[l, Tree Node<int>*t)其中,指 针t指向生成森林上具有图顶点ν信息的根结点。(提示:在继续按深度方向从根ν的某 一未访问过的邻接顶点w向下遍历之前,建立子女结点。但需要判断是作为根的第一个 子女还是作为其子女的右兄弟链入生成树。) 8-10用邻接表表示图时,顶点个数设为n,边的条数设为e,在邻接表上执行有关图的 遍历操作时,时间代价是On*e)?还是O(n+e)?或者是Omax(n,e) 【解答】在邻接表上执行图的遍历操作时,需要对邻接表中所有的边链表中的结点访问 次,还需要对所有的顶点访问一次,所以时间代价是O(n+e)。 8-15右图是一个连通图,请画出 ②2 (1)以顶点①为根的深度优先生成树 (2)如果有关节点,请找出所有的关节点。 (3)如果想把该连通图变成重连通图,至少在 图中加几条边?如何加? 【解答】 (1)从顶点①出发的深度优先生成树为 ③人 此答案不唯 8 8-16试证明在一个有n个顶点的完全图中,生成 树的数目至少有2n1-1 10 8-17编写一个完整的程序,首先定义堆和并查集 的结构类型和相关操作,再定义 Kruskal求连通 网络的最小生成树算法的实现。并以右图为例
8-9 试扩充深度优先搜索算法，在遍历图的过程中建立生成森林的左子女-右兄弟链表。 算法的首部为viod Graph::DFS ( const int v, int visited [ ], TreeNode<int> * t ) 其中，指 针 t 指向生成森林上具有图顶点 v 信息的根结点。（提示：在继续按深度方向从根 v 的某 一未访问过的邻接顶点 w 向下遍历之前，建立子女结点。但需要判断是作为根的第一个 子女还是作为其子女的右兄弟链入生成树。） 8-10 用邻接表表示图时，顶点个数设为 n，边的条数设为 e，在邻接表上执行有关图的 遍历操作时，时间代价是 O(n*e)？还是 O(n+e)？或者是 O(max(n,e))？ 【解答】在邻接表上执行图的遍历操作时，需要对邻接表中所有的边链表中的结点访问 一次，还需要对所有的顶点访问一次，所以时间代价是 O(n+e)。 8-15 右图是一个连通图，请画出 (1) 以顶点①为根的深度优先生成树； (2) 如果有关节点，请找出所有的关节点。 (3) 如果想把该连通图变成重连通图，至少在 图中加几条边？如何加？ 【解答】 (1) 从顶点①出发的深度优先生成树为 此答案不唯一 (2) 8-16 试证明在一个有 n 个顶点的完全图中，生成 树的数目至少有 2 n-1 -1。 8-17 编写一个完整的程序，首先定义堆和并查集 的结构类型和相关操作，再定义 Kruskal 求连通 网络的最小生成树算法的实现。并以右图为例
写出求解过程中堆、并查集和最小生成树的变化。 8-18利用 Dijkstra算法的思想,设计一个求最小生成树的算法 8-19以右图为例,按 Dijkstra算法计算得到的从顶点 ①到其它各个顶点的最短路径和最短路径长度 5 OC 8-20在以下假设下,重写 Dijkstra算法 1)用邻接表表示带权有向图G,其中每个边结点有3个域:邻接顶点 vertex,边上 的权值 length和边链表的链接指针lmke (2)用集合T=I(G)-S代替S(已找到最短路径的顶点集合),利用链表来表示集合T 试比较新算法与原来的算法,计算时间是快了还是慢了,给出定量的比较。 8-22使用 Floyd算法计算8-19题所用的带权有向图的各对顶点之间的最短路径。 23下面是基于元素0到4的一些优先关系的集合,试问它们是否定义了一个偏序关 ?为什么? 0<1;1<3;1<2;2<3;2<4;4<0 8-24试证明:对于一个无向图G=(VE),若G中各顶点的度均大于或等于2,则G中 必有回路 【解答】反证法:对于一个无向图G=(V,E),若G中各顶点的度均大于或等于2,则 G中没有回路。此时从某一个顶点出发,应能按拓扑有序的顺序遍历图中所有顶点。但 当遍历到该顶点的另一邻接顶点时,又可能回到该顶点,没有回路的假设不成立。 8-25设有一个有向图存储在邻接表中。试设计一个 算法,按深度优先搜索策略对其进行拓扑排序。并 以右图为例检验你的算法的正确性 【解答】 (1)定义邻接表结构 const n=.. (顶点个数} type pointer= t node node= record adi: integer; 邻接顶点号} cost: real 边上的权值}
写出求解过程中堆、并查集和最小生成树的变化。 8-18 利用 Dijkstra 算法的思想，设计一个求最小生成树的算法。 8-19 以右图为例，按 Dijkstra 算法计算得到的从顶点 ①到其它各个顶点的最短路径和最短路径长度。 8-20 在以下假设下，重写 Dijkstra 算法： (1) 用邻接表表示带权有向图 G，其中每个边结点有 3 个域：邻接顶点 vertex，边上 的权值 length 和边链表的链接指针 link。 (2)用集合 T = V(G) - S 代替 S(已找到最短路径的顶点集合)，利用链表来表示集合 T。 试比较新算法与原来的算法，计算时间是快了还是慢了，给出定量的比较。 8-22使用 Floyd 算法计算 8-19 题所用的带权有向图的各对顶点之间的最短路径。 8-23 下面是基于元素 0 到 4 的一些优先关系的集合，试问它们是否定义了一个偏序关 系？为什么？ 0<1;1<3; 1<2;2<3;2<4; 4<0 8-24 试证明：对于一个无向图 G = (V, E)，若 G 中各顶点的度均大于或等于 2，则 G 中 必有回路。 【解答】反证法：对于一个无向图 G=（V，E），若 G 中各顶点的度均大于或等于 2，则 G 中没有回路。此时从某一个顶点出发，应能按拓扑有序的顺序遍历图中所有顶点。但 当遍历到该顶点的另一邻接顶点时，又可能回到该顶点，没有回路的假设不成立。 8-25 设有一个有向图存储在邻接表中。试设计一个 算法，按深度优先搜索策略对其进行拓扑排序。并 以右图为例检验你的算法的正确性。 【解答】 (1) 定义邻接表结构 const n = ……; {顶点个数} type pointer = ↑node node = record adj : integer; {邻接顶点号} cost : real; {边上的权值} link : pointer;
record 顶点入度} four pointer {出边表头指针} nodelist =array[ln] of vex; 邻接表} ·另设一个辅助数组,记录访问顺序: visited:aray1. n] of integero 初始时,各结点的wsed均为0。 ·还有一个访问计数coum,初始时为0。 (2)拓扑排序算法 procedure d/s(G: nodelist; v: integer ) var w: integer; p: pointer; count: =count+ I; visited =count; p:=Gv] four w:=p↑.ad; Gw].ind: =G[w]. ind-1; if( visited]=0)and( Glw]. ind=0)then dfs(G, w); p=p↑.limk d 主程序 for i: =1 to n do visited[0: =0; read i,j, 1); while(io0)and(o0)do begin new(p); p↑ad:=j; GU]. ind: =Gl). ind+ 1; G[i fout: =P read(i,j, w);
end; vex = record ind : integer; {顶点入度} fout : pointer; {出边表头指针} end; nodelist = array[1..n] of vex; {邻接表} 另设一个辅助数组，记录访问顺序：visited : array[1..n] of integer。 初始时，各结点的 visited[i]均为 0。 还有一个访问计数 count，初始时为 0。 (2) 拓扑排序算法 procedure dfs ( G : nodelist; v : integer ); var w : integer; p : pointer; begin count := count + 1; visited[v] := count; p := G[v].fout; while p <> nil do begin w := p↑.adj; G[w].ind := G[w].ind - 1; if ( visited[w] = 0 ) and ( G[w].ind = 0 ) then dfs( G, w ); p := p↑.link; end; end; 主程序 for i := 1 to n do visited[i] := 0; count := 0; read ( i, j, w); while ( i <> 0 ) and ( j <> 0 ) do begin new(p); p↑.adj := j; p↑.cost := w; G[j].ind := G[j].ind + 1; p↑.link := G[i].fout; G[i].fout := p; read ( i, j, w);
nd: if visited[(=0)and(G( ind=0)then dfs(G,i); if count< n then write(排序失败); 8-26试对右图所示的AOE网络 (1)这个工程最早可能在什么时 2 间结束 19 (2)求每个活动的最早开始时间 ()和最迟开始时间l) (3)确定哪些活动是关键活动 【解答】按拓扑有序的顺序计算各个顶点的最早可能开始时间距和最迟允许开始时间 l然后再计算各个活动的最早可能开始时间e和最迟允许开始时间l,根据l-e=0?来 确定关键活动,从而确定关键路径。 19 15 37 8 17 15 27 19 27 37 38 17 12 此工程最早完成时间为43。关键路径为<1,3><3,2><2,5><5,6 8-27若AOE网络的每一项活动都是关键活动。令G是将该网络的边去掉方向和权 后得到的无向图 (1)如果图中有一条边处于从开始顶点到完成顶点的每一条路径上,则仅加速该边 表示的活动就能减少整个工程的工期。这样的边称为桥( bridge)。证明若从连通图中删去 桥,将把图分割成两个连通分量 (2)编写一个时间复杂度为On+e)的使用邻接表表示的算法,判断连通图G中是否 有桥,若有。输出这样的桥。 8.28.48.7 8.238.24 8.178.28 8.258.268.27
end; for i := 1 to n do if ( visited[i] = 0 ) and ( G[i].ind = 0 ) then dfs ( G, i ); if count < n then write (‘排序失败’); 8-26 试对右图所示的 AOE 网络 (1) 这个工程最早可能在什么时 间结束。 (2) 求每个活动的最早开始时间 e( )和最迟开始时间 l( )。 (3) 确定哪些活动是关键活动。 【解答】按拓扑有序的顺序计算各个顶点的最早可能开始时间 Ve 和最迟允许开始时间 Vl。然后再计算各个活动的最早可能开始时间 e 和最迟允许开始时间 l，根据 l - e = 0? 来 确定关键活动，从而确定关键路径。 1 2 3 4 5 6 Ve 0 19 15 29 38 43 Vl 0 19 15 37 38 43 <1, 2> <1, 3> <3, 2> <2, 4> <2, 5> <3, 5> <4, 6> <5, 6> e 0 0 15 19 19 15 29 38 l 17 0 15 27 19 27 37 38 l-e 17 0 0 8 0 12 8 0 此工程最早完成时间为 43。关键路径为<1, 3><3, 2><2, 5><5, 6> 8-27 若 AOE 网络的每一项活动都是关键活动。令 G 是将该网络的边去掉方向和权 后得到的无向图。 (1) 如果图中有一条边处于从开始顶点到完成顶点的每一条路径上，则仅加速该边 表示的活动就能减少整个工程的工期。这样的边称为桥(bridge)。证明若从连通图中删去 桥，将把图分割成两个连通分量。 (2) 编写一个时间复杂度为 O(n+e)的使用邻接表表示的算法，判断连通图 G 中是否 有桥，若有。输出这样的桥。 8.8 8.11 8.15 8.9 8.2 8.4 8.7 8.23 8.24 8.17 8.28 8.25 8.26 8.27