题目内容
（请给出正确答案）
[主观题]
试修改Prim算法，使之能在邻接表存储结构上实现求图的最小生成森林，并分析其时间复杂度(森林的存储结构为孩子一兄弟链表)。
试修改Prim算法，使之能在邻接表存储结构上实现求图的最小生成森林，并分析其时间复杂度（森林的存储结构为孩子一兄弟链表)。
如搜索结果不匹配，请 联系老师 获取答案
更多“试修改Prim算法，使之能在邻接表存储结构上实现求图的最小生…”相关的问题
第2题
试扩充深度优先搜索算法，在遍历图的过程中建立生成森林的子女-兄弟链表。算法的首部为其中，指
试扩充深度优先搜索算法，在遍历图的过程中建立生成森林的子女-兄弟链表。算法的首部为
其中，指针t指向生成森林上具有图顶点v信息的根结点。(提示：在继续按深度方向从根v的某一未访问过的邻接顶点w向下遍历之前，建立子女结点。但需要判断是作为根的第一个子女还是作为其子女的右兄弟链入生成树)
第4题
设有向图具有n个顶点和e条边，如果用邻接表作为它的存储结构，则拓扑排序的时间复杂度为()
设有向图具有n个顶点和e条边，如果用邻接表作为它的存储结构，则拓扑排序的时间复杂度为（)
点击查看答案
A、O(n)
B、O(n+e)
C、O(n2)
D、O(n×e)
第5题
在森林的二叉树表示中，用llink存储指向结点第一个子女的指针，用rlink存储指向结点下一个兄弟
的指针，用data存储结点的值。如果我们采用静态二叉链表作为森林的存储表示，同时按森林的先根次序依次安放森林的所有结点，则可以在它们的结点中用只有一个二进位的标志Itag代替Ilink，用rtag代替rlink。并设定若Itag=0，则该结点没有子女，若Itag≠0.则该结点有子女;若rtag=0，则该结点没有下一个兄弟，若rtag不等于0.则该结点有下一个兄弟。试给出这种表示的结构定义，并设计一个算法，将用这种表示存储的森林转换成用Ilink-rIlink表示的森林。
点击查看答案
第6题
编写一个完整的程序，首先定义堆和并查集的结构类型和相关操作，再定义Kruskal求连通网络的最小
生成树算法的实现。并以图8-17为例，写出求解过程中堆、并查集和最小生成树的变化。
点击查看答案
第7题
在一个有n个顶点的带权连通图中，有条边，则应该选用()算法来求这个图的最小生成树，从而使计算
在一个有n个顶点的带权连通图中，有条边，则应该选用（)算法来求这个图的最小生成树，从而使计算
点击查看答案
在一个有n个顶点的带权连通图中，有
条边，则应该选用()算法来求这个图的最小生成树，从而使计算时间较少，
A、Prim
B、Kruskal
第8题
对用邻接矩阵表示的图进行任一种遍历时，其时间复杂度为(①)，对用邻接表表示的图进行任一种历时，其时间复杂度为(②)。
对用邻接矩阵表示的图进行任一种遍历时，其时间复杂度为（①)，对用邻接表表示的图进行任一种历时，其时间复杂度为（②)。
点击查看答案
第9题
计算连通网的最小生成树的Dijkstra算法可简述如下：将连通网所有的边以方便的次序逐条加人到初
始为空的生成树的边集合S中。每次选择并加人一条边时，需要判断它是否会与先前加人S中的边构成回路。如果构成了回路，则从这个回路中将权值(花费)最大的边退选。试设计一个求最小生成树的算法。要求以邻接矩阵作为连通网的存储结构，并允许在运算后改变邻接矩阵的结构。
点击查看答案
热门考试
全部 >
相关试卷
全部 >
