题目内容
(请给出正确答案)
[主观题]
计算连通网的最小生成树的Dijkstra算法可简述如下:将连通网所有的边以方便的次序逐条加人到初
始为空的生成树的边集合S中。每次选择并加人一条边时,需要判断它是否会与先前加人S中的边构成回路。如果构成了回路,则从这个回路中将权值(花费)最大的边退选。试设计一个求最小生成树的算法。要求以邻接矩阵作为连通网的存储结构,并允许在运算后改变邻接矩阵的结构。
提问人:网友13***002
发布时间:2022-01-07
//设图中总顶点数为n,总边数为m
将图中所有的边按其权值从大到小排序为;
若图不再连通,则恢复e1;(m=m+1);I=i+1;
(1)试间这个算法是否正确,并说明原因。
(2)以图8-44所示的图为例,写出执行以上算法的过程。
(1)将每个顶点视为一棵树,图中所有顶点形成一个森林;
(2)为每棵树选取一条边,它是该树与其他树相连的所有边中权值最小的一条边,把该边加入生成树中。如果某棵树选取的边已经被其他树选过,则该边不再选取。
重复以上操作,直到整个森林变成一棵树。
以图8-44所示的图为例,写出执行以上算法的过程。
为了保护您的账号安全,请在“简答题”公众号进行验证,点击“官网服务”-“账号验证”后输入验证码“”完成验证,验证成功后方可继续查看答案!