数据结构（六）图的存储、遍历

根据深度优先遍历的规则，0->1->3->4->2到这里就断了，选一个未被访问的结点作为起点继续访问，可以选5，5->6；将两个连起来，便是答案B。
该题选B

每次遍历都会利用到队列
该题选B

1->2->4 1,2,4
2->5 5
4->3 3
所以遍历顺序为1,2,4,5,3
该题选C

因为DFS是对树的分支进行深入遍历，所以生成树会比较高
该题选D

构造最小生成树的算法主要有Prim算法和Kruskal算法 Prim算法是直接查找，多次查询邻边权重的最小值，适合边的权重变化不大的情况。
Kruskal算法是先将权重排序后再进行查找，适用于边的权重变化频繁的情况。 既然是稠密图，那么权值变化并不大，该题选D
注：Floyd算法和Dijkstra算法均用于求解最短路径。

因为有2e>=n，可推断出每两个点之间均有边，即e>=n-1,所以按深度优先遍历的时间复杂度算即为：O(n+n-1)，即为O(n)
该题选C

深度优先遍历类似于二叉树的先序遍历，广度优先遍历类似于二叉树的层序遍历。
该题选A

拓扑排序需要先找到入度为0的点，但是环中不存在入度为0的点。
该题选A