最短路径问题
最短路径问题采用的算法是标号法，利用标号算法不仅可以求出从 Vs，到 Vt 的最短路径及它的长度，而且可以同时求出从 D 中 Vs，到所有顶点 Vs 的最短路及其长度，或者指出不存在从 Vs 到 Vj 的有向路径。这种标号算法仅适用于每条弧的长度都是非负数的情况。
求图从 V1 到各个顶点的最短路径的长度
最小生成树
树是图论中的一个重要概念，所谓树就是无圈的连通图。
树的示意
给定一个无向图 G = (V，E)，保留 G 的所有点，而删掉部分 G 的边或者保留一部分 G 的边，所获得的图就称之为生成子图。
如果图 G 的一个生成子图还是一个树，则称这个生成子图为生成树。所谓最小生成树的问题就是在一个赋权的、连通的无向图 G 中找出一个生成树，并使得这个生成树的所有边的权数之和为最小。最小生成树的求取方法有两种，分别是破圈法和避圈法，本文只介绍破圈法。
破圈法求最小生成树的具体步骤如下。
- 在给定的赋权的连通图上任找一个圈；
- 在所找的圈中去掉一条权数最大的边(如果有两条或两条以上的边都是权数最大的边，则任意去掉其中一条)；
- 如果所余下的图已不含圈，则计算结束，所余下的图即为最小生成树，否则返回步骤（1）。
例子
某大学准备对其所属的 7 个学院办公室的计算机联网，这个网络的可能联通途径如图所示。图中的边为可能联网的途径，边上的数值为路线长度。请设计一个网络能联通 7 个学院办公室，并使总的线路长度最短。
图解
网友评论