目录
生成树（Spanning Tree）
最小生成树（Minimum Spanning Tree）
切分定理
Prim算法
Prim算法 – 执行过程
Prim算法 – 实现
Kruskal算法
Kruskal算法 – 执行过程
Kruskal算法 – 实现
Prim算法、Kruskal算法中使用的最小堆和并查集
最小堆
并查集
生成树（Spanning Tree）
生成树(Spanning Tree),也称为支撑树, 连通图的极小连通子图, 它含有图中全部的 n 个顶点,恰好只有 n – 1 条边
最小生成树（Minimum Spanning Tree）
最小生成树(Minimum Spanning Tree, 简称MST) (1) 也称为最小权重生成树(Minimum Weight Spanning Tree)、最小支撑树 (2) 是所有生成树中，总权值最小的那棵 (3) 适用于有权的连通图(无向)
最小生成树在许多领域都有重要的作用，例如: 要在 n 个城市之间铺设光缆，使它们都可以通信, 铺设光缆的费用很高, 铺且各个城市之间因为距离不同等因素, 铺设光缆的费用也不同, 如何使铺设光缆的总费用最低？
如果图的每一条边的权值都互不相同，那么最小生成树将只有一个，否则可能会有多个最小生成树
求最小生成树的2个经典算法:
Prim (普里姆算法)Kruskal (克鲁斯克尔算法)
切分定理
切分(Cut)：把图中的节点分为两部分，称为一个切分, 下图有个切分 C = (S, T), S = {A, B, D}, T = {C, E}
横切边 (Crossing Edge)：如果一个边的两个顶点，分别属于切分的两部分，这个边称为横切边 比如上图的边 BC、BE、DE 就是横切边切分定理：给定任意切分，横切边中权值最小的边必然属于最小生成树
Prim算法
Prim算法 – 执行过程
假设 G = (V，E) 是有权的连通图(无向), A 是 G 中最小生成树的边集 算法从 S = { u0 } (u0 ∈ V), A = { } 开始，重复执行下述操作, 直到 S = V 为止 找到切分 C = (S，V – S)的最小横切边 (u0，v0) 并入集合 A, 同时将 v0 并入集合 S
Prim算法 – 实现
@Override
public Set<EdgeInfo<V, E>> prim() {
//随机选取一个顶点
Iterator<Vertex<V, E>> iterator = vertices.values().iterator();
if(!iterator.hasNext()) return null;
Vertex<V, E> vertex = iterator.next();
//存储找到的最小生成树的边
Set<Vertex<V,E>> addedVertices = new HashSet<>();
Set<EdgeInfo<V, E>> edgeInfos = new HashSet<>();
//创建最小堆(批量建堆), 用于获取权值最小的边
MinHeap<Edge<V,E>> minHeap = new MinHeap<>(vertex.outEdges, (Edge<V, E> e1,Edge<V, E> e2)->{
return weightManager.compare(e1.weight,e2.weight);
});
addedVertices.add(vertex);
int verticesSize = vertices.size();
while(!minHeap.isEmpty() && addedVertices.size() < verticesSize){
Edge<V, E> minEdge = minHeap.remove(); //获取最小边 边[from -> to]
if(addedVertices.contains(minEdge.to)) continue; //由于是无向图(底层使用有向图), 所以可能存在边[to -> from], 该边已加入addedVertices集合, 所以跳过
addedVertices.add(minEdge.to); //存储已遍历过的顶点
edgeInfos.add(minEdge.info()); //将最小边添加至set集合中
minHeap.addAll(minEdge.to.outEdges); //将to顶点的所有出边放入堆中, 继续寻找最小边
}
return edgeInfos;
}
Kruskal算法
Kruskal算法 – 执行过程
按照边的权重顺序(从小到大)将边加入生成树中，直到生成树中含有 V – 1 条边为止(V 是顶点数量) 若加入该边会与生成树形成环，则不加入该边, 从第3条边开始，可能会与生成树形成环
Kruskal算法 – 实现
@Override
public Set<EdgeInfo<V, E>> kruskal() {
int edgeSize = edges.size() - 1;
if(edgeSize == -1) return null;
MinHeap<Edge<V,E>> minHeap = new MinHeap<>(edges, (Edge<V, E> e1,Edge<V, E> e2)->{
return weightManager.compare(e1.weight,e2.weight);
});
Set<EdgeInfo<V, E>> edgeInfos = new HashSet<>();
UnionFind<Object> unionFind = new UnionFind<>();
vertices.forEach((V v, Vertex<V, E> vertex) -> {
unionFind.makeSet(vertex); //将每个顶点都单独作为一个集合
});
while(!minHeap.isEmpty() && edgeInfos.size() < edgeSize){
Edge<V, E> edge = minHeap.remove();
/**
* 如果from顶点和 to顶点属于同一个集合(同一个集合内的任意两个顶点是互通的)
* 即如果将[from--to]加入到最小生成树集合中, 那么将出现环, 所以需要则跳过该边
*/
if(unionFind.isSame(edge.from,edge.to)) continue;
edgeInfos.add(edge.info());
unionFind.union(edge.from,edge.to); //将from所属顶点集与to所属顶点集合并
}
return edgeInfos;
}
Prim算法、Kruskal算法中使用的最小堆和并查集
最小堆
package com.lic.graph;
import java.util.Collection;
import java.util.Comparator;
/**
* 二叉堆（最小堆）
* @author LIC
*
* @param <E>
*/
@SuppressWarnings("unchecked")
public class MinHeap<E> {
private int size;
private Comparator<E> comparator;
private int compare(E e1, E e2) {
return comparator != null ? comparator.compare(e1, e2)
: ((Comparable<E>)e1).compareTo(e2);
}
private E[] elements;
private static final int DEFAULT_CAPACITY = 10;
public MinHeap(Collection<E> elements, Comparator<E> comparator) {
this.comparator = comparator;
size = elements == null ? 0 : elements.size();
if (size == 0) {
this.elements = (E[]) new Object[DEFAULT_CAPACITY];
} else {
int capacity = Math.max(size, DEFAULT_CAPACITY);
this.elements = (E[]) new Object[capacity];
int i = 0;
for (E element : elements) {
this.elements[i++] = element;
}
heapify();
}
}
public MinHeap(E[] elements, Comparator<E> comparator) {
this.comparator = comparator;
if (elements == null || elements.length == 0) {
this.elements = (E[]) new Object[DEFAULT_CAPACITY];
} else {
size = elements.length;
int capacity = Math.max(elements.length, DEFAULT_CAPACITY);
this.elements = (E[]) new Object[capacity];
for (int i = 0; i < elements.length; i++) {
this.elements[i] = elements[i];
}
heapify();
}
}
public MinHeap(Collection<E> elements) {
this(elements, null);
}
public MinHeap(E[] elements) {
this(elements, null);
}
public MinHeap(Comparator<E> comparator) {
this.comparator = comparator;
this.elements = (E[]) new Object[DEFAULT_CAPACITY];
}
public MinHeap() {
this.elements = (E[]) new Object[DEFAULT_CAPACITY];
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public void addAll(Collection<E> elements) {
if (elements == null) return;
for (E element : elements) {
add(element);
}
}
public void addAll(E[] elements) {
if (elements == null) return;
for (E element : elements) {
add(element);
}
}
public void clear() {
for (int i = 0; i < size; i++) {
elements[i] = null;
}
size = 0;
}
public void add(E element) {
elementNotNullCheck(element);
ensureCapacity(size + 1);
elements[size++] = element;
siftUp(size - 1);
}
public E get() {
emptyCheck();
return elements[0];
}
public E remove() {
emptyCheck();
int lastIndex = --size;
E root = elements[0];
elements[0] = elements[lastIndex];
elements[lastIndex] = null;
siftDown(0);
return root;
}
public E replace(E element) {
elementNotNullCheck(element);
E root = null;
if (size == 0) {
elements[0] = element;
size++;
} else {
root = elements[0];
elements[0] = element;
siftDown(0);
}
return root;
}
/**
* 批量建堆
*/
protected void heapify() {
// 自下而上的下滤
for (int i = (size >> 1) - 1; i >= 0; i--) {
siftDown(i);
}
}
/**
* 让index位置的元素下滤
* @param index
*/
private void siftDown(int index) {
E element = elements[index];
int half = size >> 1;
// 第一个叶子节点的索引 == 非叶子节点的数量
// index < 第一个叶子节点的索引
// 必须保证index位置是非叶子节点
while (index < half) {
// index的节点有2种情况
// 1.只有左子节点
// 2.同时有左右子节点
// 默认为左子节点跟它进行比较
int childIndex = (index << 1) + 1;
E child = elements[childIndex];
// 右子节点
int rightIndex = childIndex + 1;
// 选出左右子节点最小的那个
if (rightIndex < size && compare(elements[rightIndex], child) < 0) {
child = elements[childIndex = rightIndex];
}
if (compare(element, child) <= 0) break;
// 将子节点存放到index位置
elements[index] = child;
// 重新设置index
index = childIndex;
}
elements[index] = element;
}
/**
* 让index位置的元素上滤
* @param index
*/
private void siftUp(int index) {
E element = elements[index];
while (index > 0) {
int parentIndex = (index - 1) >> 1;
E parent = elements[parentIndex];
if (compare(element, parent) >= 0) break;
// 将父元素存储在index位置
elements[index] = parent;
// 重新赋值index
index = parentIndex;
}
elements[index] = element;
}
private void ensureCapacity(int capacity) {
int oldCapacity = elements.length;
if (oldCapacity >= capacity) return;
// 新容量为旧容量的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
E[] newElements = (E[]) new Object[newCapacity];
for (int i = 0; i < size; i++) {
newElements[i] = elements[i];
}
elements = newElements;
}
private void emptyCheck() {
if (size == 0) {
throw new IndexOutOfBoundsException("Heap is empty");
}
}
private void elementNotNullCheck(E element) {
if (element == null) {
throw new IllegalArgumentException("element must not be null");
}
}
}
并查集
package com.lic.graph;
import java.util.HashMap;
import java.util.Map;
import java.util.Objects;
public class UnionFind<V> {
private Map<V, Node<V>> nodes = new HashMap<>();
public void makeSet(V v) {
if (nodes.containsKey(v)) return;
nodes.put(v, new Node<>(v));
}
/**
* 找出v的根节点
*/
private Node<V> findNode(V v) {
Node<V> node = nodes.get(v);
if (node == null) return null;
while (!Objects.equals(node.value, node.parent.value)) {
node.parent = node.parent.parent;
node = node.parent;
}
return node;
}
public V find(V v) {
Node<V> node = findNode(v);
return node == null ? null : node.value;
}
public void union(V v1, V v2) {
Node<V> p1 = findNode(v1);
Node<V> p2 = findNode(v2);
if (p1 == null || p2 == null) return;
if (Objects.equals(p1.value, p2.value)) return;
if (p1.rank < p2.rank) {
p1.parent = p2;
} else if (p1.rank > p2.rank) {
p2.parent = p1;
} else {
p1.parent = p2;
p2.rank += 1;
}
}
public boolean isSame(V v1, V v2) {
return Objects.equals(find(v1), find(v2));
}
private static class Node<V> {
V value;
Node<V> parent = this;
int rank = 1;
Node(V value) {
this.value = value;
}
}
}
