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 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个顶点的完全图中，生成树的数目至少有2n-1-1。
8-17 编写一个完整的程序，首先定义堆和并查集的结构类型和相关操作，再定义Kruskal求连通网络的最小生成树算法的实现。并以右图为例，写出求解过程中堆、并查集和最小生成树的变化。
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;
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);
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
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 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个顶点的完全图中，生成树的数目至少有2n-1-1。
8-17 编写一个完整的程序，首先定义堆和并查集的结构类型和相关操作，再定义Kruskal求连通网络的最小生成树算法的实现。并以右图为例，写出求解过程中堆、并查集和最小生成树的变化。
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;
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);
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
