AOV 网
大的工程分成小的子工程, 子工程之间有一定的先后顺序, 子工程完成后才能开始后续的工程
以顶点表示活动, 有向边表示活动之间的先后顺序, 这样的图简称AOV 网
标准的AOV 网必须是一个有向无环图
AOV网
拓扑排序(Topological Sort)
将AOV 网中所有活动排成一个序列, 使得每个活动的前驱活动都排在该活动的前面
前驱活动, 有向边起点的活动称为终点的前驱活动, 只有该活动的前驱全部完成, 这个活动才能进行
后继活动, 有向边终点的活动称为起点的后继活动
排序思路
卡恩算法
假设L 是存放拓扑排序结果的列表
- 把所有入度为0 的顶点放入L 中, 然后把这些顶点从图中去掉
- 重复1 中的操作, 直到找不到入度为0 的顶点
如果此时L 的元素个数和顶点数量相同, 排序完成, L 中的元素数量少于顶点总数, 说明图中存在环, 无法完成拓扑排序
拓扑排序
@Override
public List<V> topologicalSort() {
List<V> list = new ArrayList<>();
Queue<Vertex<V, E>> queue = new LinkedList<>();
// 使用map 记录图中元素的入度数量, 有变化时更新数量直到为0
Map<Vertex<V, E>,Integer> ins = new HashMap<>();
// 初始化, 将度为0 的节点都放入到队列中
vertices.forEach((V v, Vertex<V, E> vertex) -> {
int in = vertex.inEdges.size();
if (in == 0) {
queue.offer(vertex);
} else {
ins.put(vertex, in);
}
});
while (!queue.isEmpty()) {
Vertex<V, E> vertex = queue.poll();
list.add(vertex.value);
for (Edge<V, E> edge : vertex.outEdges) {
int toIn = ins.get(edge.to) - 1;
if (toIn == 0) {
queue.offer(edge.to);
} else {
ins.put(edge.to, toIn);
}
}
}
return list;
}
最小生成树(Spanning Tree)
生成树, 也称为支撑树
连通图的极小连通子图, 它含有图中全部的n 个顶点, 恰好只有n - 1 条边
生成树
最小生成树
简称MST
适用于有权的无向连通图, 是所有生成树中, 总权值最小的那棵树, 也称为最小重生成树, 最小支撑树
最小生成树
作用:
n 个城市之间铺设光缆, 费用最低
两个经典算法
- Prim, 普里姆算法
- Kruskal, 克鲁斯克尔算法
Prim
切分Cut, 把图中的节点分为两部分, 称为一个切分
C = (S, T), S = {A, B, D}, T = {C, E}
切分
横切边(Crossing Edge), 如果一个边的两个顶点, 分别属于切分的两部分, 这个边称为横切边
切分定理, 给定任意切分, 横切边中权值最小的边必然属于最小生成树
假设G = (V, E) 是有权的无向连通图, A 是G 中最小生成树的边集
算法从S = {u0}(u0 ∈ V), A = {} 开始, 重复执行以下操作, 直到S = V
找到切分C = (S, V - S) 的最小横切边(u0, v0) 并入集合A, 同时将v0 并入集合S
prim执行过程1
prim执行过程2
prim执行结果
protected WeightManager<E> weightManager;
public interface WeightManager<E> {
int compare(E e1, E e2);
E add(E e1, E e2);
E zero();
}
public static class EdgeInfo<V, E> {
private V from;
private V to;
private E weight;
public EdgeInfo(V from, V to, E weight) {
this.from = from;
this.to = to;
this.weight = weight;
}
public V getFrom() {
return from;
}
public void setFrom(V from) {
this.from = from;
}
public V getTo() {
return to;
}
public void setTo(V to) {
this.to = to;
}
public E getWeight() {
return weight;
}
public void setWeight(E weight) {
this.weight = weight;
}
@Override
public String toString() {
return "EdgeInfo [from=" + from + ", to=" + to + ", weight=" + weight + "]";
}
}
private Set<EdgeInfo<V, E>> prim() {
// 取得迭代器
Iterator<Vertex<V, E>> it = vertices.values().iterator();
// 为空直接返回null
if (!it.hasNext()) return null;
// 取得第一个
Vertex<V, E> vertex = it.next();
// 存放最小生成树的边信息
Set<EdgeInfo<V, E>> edgeInfos = new HashSet<>();
// 已经访问过的顶点, 不需要重复添加
Set<Vertex<V, E>> addedVertices = new HashSet<>();
addedVertices.add(vertex);
// 使用最小堆, 获取最小边
MinHeap<Edge<V, E>> heap = new MinHeap<>(vertex.outEdges, edgeComparator);
int verticesSize = vertices.size();
while (!heap.isEmpty() && addedVertices.size() < verticesSize) {
Edge<V, E> edge = heap.remove();
if (addedVertices.contains(edge.to)) continue;
edgeInfos.add(edge.info());
addedVertices.add(edge.to);
heap.addAll(edge.to.outEdges);
}
return edgeInfos;
}
Kruskal
按照边的权重顺序, 从小到大将边加入生成树中, 直到生成树中含有V - 1条边为止
若加入该边会与生成树形成环, 则不加入, 从第三条边开始, 可能形成环
kruskal执行过程1
kruskal执行过程2
private Set<EdgeInfo<V, E>> kruskal() {
int edgeSize = vertices.size() - 1;
if (edgeSize == -1) return null;
Set<EdgeInfo<V, E>> edgeInfos = new HashSet<>();
MinHeap<Edge<V, E>> heap = new MinHeap<>(edges, edgeComparator);
// 并查集, 检查是否形成环
UnionFind<Vertex<V, E>> uf = new UnionFind<>();
// 并查集初始化, 每个顶点构成一个集合
vertices.forEach((V v, Vertex<V, E> vertex) -> {
uf.makeSet(vertex);
});
while (!heap.isEmpty() && edgeInfos.size() < edgeSize) {
Edge<V, E> edge = heap.remove();
// 同一个集合,跳过
if (uf.isSame(edge.from, edge.to)) continue;
// 加入到info 中
edgeInfos.add(edge.info());
// 起点终点构成集合
uf.union(edge.from, edge.to);
}
return edgeInfos;
}
网友评论