最小生成树
本篇我们会聊聊最小生成树，最小生成树和之前的无向图最大的区别是这个每一条边都是带有权重的。在聊最小生成树之前 我们要先聊两个理念，因为最小生成树是基于这两个理念的基础上得到的相关数据结构算法。
首先我们先了解下切分定理。在一幅加权图中，给定任意的切分，他的横切边中权重最小者必然属于图的最小生成树。找个可以想想下要是3个节点形成换的一个节点图， 要是不把最小的边加进去，那么必然要把另外两个节点加入图中 而剩下的两条边之和肯定小于最小的边在加上随机一条边，所以可以得到这个定理。
第二 是我们常见的一个贪心算法，这个大家都熟所以不细述了。 在这里的应用就是找到最小生成树的一条边，不断重复直到找到最小生成树的所有边。
而最小生成树也主要用到了这两种理念，我先找到最小的一条边，生成一副图，然后找所有节点到这副图最小的权重，然后加入这图中，直至所有节点全部加入为止，这个最小生成树就算完成了，如下图。
现在常用在最小生成树的算法代码是prim算法
package com.jimmysun.algorithms.chapter4_3;
import com.jimmysun.algorithms.chapter1_3.Queue;
import edu.princeton.cs.algs4.IndexMinPQ;
public class Ex22PrimMST {
private Edge[] edgeTo;
private double[] distTo;
private boolean[] marked;
private IndexMinPQ<Double> pq;
public Ex22PrimMST(EdgeWeightedGraph G) {
edgeTo = new Edge[G.V()];
distTo = new double[G.V()];
marked = new boolean[G.V()];
for (int v = 0; v < G.V(); v++) {
distTo[v] = Double.POSITIVE_INFINITY;
}
pq = new IndexMinPQ<Double>(G.V());
for (int v = 0; v < G.V(); v++) {
if (!marked[v]) {
distTo[v] = 0.0;
pq.insert(v, 0.0);
while (!pq.isEmpty()) {
visit(G, pq.delMin());
}
}
}
}
private void visit(EdgeWeightedGraph G, int v) {
marked[v] = true;
for (Edge e : G.adj(v)) {
int w = e.other(v);
if (marked[w]) {
continue;
}
if (e.weight() < distTo[w]) {
edgeTo[w] = e;
distTo[w] = e.weight();
if (pq.contains(w)) {
pq.changeKey(w, distTo[w]);
} else {
pq.insert(w, distTo[w]);
}
}
}
}
public Iterable<Edge> edges() {
Queue<Edge> mst = new Queue<>();
for (Edge edge : edgeTo) {
if (edge != null) {
mst.enqueue(edge);
}
}
return mst;
}
}具体应用 ：如电路，图像分析，航空等等
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2018-08-08，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读