7.1 在图7.23所示的各无向图中：
(1)找出所有的简单环。
(2)哪些图是连通图?对非连通图给出其连通分量。
(3)哪些图是自由树(或森林)?
答:
(1)所有的简单环：(同一个环可以任一顶点作为起点)
(a)1231
(b)无
(c)1231、2342、12341
(d)无
(2)连通图：
(a)、(c)、(d)是连通图，
(b)不是连通图，因为从1到2没有路径。具体连通分量为：
(3)自由树(森林)：自由树是指没有确定根的树，无回路的连通图称为自由树：
(a)不是自由树，因为有回路。
(b)是自由森林，其两个连通分量为两棵自由树。
(c)不是自由树。
(d)是自由树。
7.2 在图7.24(下图)所示的有向图中：
(1) 该图是强连通的吗? 若不是，则给出其强连通分量。
(2) 请给出所有的简单路径及有向环。
(3) 请给出每个顶点的度，入度和出度。
(4) 请给出其邻接表、邻接矩阵及逆邻接表。
答：
(1)该图是强连通的，所谓强连通是指有向图中任意顶点都存在到其他各顶点的路径。
(2)简单路径是指在一条路径上只有起点和终点可以相同的路径：
有v1v2、v2v3、v3v1、v1v4、v4v3、v1v2v3、v2v3v1、v3v1v2、v1v4v3、v4v3v1、v3v1v4、另包括所有有向环,有向环如下：
v1v2v3v1、v1v4v3v1(这两个有向环可以任一顶点作为起点和终点)
(3)每个顶点的度、入度和出度：
D(v1)=3 ID(v1)=1 OD(v1)=2
D(v2)=2 ID(v2)=1 OD(v2)=1
D(v3)=3 ID(v3)=2 OD(v3)=1
D(v4)=2 ID(v4)=1 OD(v4)=1
(4)邻接表：(注意边表中邻接点域的值是顶点的序号，这里顶点的序号是顶点的下标值-1)
vertex firstedge next
┌─┬─┐ ┌─┬─┐ ┌─┬─┐
0│v1│ ─→│ 1│ ─→│ 3│∧│
├─┼─┤ ├─┼─┤ └─┴─┘
1│v2│ ─→│ 2│∧│
├─┼─┤ ├─┼─┤
2│v3│ ─→│ 0│∧│
├─┼─┤ ├─┼─┤
3│v4│ ─→│ 2│∧│
└─┴─┘ └─┴─┘
逆邻接表：
┌─┬─┐ ┌─┬─┐
0│v1│ ─→│ 2│∧│
├─┼─┤ ├─┼─┤
1│v2│ ─→│ 0│∧│
├─┼─┤ ├─┼─┤ ┌─┬─┐
2│v3│ ─→│ 1│ ─→│ 3│∧│
├─┼─┤ ├─┼─┤ └─┴─┘
3│v4│ ─→│ 0│∧│
└─┴─┘ └─┴─┘
邻接矩阵：
0 1 0 1
0 0 1 0
1 0 0 0
0 0 1 0
7.3 假设图的顶点是A,B...，请根据下述的邻接矩阵画出相应的无向图或有向图。
┌ ┓
┌ ┓ | 0 1 1 0 0 |
| 0 1 1 1 | | 0 0 0 1 0 |
| 1 0 1 1 | | 0 0 0 1 0 |
| 1 1 0 1 | | 1 0 0 0 1 |
| 1 1 1 0 | | 0 1 0 1 0 |
┕ ┙ ┕ ┙
(a) (b)
答:
7.4 假设一棵完全二叉树包括A,B,C...等七个结点，写出其邻接表和邻接矩阵。
解：
邻接表如下：
┌─┬─┐ ┌─┬─┐ ┌─┬─┐
0│A │ ─→│ 1│ ─→│ 2│∧│
├─┼─┤ ├─┼─┤ ├─┼─┤ ┌─┬─┐
1│B │ ─→│ 0│ ─→│ 3│ ─→│ 4│∧│
├─┼─┤ ├─┼─┤ ├─┼─┤ ├─┼─┤
2│C │ ─→│ 0│ ─→│ 5│ ─→│ 6│∧│
├─┼─┤ ├─┼─┤ └─┴─┘ └─┴─┘
3│D │ ─→│ 1│∧│
├─┼─┤ ├─┼─┤
4│E │ ─→│ 1│∧│
├─┼─┤ ├─┼─┤
5│F │ ─→│ 2│∧│
├─┼─┤ ├─┼─┤
6│G │ ─→│ 2│∧│
└─┴─┘ └─┴─┘
邻接矩阵如下：
0 1 1 0 0 0 0
1 0 0 1 1 0 0
1 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0
0 0 1 0 0 0 0
0 0 1 0 0 0 0
7.5 对n个顶点的无向图和有向图，采用邻接矩阵和邻接表表示时，如何判别下列有关问题?
(1) 图中有多少条边?
(2)任意两个顶点i和j是否有边相连?
(3) 任意一个顶点的度是多少?
答：
对于n个顶点的无向图和有向图，用邻接矩阵表示时：
(1)设m为矩阵中非零元素的个数
无向图的边数=m/2
有向图的边数=m
(2)无论是有向图还是无向图，在矩阵中第i行,第j列的元素若为非零值，则该两顶点有边相连。
(3)对于无向图，任一顶点i的度为第i行中非零元素的个数。
对于有向图，任一顶点i的入度为第i列中非零元素的个数，出度为第i行中非零元素的个数，度为入度出度之和。
当用邻接表表示时：
(1)对于无向图，图中的边数=边表中结点总数的一半。
对于有向图，图中的边数=边表中结点总数。
(2)对于无向图，任意两顶点间是否有边相连，可看其中一个顶点的邻接表，若表中的adjvex域有另一顶点位置的结点，则表示有边相连。
对于有向图，则表示有出边相连。
(3)对于无向图，任意一个顶点的度则由该顶点的边表中结点的个数来决定。
对于有向图，任意一个顶点的出度由该顶点的边表中结点的个数来决定，入度则需遍历各顶点的边表。(用逆邻接表可容易地得到其入度。)
7.6 n个顶点的连通图至少有几条边?强连通图呢?
答：
n个顶点的连通图至少有n-1条边，强连通图至少有2(n-1)条边。
7.7 DFS和BFS遍历各采用什么样的数据结构来暂存顶点?当要求连通图的生成树的高度最小，应采用何种遍历?
答：
DFS遍历采用栈来暂存顶点。BFS采用队列来暂存顶点。当要求连通图的生成树的高度最小时，应采用BFS遍历。
7.8 画出以顶点v1为初始源点遍历图7.25（下图）所示的有向图所得到的DFS 和BFS生成森林。
答：
7.9 按顺序输入顶点对：(1，2)，(1，6)，(2，6)，(1，4)，(6，4)，(1，3)，(3，4),(6，5)，(4，5)，(1,5),(3,5),根据第7.2.2节中算法CreatALGraph画出相应的邻接表。并写出在该邻接表上，从顶点4开始搜索所得的DFS和BFS序列，及DFS和BFS生成树。
答：
相应的邻接表如下：
┌─┬─┐ ┌─┬─┐ ┌─┬─┐ ┌─┬─┐ ┌─┬─┐ ┌─┬─┐
1│1 │ ─→│ 5│ ─→│ 3│ ─→│ 4│ ─→│ 6│ ─→│ 2│∧│
├─┼─┤ ├─┼─┤ ├─┼─┤ └─┴─┘ └─┴─┘ └─┴─┘
2│2 │ ─→│ 6│ ─→│ 1│∧│
├─┼─┤ ├─┼─┤ ├─┼─┤ ┌─┬─┐
3│3 │ ─→│ 5│ ─→│ 4│ ─→│ 1│∧│
├─┼─┤ ├─┼─┤ ├─┼─┤ ├─┼─┤ ┌─┬─┐
4│4 │ ─→│ 5│ ─→│ 3│ ─→│6 │ ─→│ 1│∧│
├─┼─┤ ├─┼─┤ ├─┼─┤ ├─┼─┤ ├─┼─┤
5│5 │ ─→│ 3│ ─→│ 1│ ─→│ 4│ ─→│ 6│∧│
├─┼─┤ ├─┼─┤ ├─┼─┤ ├─┼─┤ ├─┼─┤
6│6 │ ─→│ 5│ ─→│ 4│ ─→│ 2│ ─→│ 1│∧│
└─┴─┘ └─┴─┘ └─┴─┘ └─┴─┘ └─┴─┘
根据上面的邻接表画出的图见下图:
从顶点4开始搜索所得的DFS序列是：453162
从顶点4开始搜索所得的BFS序列是：453612
相应的生成树见上图。
7.10 什么样的图其最小生成树是唯一的?用PRIM 和Kruskal求最小生成树的时间各为多少?它们分别适合于哪类图?
答：
当候选轻边集中的轻边数始终等于1条时，其最小生成树是唯一的。用Prim和Kruskal求最小生成树的时间复杂度分别为O(n2)和O(elge),前者适合于稠密图，后者适合于稀疏图.
7.11 对图7.26（下图）所示的连通图，请分别用Prim和Kruskal算法构造其最小生成树。
答：
7.12 对图7.27(下图)所示的有向图，试利用Dijkstra算法求出从源点1到其它各顶点的最短路径，并写出执行算法过程中扩充红点集的每次循环状态(见表7.2).
答：
循环状态表如下：
循环 红点集 K D[1] D[2] D[3] D[4] D[5] D[6] P[1] P[2] P[3] P[4] P[5] P[6]
初始化 {1} - 0 20 15 ∞ ∞ ∞ -1 1 1 -1 -1 -1
1 {1,3} 3 0 19 15 ∞ ∞ 25 -1 3 1 -1 -1 3
2 {1,3,2} 2 0 19 15 ∞ 29 25 -1 3 1 -1 2 3
3 {1,3,2,6} 6 0 19 15 29 29 25 -1 3 1 6 2 3
4 {1,3,2,6,4} 4 0 19 15 29 29 25 -1 3 1 6 2 3
5 {1,3,2,6,4,5} 5 0 19 15 29 29 25 -1 3 1 6 2 3
6 同上 - 同上 同上
从源点1到各点的路径如下所示：
1到2：132
1到3：13
1到4：1364
1到5：1325
1到6：136
整个执行算法过程中的扩充红点集的每次循环状态见上表。
7.13 试写出图7.28(下图)所示有向图的所有拓扑序列，并指出就用7.6节给出的NonPreFirstTopSort算法求得的是哪个序列，设邻接表的边表结点中的邻接点序号是递增有序的。
答：
上图中所有拓扑序列如下：
v0v1v5v2v3v6v4 *
v0v1v5v2v6v3v4
v0v1v5v6v2v3v4
v1v0v5v6v2v3v4
v1v0v5v2v3v6v4
v1v0v5v2v6v3v4
v1v5v0v2v3v6v4
v1v5v0v2v6v3v4
v1v5v0v6v2v3v4
v5v1v0v2v3v6v4
v5v1v0v2v6v3v4
v5v1v0v6v2v3v4
v5v0v1v2v3v6v4
v5v0v1v2v6v3v4
v5v0v1v6v2v3v4
v0v5v6v1v2v3v4
v1v5v6v0v2v3v4
v5v6v1v0v2v3v4
v5v6v0v1v2v3v4
v5v0v6v1v2v3v4
v5v1v6v0v2v3v4
用NonPreFirstTopSort算法求得的是v0v1v5v2v3v6v4也就是上面带*号的那个。
7.14 什么样的DAG的拓扑序列是唯一的?
答：
确定了排序的源点，DAG图中无前趋顶点只有一个且从该点到终点只有一条路径时，它的拓扑序列才是唯一的。
7.15 请以V0为源点，给出用DFS搜索图7.28(下图)得到的逆拓扑序列。
答：
逆拓扑序列是：V4 V2 V1 V0 V1 V6 V5