今天在做题的时候遇到一个问题，如何根据图的邻接表来画出DFS生成树和BFS生成树，有两年的真题中涉及到这个问题，在以前的学习中没注意过此问题，由于严奶奶的书上也只是一带而过，所以对它的理解也不深刻，作为基础的知识应该掌握，因此从网上查阅了一些资料，针对这个问题做如下总结，由于提到生成树自然会想到还有一种最小生成树，顺便把生成最小生成树的方法也总结一下，做出更好的区分，给需要的同学提供一个方便：
一．生成树
1. 生成树：是一个极小连通子图，它含有图中全部顶点，但只有n-1条边。
2. DFS生成树：由深度优先搜索遍历得到的生成树，称为深度优先生成树。
3. BFS生成树：由广度优先搜索遍历得到的生成树，称为广度优先生成树。
例1：无向图G7的两种生成树（从顶点1开始）：
说明：使用不同的遍历图的方法，可以得到不同的生成树；从不同的顶点出发，也可能得到不同的生成树。
例2：画出下图的生成树
1）邻接表：
要会根据图的邻接表画出DFS,BFS生成树。
2）DFS生成树： 3）BFS生成树：
/*------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------*/
二．最小生成树（MST：Minimum cost SpanningTree）
1. 最小生成树：n个顶点的生成树很多，最小生成树就需要从这很多树中选一棵代价最小的生成树（即该树各边的代价之和最小）。
2. 构造最小生成树的准则
1） 必须只使用该网络中的边来构造最小生成树；
2） 必须使用且仅使用n-1条边来联络网络中的n个顶点；
3） 不能使用产生回路的边。
3. 两种方法：Prime, Kruskal
//严奶奶书上是用表格的形式列出来最小生成树的过程，我觉得那样做挺麻烦的，在下面详细过程之后我描述了一种画线的方法，这种方法来的更容易一些。
1) Prime
i 1 2 3 4 5 6 Closest[i] 1 1 1 1 1 1 Lowcost[i] 0 6 1 5 ∞ ∞ (b)
（Closest[i]用于存放顶点序号，Lowcost[i]存放权值）
i
1
2
3
4
5
6
Closest[i]
1
3
1
1
3
3
Lowcost[i]
0
5
0
5
5
4
(c)
i
1
2
3
4
5
6
Closest[i]
1
3
1
6
3
3
Lowcost[i]
0
5
0
2
5
0
(d)
i
1
2
3
4
5
6
Closest[i]
1
3
1
6
3
3
Lowcost[i]
0
5
0
0
5
0
(e)
i
1
2
3
4
5
6
Closest[i]
1
3
1
6
2
3
Lowcost[i]
0
0
0
0
3
0
(f)
i
1
2
3
4
5
6
Closest[i]
1
3
1
6
2
3
Lowcost[i]
0
0
0
0
0
0
(g)
画线方法
根据每条画的线所穿过的线段就可以找到最小的权值边，比如从顶点1开始，然后画一条黑线，黑线穿过的线段对应的权值分别为6，1，5，可见1是最小的，所以连接顶点1与顶点3，然后把顶点1顶点3作为一个整体，画出红色线条，红色线穿过的线段有6，5，6，4，5，5，最小的是4，所以连接顶点3和顶点6，然后把顶点1顶点3顶点6作为一个整体，按照这种方法，依次类推，便可得到最小生成树。
2) Kruskal
Kruskal的思想我觉得比Prime要容易得多，利用上面的无向图，使用Kruskal生成最小生成树的过程：
