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*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 * 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<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 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。关键路径为 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
