邻接多重表是无向图的另一种存储结构，边结点至少包括5个域：连接边的两个顶点在顶点向量中的下标，指向与该边相连接的两顶点的下一条边的指针，以及该边的标记信息（如该边是否被访问）。边结点的个数与边的个数相同，这是邻接多重表比邻接表优越之处。 11．
已知顶点i，找与i相邻的顶点j的规则如下：在顶点向量中，找到顶点i，顺其指针找到第一个边结点（若其指针为空，则顶点i无邻接点）。在边结点中，取出两顶点信息，若其中有j，则找到顶点j；否则，沿从i发出的另一条边的指针（ilink）找i的下一邻接点。在这种查找过程中，若边结点中有j，则查找成功；若最后ilink为空，，则顶点i无邻接点j。
12．按各顶点的出度进行排序。n个顶点的有向图，其顶点最大出度是n-1，最小出度为0。这样排序后，出度最大的顶点编号为1，出度最小的顶点编号为n。之后，进行调整，即若存在弧
13．采用深度优先遍历算法，在执行dfs(v)时，若在退出dfs(v)前，碰到某顶点u ，其邻接点是已经访问的顶点v，则说明v的子孙u有到v的回边，即说明有环，否则，无环。（详见下面算法题13）
14．深度优先遍历序列：125967384
宽度优先遍历序列：123456789 注：（1）邻接表不唯一，这里顶点的邻接点按升序排列
（2）在邻接表确定后，深度优先和宽度优先遍历序列唯一 （3）这里的遍历，均从顶点1开始 15．（1）V1V2V4V3V5V6 （2）V1V2V3V4V5V6 16.(1)
1 2 3 4 5 8 6 9 7 10
16题（3）宽度优先生成树
10 9 1 2 5 3 4 7 6 8 （2）深度优先生成树
为节省篇幅，生成树横画，下同。
17．设从顶点1开始遍历，则深度优先生成树(1)和宽度优先生成树(2)为： 1 4 3 2 1 2 3 4 5 5 图17(1) 图17(2) 18．遍历不唯一的因素有：开始遍历的顶点不同；存储结构不同；在邻接表情况下邻接点的顺序不同。 19．（1）邻接矩阵：（6*6个元素）*2字节/元素=72字节
邻接表：表头向量6*（4+2）+边结点9*(2+2+4)*2=180字节
邻接多重表：表头向量6*（4+2）+边结点9*（2+2+2+4+4）=162字节
邻接表占用空间较多，因为边较多，边结点又是边数的2倍，一般来说，邻接矩阵所占空间与边个数无关（不考虑压缩存储），适合存储稠密图，而邻接表适合存储稀疏图。邻接多重表边结点个数等于边数，但结点中增加了一个顶点下标域和一个指针域。 5 1 2 3 （2）因未确定存储结构，从顶点1开始的DFS树 1 6 5 4 不唯一，现列出两个：
20．未确定存储结构，其DFS树不唯一，其中之一（按邻接点逆序排列）是
1 8 9 3 10 2 7
4 6 5
（2）关节点有3，1，8，7，2 21．（1） A
F B C E D
（2）AFEDBC
4 2 6 3 22．设邻接表（略）中顶点的邻接点按顶点编号升序排列（V1编号为1）
（1） 广度优先搜索序列：V1V2V3V4V5V6V7V8 （2） 深度优先搜索序列：V1V2V4V8V5V3V6V7 23．（1）略 （2）V1V2V5V3V4V6 (4) V1V2V3V4V5V6 V1 (3) V4 (5) V6 V3 V4 V2
V1 V2 V5 V3 V6 V5 (6）见本章五算法设计第6题 24．设该图用邻接表存储结构存储，顶点的邻接点按顶点编号升序排列 (1)ABGFDEC (2)EACFBDG (3)
A 2 A 2 2 A A 2 D B D D 3 1 D 3 3 F F G G 1 F 3
A 2 A 2 4 D 4 D B C B C 3 3 E 1 3 F 3 F G 1 G 1
25．在有相同权值边时生成不同的MST，在这种情况下，用Prim或Kruskal也会生成不同的MST。
26．无向连通图的生成树包含图中全部n个顶点，以及足以使图连通的n-1条边。而最小生成树则是各边权值之和最小的生成树。从算法中WHILE（所剩边数>=顶点数）来看，循环到边数比顶点数少1（即n-1）停止，这符合n个顶点的连通图的生成树有n-1条边的定义；由于边是按权值从大到小排序，删去的边是权值大的边，结果的生成树必是最小生成树；算法中“若图不再连通，则恢复ei”，含义是必须保留使图连通的边，这就保证了是生成树，否则或者是有回路，或者成了连通分量，均不再是生成树。
27．Prim算法构造最小生成树的步骤如24题所示，为节省篇幅，这里仅用Kruskal算法，构造最小生成树过程如下：（下图也可选(2,4)代替(3,4),(5,6)代替(1,5)） 1 2 5 9 即 10 6 11 3 2 5 3 1 9 1 2 10 5 3 6 6 11 6 4 6 4 5 28．（1）最小生成树的定义见上面26题
（2）最小生成树有两棵。
（限于篇幅，下面的生成树只给出顶点集合和边集合，边以三元组（Vi,Vj,W）形式），其中W代表权值。
V（G）={1，2，3，4，5} E1(G)={(4，5，2)，（2，5，4），（2，3，5），（1，2，7）}；
E2(G)={(4，5，2），（2，4，4），（2，3，5），（1，2，
7）}
29．V（G）={1，2，3，4，5，6，7}
E（G）={（1，6，4），（1，7，6），（2，3，5），（2，4，8），（2，5，12），（1，2，18）} 30．V（G）={1，2，3，4，5，6，7，8}
E（G）={（3，8，2），（4，7，2），（3，4，3），（5，8，3），（2，5，4），（6，7，4），
1 1 2 1 1 2 4 3 1 3 1 6 5 （1，2，5）}
注：（或将（3，4，3）换成（7，8，3））
31．设顶点集合为{1，2，3，4，5，6}，
由右边的逻辑图可以看出，在{1，2，3}和{4，5，6}回路中， 各任选两条边，加上（2，4），则可构成9棵不同的最小生成树。 32．（1）邻接矩阵略 （2） Y Closedge Vex Lowcost Vex Lowcost Vex Lowcost Vex Lowcost Vex Lowcost Vex Lowcost Vex Lowcost Vex Lowcost 2 3 4 5 6 7 8 U {1} {1,2} {1,2,4} {1,2,4,3} {1,2,4,3,5} V-U {2,3,4,5,6,7,8} {3,4,5,6,7,8} {3,5,6,7,8} {5,6,7,8} {6,7,8} {7,8} {8} ① ① 2 3 ① ② 3 2 ④ 1 ④ ④ 2 4 ④ ④ 2 4 ⑤ ⑤ 1 2 ⑤ ⑥ {1,2,4,3,5,6} 2 4 ⑦ {1,2,4,3,5,6,7} 3 {1,2,4,3,5,6,7,8} {} 33.(1) (2) Pe
M N T Pa L (3)最小生成树6个顶点5条边：V(G)={Pe,N,Pa,L,T,M}
E(G)={(L,Pa,3),(Pe,T,21),(M,N,32),(L,N,55),(L,Pe,81)} 34.(1)
TYPE edgeptr=^enode；
enode=RECORD ivex,jvex:vtxptr; w:integer; jlink,ilink:edgeptr; END ; vexnode=RECORD data:vertertype; firstedge:edgeptr; END; adjmulist=ARRAY[vexptr] OF vexnode;
(2)深度优先遍历序列：1,4,6,5,3,2；
深度优先生成树的边集合：{(1,4),(4,6),(6,5),(5,3),(3,2)} (3)宽度优先遍历序列：143265；
宽度优先生成树的边集合：{(1,4),(1,3),(1,2),(4,6),(4,5)}： （4按Prim构造过程只画出最小生成树的边和权植：
E(G)={(1,4,3),(4,3,4),(3,5,1),(3,2,2),(3,6,10)} 35．E1(G)={（1，2，16），（2，3，5），（2，6，6），（2，4，11），（6，5，18）}，V(G)={1,2,3,4,5,6}
E2(G)={（1，2，16），（2，3，5），（3，6，6），（2，4，11），（6，5，18）} 36．
36（1）邻接矩阵和邻接表
b d 1 3 36（2）深度优先搜索序列:abcdehf; 36(3) 最小生成树 5 宽度优先搜索序列: abfcdef a c 4 f 2
e 3 37．A=
A=A=A=33 38．(1) (2)V1,V2,V4,V6,V3,V5 2 36 25 1
29 6 10 30 3 18 38 4
42
(3) 顶点集合V(G)={V1,V2,V3,V4,V5,V6}
0123
A=
1 2 4
4 5 6 3