81有n个选手参加的单循环比赛要进行多少场次的比赛

8.1有n个选手参加的单循环比赛要进行多少场次的比赛？试用图结构描述其求解。若是主客场制的联赛，又要进行多少场比赛？

8.2证明下列命题：

（1）在任意一个有向图中，所有顶点的入度之和与出度之和相等。 （2）任一无向图中各顶点的度的和一定为偶数。 8.3一个强连通图中各顶点的度有什么特点？ 8.4证明：有向树中仅有n-1条弧。

8.5证明树的三个不同定义之间的等价性。

8.6已知有向图G用邻接矩阵存储，设计算法以分别求解顶点vi的入度、出度和度。 8.7已知图G用邻接矩阵存储，设计算法以分别实现函数firstadj（G，v）和nextadj(G,v,w)。 8.8设图G用邻接矩阵A[n+1,n+1]表示，设计算法以判断G是否是无向图。 8.9已知图G用邻接表存储，设计算法以输出其所有边或弧。（假设各表头指针在数组A[n+1]中）

8.10对下列图，分别执行dfs(1)和dfs(5)，写出遍历序列，并构造出相应的dfs生成树。

○1 ○1

2 ○3 ○2 ○5 ○

4 ○5 ○6 ○7 ○8 ○3 ○4 ○6 ○7 ○8.11对下图G所示的邻接表，不用还原出原图，请执行dfs(1)，写出遍历序列，并构造出相应的dfs生成树。

info ptr 1 2 3 ∧ 2 3 4 5 ∧ 3 4 ∧ 4 8 ∧ 5 4 6 ∧ 6 4 7 ∧ 7 5 8 ∧ 8 5 ∧ 8.12设计算法以判断顶点vi到vj之间是否存在路径？若存在，则返回TRUE，否则返

回FALSE。

8.13设计算法以判断无向图G是否是连通的，若连通，返回TRUE，否则返回FALSE； 8.14设G是无向图，设计算法求出G中的边数。（假设图G分别采用邻接矩阵、邻接表以及不考虑具体存储形式，而是通过调用前面所述函数来求邻接点）

8.15设G是无向图，设计算法以判断G是否是一棵树，若是树，则返回TRUE，否则返回FALSE；

8.16设G是有向图，设计算法以判断G是否是一棵以v0为根的有向树，若是返回TRUE，否则返回FALSE；

8.17在图G分别采用邻接矩阵和邻接表存储时，分析深度遍历算法的时间复杂度。 8.18设连通图用邻接表A表示，设计算法以产生dfs（1）的dfs生成树，并存储到邻接矩阵B中。

8.19在图G分别采用邻接矩阵和邻接表存储时，分析广度遍历算法的时间复杂度。 8.20设计算法以求解从vi到vj之间的最短路径。（每条边的长度为1） 8.21设计算法以求解距离v0最远的一个顶点。

8.22设计算法以求解二叉树T中层次最小的一个叶子结点的值。

8.23分别用prim算法和Kruskal算法求解下图的最小生成树，并标注出中间求解过程的各状态。

○1 6 ○6 20 19 17 9 ○2 17 ⑦ 19 ○5 16 15 20 24 ○3 13 ○4

8.24在图分别采用邻接矩阵和邻接表存储时，prim算法的时间复杂度是否一致？为什么？

8.25在实现Kruskal算法时，如何判断某边和已选边是否构成回路？ 8.26对下列AOV网，完成如下操作：

（1）按拓扑排序方法进行拓扑排序，写出中间各步的入度数组和栈的状态值，并写出拓扑序列。

（2）写出左图所示AOV网的所有的拓扑序列。

③ ⑥ ② ④ ⑤ ① ⑨ ① ④ ⑦ ⑩

③ ⑥ ② ⑤ ⑧ (a) (b)

8.27分析在图分别采用邻接矩阵和邻接表存储时的拓扑排序算法的时间复杂度。 8.28对下面的图，求出从顶点1到其余各顶点的最短路径。

① 10 ② 25 ③ 20 ④ 15 20 6 6 8 10 5

⑤ 5 ⑥ 7 ⑦ 4 ⑧

8.29分析在图分别采用邻接矩阵和邻接表存储时，求最短路径的Dijkstra算法的时间复杂度。

8.30采用Floyd算法求解下图中各顶点之间的最短路径。 6

① ② 2

15 8 20

6 ③ ④ 12