试题详情
- 简答题简述Kruskal算法的作用和具体步骤。
- K.ruskal算法用于最小生成树问题求解。对于有n个顶点的图G=（V，E），Kruskal算法根据图G中所有n个顶点生成一个包括n棵只有根结点的树Ti（i=0，1，…，n-1）的森林F，并按照以下规则森林F中的树合并，形成最小生成树：
A.从边集合E中选取未被访问过且具有最小权的边，置该边状态为已访问。判断该边的两个顶点是否属于不同的树，若属于不同的树则使用该边将两棵树合并为一棵；若属于同一棵树则不做任何处理。
B.重复上一步骤直至森林F中只剩下一棵树，该树即是图G的最小生成树。若最后森林F中剩下不止一棵树，则说明图G是非连通图或非强连通图，在这种情况下不存在最小生成树。 关注下方微信公众号，在线模考后查看
热门试题
- 下面程序段的时间复杂性的量级为（）
- 一种逻辑结构（）。
- 若循环队列有 n个顺序存储单
- 下列选项中是结构体普通变量或指针变量引用
- 假定一棵三叉树的结点个数为50，则它的最
- 如下图所示，若从顶点a出发，按图的广度优
- 设指针变量front表示链式队列的队头指
- 单链表不是一种随机存储结构。
- 数据结构中，算法要便于阅读、理解和交流；
- 在表长为n的链表中进行顺序查找，它的平均
- KMP算法的最大特点是指示主串的指针不需
- 画出无向图G1的邻接矩阵和邻接表示意图，
- 空间复杂度
- 数据结构中，以下是算法的设计要求是（）。
- 假设在算法描述语言中引入指针的二元运算“
- 求子串函数 的结果是（）
- 在非递归调用的情况下，数据区的分配方法采
- 广度优先周游一棵二叉树所得到的结点序列，
- 连通图G的生成树是一个包含G的所有n个顶
- 直接插入排序算法的时间复杂度为（）。