加权图的类型有两种: 顶点加权和边加权。在顶点加权图中，每个顶点都分配了一个权值。在边加权图中，每条边都分配一个权值。这两种类型中，边加权图应用更广泛。
加权图与非加权图的表示方法一样，除非必须表示边的权值。加权图的顶点与非加权图一样，都存储在一个数组里。
加权边的表示:边数组
加权邻接矩阵
优先邻接链表
WeightedGraph类
WeightedGraph用四个创建具体WeightedGraph实例的构造方法来扩展AbstractGraph。WeightedGraph继承
AbstractGraph的所有方法，并且引入新的方法来获取最小生成树并找出单源所有最短路径
最小生成树
一副加权无向图的最小生成树(MST)是一棵权值之和最小的生成树。而生成树则是一棵含有所有顶点的无环连通子图。
最小生成树算法：
1.Prim算法 2.Kruskal算法
这两个算法的本质都是贪心算法，都是基于切分定理得到的。
切分定理
在一幅加权图中，给定任意切分，它的横切边中的权重最小者必然属于最小生成树。
上面两个最小生成树算法都是贪心算法，在保证最小生成树的基础上，选择边的算法。
当然，作为一个算法的使用者，我们更关心的是算法实现本身，这里提到切分定理只是表明，这两个算法是有理论依据的，可以放心使用。
当然，在完成最小生成树算法之前，我们第一步首先是要确定数据结构。
我们使用什么样的方式来表示加权无向图呢？
在非加权无向图中，我们使用邻接表矩阵的方式来保存无向图。而对于加权无向图，我们也采用同样的方式。但是不同的是，加权无向图有着非加权无向图的别的特性，那就是我们还需要保存 边的权重的信息。所以我们定义一个Edge边类，其中有weight属性，用来保存权重信息。
增加一个小小的修改就成了这样：
public class Edge { // 图的边
private int v; // 另外一个
private double weight; // 边的权重
}
但是呢，邻接表矩阵用List<>[]数组表示，调用add方法会增加引用。所以我们不妨这样：
public class Edge { // 图的边
private int v; // 其中一个节点
private int w; // 另一个节点
private double weight; // 边的权重
将两条边的顶点都保存下来，这样的话，虽然看上去好像增加了冗余的信息，因为邻接表矩阵的下标就是当前的顶点。
其实并非是这样的，例如v-w。那么就存在Edge对象e，那邻接表矩阵v可以指向e，w也可以指向e。这样，我们就可以少创建一半的类。减小了内存的开销。
网友评论