对于下图，试利用克鲁斯卡尔算法（Kruskal)求图的最小生成树，并写出其构造过程。

判断一个有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用_________。

A．深度优先搜索遍历算法

B．广度优先搜索遗历算法

C．普里姆算法

D．克鲁斯卡尔算法

使用_______算法可以确定从源点到图中其余顶点的最短路径。

A．迪杰斯特拉

B．弗洛伊德

C．克鲁斯卡尔

D．普里姆

A.边稠密，边稀疏

B.边稀疏，边稠密

C.边稠密，边稠密

D.边稀疏，边稀疏

对于下图，按迪杰斯特拉(Dijkstra)算法求从顶点a到其他各顶点的最短路径，并给出辅助数组中值的变化过程。

试证：如果LP的目标函数有下界，则对于原仿射尺度算法，必有下式成立：

从而有

1．试证：如果LP的目标函数有下界，则对于原仿射尺度算法，必有下式成立：

从而有

A.经验估算法

B.查表修正法

C.分析计算法

D.试切法