题目内容
(请给出正确答案)
[主观题]
用Prim 算法构造图所示的连通图的最小代价生成树。
用Prim 算法构造图所示的连通图的最小代价生成树。
提问人:网友nhwsin
发布时间:2022-01-07
A、稀疏有向图(连接边比较少)应用Prim算法,稠密图(连接边比较多)应用Kruskal算法。
B、稀疏有向图(连接边比较少)应用Kruskal算法,稠密图(连接边比较多)应用Prim算法。
C、稀疏有向图(连接边比较少)和稠密图(连接边比较多)都应用Kruskal算法。
D、稀疏有向图(连接边比较少)和稠密图(连接边比较多)都应用Prim算法。
A、每个带权图都有唯一的最小生成树。
B、连通图上各边权值均不相同,则该图的最小生成树可能有多个。
C、求最小生成树的Prim算法中边上的权可正可负。
D、最小生成树的Kruskal算法是一种贪心算法。
(1)将每个顶点视为一棵树,图中所有顶点形成一个森林;
(2)为每棵树选取一条边,它是该树与其他树相连的所有边中权值最小的一条边,把该边加入生成树中。如果某棵树选取的边已经被其他树选过,则该边不再选取。
重复以上操作,直到整个森林变成一棵树。
以图8-44所示的图为例,写出执行以上算法的过程。
A、BE1、AF2、ED3、BA4、AC6
B、BE1、ED3、BA4、AF2、AC6
C、AB4、BE1、ED3、AF2、AC6
D、BE1、AF2、BA4、ED3、AC6
为了保护您的账号安全,请在“简答题”公众号进行验证,点击“官网服务”-“账号验证”后输入验证码“”完成验证,验证成功后方可继续查看答案!