A.边稠密,边稀疏
B.边稀疏,边稠密
C.边稠密,边稠密
D.边稀疏,边稀疏
A.迪杰斯特拉(Dijkstra)算法
B.克鲁斯卡尔(Kruskal)算法
C.普里姆(Prim)算法
D.广度优先遍历(BFS)算法
程分为若于阶段,每一阶段选取若干条边.算法思路如下:
(1)将每个顶点视为一棵树,图中所有顶点形成一个森林;
(2)为每棵树选取一条边,它是该树与其他树相连的所有边中权值最小的一条边,把该边加入生成树中。如果某棵树选取的边已经被其他树选过,则该边不再选取。
重复以上操作,直到整个森林变成一棵树。
以图8-44所示的图为例,写出执行以上算法的过程。
下面是求无向连通图的最小生成树的一种算法:
//设图中总顶点数为n,总边数为m
将图中所有的边按其权值从大到小排序为;
若图不再连通,则恢复e1;(m=m+1);I=i+1;
(1)试间这个算法是否正确,并说明原因。
(2)以图8-44所示的图为例,写出执行以上算法的过程。
A.生成树算法的核心是在网络中生成一棵树,然后所有的数据转发都从树根向各个节点转发,这样就不可能发生广播风暴
B.如果网络中有环路,运行生成树算法通过阻塞掉一些链路以消除环路
C.生成树算法中的树根可以人为控制
D.一个局域网中,可能有多棵生成树