6.9 本 章 小 结
6.9 本 章 小 结
本章的基本内容是：图的定义和基本术语、图的存储结构、图的两种遍历方法、最短距离问题等。
图是一种网状型的数据结构，属于多对多的非线性结构，图中的每个节点可以有多个直接前趋和直接后继。图的存储包括存储图中顶点的信息和边的信息两个部分。这两个部分既可以分开单独存储，也可以用结构体形式一起存储。图的存储结构有邻接矩阵、邻接表等。
图的遍历包含深度优先搜索遍历和广度优先搜索遍历。对于用邻接矩阵结构存储的图，从某个给定顶点出发的图的遍历得到的访问顶点次序是唯一的，而对于邻接表结构存储的图，从某个给定的顶点出发的图的遍历得到的访问顶点次序随建立邻接表的不同而可能不同。
一个连通图的生成树含有该图的全部n个顶点和其中n-1条边（不构成回路），其中权值之和最小的生成树称为最小生成树。求最小生成树有两种不同的方法，一种是普里姆算法，另一种是克鲁斯卡尔算法。所采用的方法不同，得到的最小生成树中边的次序也可能不同，但最小生成树的权值之和相同。
求图的最短路径有两种，其一是单源点的最短路径，用狄克斯特拉算法来实现；其二是所有顶点对的最短路径，用弗洛伊德算法来实现。
6.10 练 习 题
1．选择题
（1）在一个图中，所有顶点的度数之和等于所有边数的 倍。
A．1/2 B．1
C．2 D．4
（2）在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的 倍。
A．1/2 B．1
C．2 D．4
（3）一个有n个顶点的无向图最多有 条边。
A．n B．n(n-1)
C．n(n-1)/2 D．2n
（4）具有4个顶点的无向完全图有 条边。
A．6 B．12
C．16 D．20
（5）具有6个顶点的无向图至少应有 条边才能确保是一个连通图。
A．5 B．6
C．7 D．8
（6）在一个具有n个顶点的无向图中，要连通全部顶点至少需要 条边。
A．n B．n+1
C．n-1 D．n/2
（7）对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是 。
A．n B．(n-1)2
C．n-1 D．n2
（8）采用邻接表存储的图的深度优先遍历算法类似于二叉树的 。
A．先序遍历 B．中序遍历
C．后序遍历 D．按层遍历
（9）采用邻接表存储的图的宽度优先遍历算法类似于二叉树的 。
A．先序遍历 B．中序遍历
C．后序遍历 D．按层遍历
（10）判定一个有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用
。
A．求关键路径方法
B．求最短路径的狄克斯特拉算法
C．宽度优先遍历算法
D．深度优先遍历算法
2．填空题
（1）n个顶点的连通图至少有 条边。
（2）在无权图G的邻接矩阵中，若A[i][j]等于1，则A[j][i] = 。
（3）已知某图的邻接矩阵表示，计算第i个节点的入度的方法是 。
（4）已知某图的邻接矩阵表示，删除所有从第i个节点出发的边的方法是 。
（5）在无权图G的邻接矩阵中，若(vi, vj)或<vi, vj>属于图G的边集，则对应元素A[i][j]等于 ，否则等于 。
（6）对于一个具有n个顶点和e条边的无向图，当分别采用邻接矩阵、邻接表和边集数组表示时，求任一顶点度数的时间复杂度依次为 、 和 。
（7）假定一个图具有n个顶点和e条边，则采用邻接矩阵、邻接表和边集数组表示时，其相应的空间复杂度分别为 、 和 。
（8）对用邻接矩阵表示的图进行任一种遍历时，其时间复杂度为 ，对用邻接表表示的图进行任一种遍历时，其时间复杂度为 。
3．问答题
（1）如果图G1是一个具有n个顶点的连通无向图，那么G1最多有多少条边？G1最少有多少条边？如果图G2是一个具有n个顶点的强连通有向图，那么G2最多有多少条边？G2最少有多少条边？
（2）对于稠密图和稀疏图，采用邻接矩阵和邻接表哪个更好？
（3）对n个顶点的无向图和有向图，采用邻接矩阵和邻接表表示时，如何判别下列有关问题：
①图中有多少条边？
②任意两个顶点i和j是否有边相连？
③任意一个顶点的度是多少？
（4）给出如图6-36所示的无向图G的邻接矩阵和邻接表两种存储结构。并在给定的邻接表基础上，指出从顶点1出发的深度优先遍历和广度优先遍历序列。
（5）对于图6-37所示的有向图，试给出：
①邻接矩阵。
②邻接表。
③强连通分量。
④从顶点1出发的深度优先遍历序列。
⑤从顶点3出发的广度优先遍历序列。
图6-36 无向图G 图6-37 有向图
（6）有一个AOV网B，如图6-38所示。
图6-38 AOV网B示意图
试求出其关键路径。
4．上机操作题
（1）设计一个算法将有向图G的邻接矩阵存储结构转换成邻接表存储结构。
（2）编写根据有向图的邻接表，求图中每个顶点的出度算法。
（3）给出一个具有n个顶点的无向图的邻接表，请设计一个算法，实现将邻接表转换为邻接矩阵。
（4）以邻接表作为图的存储结构，求图中从顶点u到v的一条简单路径。