试修改Prim算法，使之能在邻接表存储结构上实现求图的最小生成森林，并分析其时间复杂度(森林的存储结构为孩子一兄弟链表)。

试扩充深度优先搜索算法，在遍历图的过程中建立生成森林的子女-兄弟链表。算法的首部为其中，指针t指向生成森林上具有图顶点v信息的根结点。(提示：在继续按深度方向从根v的某一未访问过的邻接顶点w向下遍历之前，建立子女结点。但需要判断是作为根的第一个子女还是作为其子女的右兄弟链入生成树)

31为例检验算法的正确性。

设有向图具有n个顶点和e条边，如果用邻接表作为它的存储结构，则拓扑排序的时间复杂度为（)

A、O(n)

B、O(n+e)

C、O(n²)

D、O(n×e)

的指针，用data存储结点的值。如果我们采用静态二叉链表作为森林的存储表示，同时按森林的先根次序依次安放森林的所有结点，则可以在它们的结点中用只有一个二进位的标志Itag代替Ilink，用rtag代替rlink。并设定若Itag=0，则该结点没有子女，若Itag≠0.则该结点有子女;若rtag=0，则该结点没有下一个兄弟，若rtag不等于0.则该结点有下一个兄弟。试给出这种表示的结构定义，并设计一个算法，将用这种表示存储的森林转换成用Ilink-rIlink表示的森林。

生成树算法的实现。并以图8-17为例，写出求解过程中堆、并查集和最小生成树的变化。

在一个有n个顶点的带权连通图中，有条边，则应该选用（)算法来求这个图的最小生成树，从而使计算

在一个有n个顶点的带权连通图中，有条边，则应该选用()算法来求这个图的最小生成树，从而使计算时间较少，

A、Prim

B、Kruskal

对用邻接矩阵表示的图进行任一种遍历时，其时间复杂度为（①)，对用邻接表表示的图进行任一种历时，其时间复杂度为（②)。

始为空的生成树的边集合S中。每次选择并加人一条边时，需要判断它是否会与先前加人S中的边构成回路。如果构成了回路，则从这个回路中将权值(花费)最大的边退选。试设计一个求最小生成树的算法。要求以邻接矩阵作为连通网的存储结构，并允许在运算后改变邻接矩阵的结构。