10．下面的邻接表表示一个给定的无向图，
（1）给出从顶点v1开始，对图G用深度优先搜索法进行遍历时的顶点序列； （2）给出从顶点v1开始，对图G用广度优先搜索法进行遍历时的顶点序列。
参考答案：（1）V1V2V4V3V5V6；（2）V1V2V3V4V5V6。
11．设G=(V,E)以邻接表存储，如图所示，试画出图的深度优先和广度优先生成树。
234?1
5?1342
124?3
12 35?4 24?5
参考答案：
深度优先生成树：
广度优先生成树：
12．对一个图进行遍历可以得到不同的遍历序列，那么导致得到的遍历序列不唯一的因素有哪些？ 参考答案：
遍历不唯一的因素有：开始遍历的顶点不同；存储结构不同；在邻接表情况下邻接点的顺序不同。
13．某田径赛中各选手的参赛项目表如下: 姓名 参 赛 项 ZHAO A B E QIAN C D SHUN C E F LI D F A ZHOU B F 设项目A,B ,?，F各表示一数据元素，若两项目不能同时举行，则将其连线(约束条件)。 （1）根据此表及约束条件画出相应的图状结构模型，并画出此图的邻接表结构； （2）写出从元素A出发按“广度优先搜索”算法遍历此图的元素序列。 参考答案：
（1）
（2）AFEDBC或ABDEFC。
14．已知无向图如下所示：（1）给出从V1开始的广度优先搜索序列；（2）画出它的邻接表；（3）画出从V1开始深度优先搜索生成树。
参考答案：
设邻接表（略）中顶点的邻接点按顶点编号升序排列（V1编号为1），广度优先搜索序列：V1V2V3V4V5V6V7V8；深度优先搜索序列：V1V2V4V8V5V3V6V7。
15．已知某图的邻接表为
v1v2v3v4v5v6211124?35563????4? （1）写出此邻接表对应的邻接矩阵；
（2）写出由v1开始的深度优先遍历的序列； （3）写出由v1开始的深度优先的生成树； （4）写出由v1开始的广度优先遍历的序列； （5）写出由v1开始的广度优先的生成树；
（6）写出将无向图的邻接表转换成邻接矩阵的算法。 参考答案： （1）略。
（2）V1V2V5V3V4V6
（3）
（4）V1V2V3V4V5V6
（5）
（6）void AdjListToAdjMatrix(AdjList gl, AdjMatrix gm)
//将图的邻接表表示转换为邻接矩阵表示。
{for (i=1;i<=n;i++) //设图有n个顶点，邻接矩阵初始化。 for (j=1;j<=n;j++) gm[i][j]=0; for (i=1;i<=n;i++)
{p=gl[i].firstarc; //取第一个邻接点。
while (p!=null) {gm[i][p->adjvex]=1;p=p->next; }//下一个邻接点 }//for }//算法结束
16．考虑右图：
（1）从顶点A出发，求它的深度优先生成树； （2）从顶点E出发，求它的广度优先生成树；
（3）根据普利姆（Prim）算法，求它的最小生成树。 参考答案：
设该图用邻接表存储结构存储，顶点的邻接点按顶点编号升序排列
（1）ABGFDEC
（2）EACFBDG
（3）
17．在什么情况下，Prim算法与Kruskual算法生成不同的MST？ 参考答案：
在有相同权值边时生成不同的MST，在这种情况下，用Prim或Kruskal也会生成不同的MST。
18．已知一个无向图如下图所示，要求分别用Prim和Kruskal算法生成最小树（假设以①为起点，试画出构造过程）。
参考答案：
Prim算法构造最小生成树的步骤：(1,6),(1,5),(6,2),(2,3),(3,4)
Kruskal算法，构造最小生成树过程：(2,3),(3,4) (或(2,4)),(1,6),(5,6)（或(1，5)）,(2,6)
19．G=(V,E)是一个带有权的连通图，则：
（1）请回答什么是G的最小生成树；
（2）G为下图所示，请找出G的所有最小生成树。 参考答案：
（2）2棵：和
20．试写出用克鲁斯卡尔（Kruskal）算法构造下图的一棵最小生成树的过程。
参考答案：
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），（
21．求出下图的最小生成树。
1，2，18）}
参考答案：
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，2，5）}
注：（或将（3，4，3）换成（7，8，3））
22．一带权无向图的邻接矩阵如下图 ，试画出它的一棵最小生成树。
参考答案：
设顶点集合为{1，2，3，4，5，6}，由右边的逻辑图可以看出，在{1，2，3}和{4，5，
6}回路中，各任选两条边，加上（2，4），则可构成9棵不同的最小生成树。
23．下图表示一个地区的通讯网，边表示城市间的通讯线路，边上的权表示架设线路花费的代价，如何选择能沟通每个城市且总代价最省的n-1条线路，画出所有可能的选择。
参考答案：
V(G)={1,2,3,4,5,6}
E1(G)={（1，2，16），（2，3，5），（2，6，6），（2，4，11），（6，5，18）}， E2(G)={（1，2，16），（2，3，5），（3，6，6），（2，4，11），（6，5，18）}
24．设无向网G如下：