对于含有N个顶点E条边的无向连通图，利用Kruskal算法生成最小代价生成树的时间复杂度为（）。
题目
对于含有N个顶点E条边的无向连通图，利用Kruskal算法生成最小代价生成树的时间复杂度为（）。
相似考题
更多“对于含有N个顶点E条边的无向连通图，利用Kruskal算法生成最小代价生成树的时间复杂度为（）。”相关问题
-
第1题：
对(),用Prim算法求最小生成树较为合适,而Kruskal算法适于构造()图的最小生成树。A.完全图
B.连通图
C.稀疏图
D.稠密图
参考答案：D,C
-
第2题：
下列叙述中正确的是（ ）。A．连通分量是无向图中的极小连通子图 B．生成树是连通图的一个极大连通子图 C．若一个含有n个顶点的有向图是强连通图，则该图中至少有n条弧 D．若一个含有n个顶点的无向图是连通图，则该图中至少有n条边
正确答案：C
有向图是一个二元组 -
第3题：
对于含有n个顶点的带权连通图，它的最小生成树是指()。A.图中任意一个由n-l条权值最小的边构成的子图
B.图中任意一个由n-1条权值之和最小的边构成的子图
C.图中任意一个由n-1条权值之和最小的边构成的连通子图
D.图中任意一个由n个顶点构成的边的权值之和最小的连通子图答案：D解析：一个连通图的生成树(连通无回路图)是一个极小连通子图。它含有图中全部n个项点，但只有构成一棵树的(n-1)条边。如果小于(n-1)条边，则是非连通图；如果多于(n-1)条边，则一定有回路，因为这条边使得它依附的那两个顶点之间有了第二条路径。但是，有(n-1)条边的图不一定都是生成树。带权连通无向图的所有生成树中具有边上的权值之和最小的树称为图的最小生成树。总之，含有n个顶点的带权连通图，它的最小生成树是指图中任意一个由n个顶点构成的边的权值之和最小的连通子图。 -
第4题：
Prim算法和Kruscal算法都是无向连通网的最小生成树的算法，Prim算法从一个顶点开始，每次从剩余的顶点中加入一个顶点，该顶点与当前的生成树中的顶点的连边权重最小，直到得到一颗最小生成树；Kruscal算法从权重最小的边开始，每次从不在当前的生成树顶点中选择权重最小的边加入，直到得到一颗最小生成树，这两个算法都采用了（请作答此空）设计策略，且（ ）。A.分治
B.贪心
C.动态规划
D.回溯答案：B解析：Prim算法和Kruscal算法都是基于贪心算法的应用。Prim算法的时间复杂度为O（n2），与图中边数无关，该算法适合于稠密图。Kruskal算法的时间复杂度只和边有关系，为O（elog2e），由于Kruskal算法只与边有关，因此适合求稀疏图的最小生成树。 -
第5题：
对于一个带权连通图，在什么情况下，利用普里姆（Prim）算法与利用克鲁斯卡尔（Kruskal）算法可能生成不同的最小生成树？
正确答案:当图中出现权值相同的边时，利用普里姆(Prim)算法与利用克鲁斯卡尔(Kruskal)算法可能生成不同的最小生成树。 -
第6题：
连通图G的生成树是一个包含G的所有n个顶点和n-1条边的子图。
正确答案:错误 -
第7题：
对于含有n个顶点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为（），利用Kruskal算法求最小生成树的时间复杂度为（）。
正确答案:O（n2）；O（elog2e） -
第8题：
由一个具有n个顶点的连通图生成的最小生成树中，具有（）条边。
- A、 n
- B、 n-1
- C、 n+1
- D、 2×n
正确答案:B -
第9题：
填空题一个连通图的生成树是该图的（）连通子图。若这个连通图有n个顶点，则它的生成树有（）条边。正确答案： 极小（最小）,n-1解析： 暂无解析 -
第10题：
单选题由一个具有n个顶点的连通图生成的最小生成树中，具有（）条边。An
Bn-1
Cn+1
D2×n
正确答案： D解析： 暂无解析 -
第11题：
问答题对于一个带权连通图，在什么情况下，利用普里姆（Prim）算法与利用克鲁斯卡尔（Kruskal）算法可能生成不同的最小生成树？正确答案： 当图中出现权值相同的边时，利用普里姆(Prim)算法与利用克鲁斯卡尔(Kruskal)算法可能生成不同的最小生成树。解析： 暂无解析 -
第12题：
单选题n个顶点的带权无向连通图的最小生成树包含（）个顶点。An-1
Bn
Cn/2
Dn+1
正确答案： B解析： 暂无解析 -
第13题：
对于含n个顶点、e条边的无向连通图,利用Prim算法构造最小生成树的时间复杂度(),用Kruskal算法构造最小生成树的时间复杂度为()。A.O(n)
B.O(n²)
C.O(e)
D.O(eloge)
F.O(e²)
参考答案：B,D
-
第14题：
Prim算法和Kruscal算法都是无向连通网的最小生成树的算法，Prim算法从一 个顶点开始，每次从剩余的顶点加入一个顶点，该顶点与当前生成树中的顶占的连边权重 最小，直到得到最小生成树开始，Kruscal算法从权重最小的边开始，每次从不在当前的生成树顶点之间的边中选择权重最小的边加入，直到得到一颗最小生成树，这两个算法都采用了（ ）设计策略，且（ ）。
A.分治 B.贪心 C.动态规划 D.回溯 A.若网较稠密，则Prim算法更好 B.两个算法得到的最小生成树是一样的 C.Prim算法比Kruscal算法效率更高 D.Kruscal算法比Prim算法效率更高
正确答案：B,A
-
第15题：
Prim算法和Kruscal算法都是无向连通网的最小生成树的算法，Prim算法从一个顶点开始，每次从剩余的顶点中加入一个顶点，该顶点与当前的生成树中的顶点的连边权重最小，直到得到一颗最小生成树；Kruscal算法从权重最小的边开始，每次从不在当前的生成树顶点中选择权重最小的边加入，直到得到一颗最小生成树，这两个算法都采用了（64）设计策略，且（65）。A.若网较稠密，则Prim算法更好
B.两个算法得到的最小生成树是一样的
C.Prim算法比Kruscal算法效率更高
D.Kruscal算法比Prim算法效率更高答案：A解析：Prim算法和Kruscal算法都是基于贪心算法的应用。Prim算法的时间复杂度为O(n2)，与图中边数无关，该算法适合于稠密图。Kruskal算法的时间复杂度只和边有关系，为O(elog2e)，由于Kruskal算法只与边有关，因此适合求稀疏图的最小生成树。 -
第16题：
Prim算法和Kruscal算法都是无向连通网的最小生成树的算法，Prim算法从一个顶点开始，每次从剩余的顶点中加入一个顶点，该顶点与当前的生成树中的顶点的连边权重最小，直到得到一颗最小生成树；Kruscal算法从权重最小的边开始，每次从不在当前的生成树顶点中选择权重最小的边加入，直到得到一颗最小生成树，这两个算法都采用了（64）设计策略，且（65）。A.分治
B.贪心
C.动态规划
D.回溯答案：B解析：Prim算法和Kruscal算法都是基于贪心算法的应用。Prim算法的时间复杂度为O(n2)，与图中边数无关，该算法适合于稠密图。Kruskal算法的时间复杂度只和边有关系，为O(elog2e)，由于Kruskal算法只与边有关，因此适合求稀疏图的最小生成树。 -
第17题：
n个顶点的带权无向连通图的最小生成树包含（）个顶点。
- A、n-1
- B、n
- C、n/2
- D、n+1
正确答案:B -
第18题：
图的生成树（），n个顶点的生成树有（）条边。
正确答案:唯一性不能确定；n-1 -
第19题：
一个连通图的生成树是该图的（）连通子图。若这个连通图有n个顶点，则它的生成树有（）条边。
正确答案:极小（最小）；n-1 -
第20题：
对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数和边数分别为（）和（）。
正确答案:n；n-1 -
第21题：
填空题对于含有N个顶点E条边的无向连通图，利用Kruskal算法生成最小代价生成树的时间复杂度为（）。正确答案： o（elg0）解析： 暂无解析 -
第22题：
填空题对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数和边数分别为（）和（）。正确答案： n,n-1解析： 暂无解析 -
第23题：
填空题对于含有n个顶点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为（），利用Kruskal算法求最小生成树的时间复杂度为（）。正确答案： O（n2）,O（elog2e）解析： 暂无解析