单选题 软件设计师
题号 #583589

根据下列题干,回答题:
某有向图中含有n个顶点,则其有向边的数目最多为( 1 )。对于n个顶点k条边的无向连通图,利用Prim算法生成最小生成树的时间复杂度为( 2 ),利用Kruskal算法生成最小生成树的时间复杂度为( 3 )。
请选择( 1 )处最佳答案

进入在线模考

参考答案

C

答案解析

边最多的情况是:每个顶点到其他点均有一条边。此时没点有n一1条边,于是n个点共有n(n-1)条,由于是有向图,各边并不重复。利用Prim算法生成最小生成树的时间复杂度只与顶点数有关,复杂度为o(n2);Kruskal算法生成最小生成树的时间复杂度只与边数有关,为0(klog2k)。

你可能感兴趣的试题

找试题 · 找答案 · 找资料 在线模考