数据结构之图拓扑排序和最小生成树_生成树拓扑图

1. 拓扑排序（Topological Sort）

将AOV网中所有活动排成一个序列，使每个活动的前驱活动都排在该活动前面。

1.1 AOV网（Activity On Vertex Network）

将一项大的工程分为若干个小的子工程，子工程中可以存在顺序，部分子工程需要等待其它子工程完成后才可以执行。

AOV网必须是一个有向完全图：明显可以看出边的终点的顶点依赖于起点的顶点。

**前驱活动：**有向边起点的活动称为终点的前驱活动；
**后驱活动：**有向边终点的活动称为起点的前驱活动；

1.2 思路

以下图为示例：

1. 新建一个list集合作为存储顶点的返回值；新建一个queue将入度为0的顶点加入到队列中等待操作；新建一个map记录每个顶点的入度。

2. 记录所有入度非0的顶点的入度：
   

3. 将入度为0的顶点加入到队列中：
   
   出队，加入到list中，将当前出队元素的所有后驱活动的入度值减一。
   
   
   

4. 循环执行上方3操作。

1.3 实现

    @Override
    public List<V> topologicalSort() {
        List<V> list = new ArrayList<>();
        Queue<Vertex<V, E>> queue = new LinkedList<>();
        HashMap<Vertex<V, E>, Integer> map = new HashMap<>();

        // 将所有的入度为0的顶点加入到队列中
        vertices.forEach((V v, Vertex<V,E> vertex) ->{
            int size = vertex.inEdges.size();
            if (size == 0){
                queue.offer(vertex);
            }else {
                map.put(vertex,size);
            }
        });

        while (!queue.isEmpty()){
            Vertex<V, E> vertex = queue.poll();
            list.add(vertex.v);
            for (Edge<V, E> edge : vertex.outEdges) {
                int size = map.get(edge.to) - 1;
                if (size == 0){ // 入度为 0 加入到队列中
                    queue.offer(edge.to);
                }else { // 不为 0 入度减一
                    map.put(edge.to,size);
                }
            }
        }
        return list;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

2. 生成树（Spanning Tree）

生成树，也称支撑树。

连通图的极小连通子图：包含图中全部n个顶点，恰好有n - 1条边。

上方图的极小连通子图

2.1 最小生成树（Minimum Spanning Tree）

所有生成树中，总权值最小的那颗。如果每条边的权值都不相同，就只有一个最小生成树，如果相同则由不同的生成树。

最小生成树

2.2 完善代码

2.2.1 修改接口

• 把接口修改为一个抽象类：保证有一个针对权重的接口处理。

     protected WeightManager<E> weightManager;

    public Graph() {}

    public Graph(WeightManager<E> weightManager) {
        this.weightManager = weightManager;
    }

    /**
     * 权值内部接口设计
     * @param <E>
     */
    public interface WeightManager<E> {
        /**
         * 比较值的大小
         * @param w1
         * @param w2
         * @return
         */
        int compare(E w1, E w2);

        /**
         * 两个值相加的结果
         * @param w1
         * @param w2
         * @return
         */
        E add(E w1, E w2);
        E zero();
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

• 新建一个内部的边类：不暴露内部真正实现的边对象。

    /**
     * 返回边的节点设计
     * @param <V>
     * @param <E>
     */
    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;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

-全部代码：

/**
 * @Description 图接口
 * @date 2022/5/10 20:31
 */
public abstract class Graph<V,E>{

    protected WeightManager<E> weightManager;

    public Graph() {}

    public Graph(WeightManager<E> weightManager) {
        this.weightManager = weightManager;
    }

    /**
     * 获取边的数量
     * @return 边数量
     */
    public abstract int edgeSize();

    /**
     * 获取顶点数量
     * @return 顶点数量
     */
    public abstract int verticesSize();

    /**
     * 添加一个顶点
     * @param v 顶点
     */
    public abstract void addVertex(V v);

    /**
     * 两个顶点之间添加一个边
     * @param from 起点
     * @param to 终点
     */
    public abstract void addEdge(V from, V to);

    /**
     * 两个顶点之间添加一个携带权值的边
     * @param from 起点
     * @param to 终点
     * @param weight 权值
     */
    public abstract void addEdge(V from, V to, E weight);

    /**
     * 删除一个顶点
     * @param v 顶点
     */
    public abstract void removeVertex(V v);

    /**
     * 删除一条边
     * @param from 起点
     * @param to 终点
     */
    public abstract void removeEdge(V from, V to);

    /**
     * 广度优先搜索
     * @param v
     */
    public abstract void bfs(V v, VertexVisitor<V> visitor);

    /**
     * 深度优先搜索
     * @param v
     */
    public abstract void dfs(V v, VertexVisitor<V> visitor);

    /**
     * 使用栈实现深度优先搜索
     * @param v
     */
    public abstract void difOfStack(V v, VertexVisitor<V> visitor);

    /**
     * dfs 和 bfs 遍历是外部获取值
     * @param <V>
     */
    public interface VertexVisitor<V> {
        boolean visit(V v);
    }

    /**
     * 拓扑排序
     * @return
     */
    public abstract List<V> topologicalSort();

    /**
     * 最小生成树
     * @return
     */
    public abstract Set<EdgeInfo<V,E>> mst();

    /**
     * 权值内部接口设计
     * @param <E>
     */
    public interface WeightManager<E> {
        /**
         * 比较值的大小
         * @param w1
         * @param w2
         * @return
         */
        int compare(E w1, E w2);

        /**
         * 两个值相加的结果
         * @param w1
         * @param w2
         * @return
         */
        E add(E w1, E w2);
        E zero();
    }

    /**
     * 返回边的节点设计
     * @param <V>
     * @param <E>
     */
    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;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164

2.2.2 修改内部Edge类

因为外部暴露的是抽象类中封装的EdgeInfo类，为了方便对象之间类型转换，新建一个方法将Edge对象变为EdgeInfo对象：

  EdgeInfo<V, E> info(){
            return new EdgeInfo<V, E>(from.v, to.v, weight);
        }
1
2
3

2.2.3 新增小顶堆

小顶堆：因为需要获取多个值中最小的一个，非常适合使用小顶堆，但是JDK的优先级队列方法有限，这里实现了一个小顶堆代码。

/**
 * @Description 小顶堆
 * @date 2022/5/10 20:38
 */
@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");
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226

2.2.4 新增并查集

并查集：判断顶点与顶点之间是否构成环，判断如果两个顶点已经位于同一个集合中，在执行并操作就会成环，因此当前边不能位于最小生成树中。

/**
 * @Description 小顶堆
 * @date 2022/5/13 20:48
 */
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;
		}
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

2.3 Prim 实现最小生成树

2.3.1 切分定理

给定任意切分，横切边中权值最小的边必然属于最小生成树。

• 切分：把图中节点分为两部分，称为一个切分。
  例如：这里有两个切分：{C、E}；{A、B、D}。

• 横切边：如果一个边的两个顶点，分别属于切边的两部分，则这个边称为横切边。
  例如：BC、BE、DE。

2.3.2 执行过程

• 定义集合信息：V：图中全部顶点集合；E：图中全部边集合； S={beignVertex}：存储切分完毕的顶点信息，开始存储起点；A={}：存储最小生成树中的边信息。

• 执行：这里以A作为起点，进行切分，将权值小的边{A,B}加入到集合A中；将B加入到集合S中。

• 切分选择：因为这里已经将切分完毕的顶点加入到集合S中，剩余的顶点就是集合V - S；所以这里切分下图中位置：
  
• 重复执行：直到S = V时完成。

2.3.3 代码实现

• 声明比较器：

    // 比较器
    private Comparator<Edge<V, E>> edgeComparator = (Edge<V, E> e1, Edge<V, E> e2) -> {
        return weightManager.compare(e1.weight, e2.weight);
    };
1
2
3
4

prim()

    @Override
    public Set<EdgeInfo<V, E>> mst() {
        return prim();
    }

    /**
     * prim最小生成树
     * @return
     */
    private Set<EdgeInfo<V, E>> prim(){
        // 获取顶点迭代器 如果迭代器为空则返回null
        Iterator<Vertex<V, E>> iterator = vertices.values().iterator();
        if (!iterator.hasNext()) return null;

        // 返回边集
        Set<EdgeInfo<V, E>> edgeInfos = new HashSet<>();

        // 已经加入到最小生成树中的顶点集
        Set<Vertex<V,E>> added = new HashSet<>();

        Vertex<V, E> vertex = iterator.next();
        added.add(vertex);

        // 初始化构建小顶堆，传入第一个顶点的出度边集合 和 比较器
        MinHeap<Edge<V, E>> heap = new MinHeap<>(vertex.outEdges,edgeComparator);

        int size = vertices.size();
        // 当堆中有元素 并且 已经处理的顶点数量小于总数量时才需要进行处理
        while (!heap.isEmpty() && edgeInfos.size() < size){
             // 权值最小的边，一定是最小生成树的一部分
            Edge<V, E> edge = heap.remove();

            // 如果当前点已经被加入到该集合中 表示已经对其处理完毕 不需要再加入到堆中进行处理
            if (added.contains(edge.to)) continue;

            // 把组成最小生成树的边放入到返回的集合中
            edgeInfos.add(edge.info());
            added.add(edge.to);

            // 将该边终点的所有出度边加入到堆中
            heap.addAll(edge.to.outEdges);
        }

        return edgeInfos;
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

2.4 Kruskal 实现最小生成树

按照权重从小到大的顺序将边加入到生成树中，但从第三条开始，可能会于生成树形成环，此时就不加入该边。直到生成树种的边数量为顶点数量减一为止。

• 执行流程

1. 最小权值边加入
2. 除已经加入的最小的加入
   
3. 直到已将加入的边是节点的数量减一
   

• 代码实现

    /**
     * kruskal 最小生成树
     * @return
     */
    private Set<EdgeInfo<V, E>> kruskal(){
        int size = vertices.size() - 1;
        if (size <= 1) return null;
        // 最小生成树 边 集合
        Set<EdgeInfo<V, E>> edgeInfos = new HashSet<>();
        // 将所有的边都加入到小顶堆中
        MinHeap<Edge<V, E>> heap = new MinHeap<>(edges,edgeComparator);
        // 初始化并查集，将每个顶点都作为一个集合
        UnionFind<Vertex<V, E>> unionFind = new UnionFind<>();
        vertices.forEach((V v , Vertex<V, E> vertex) ->{
            unionFind.makeSet(vertex);
        });
        while (!heap.isEmpty() && edgeInfos.size() < size){
            // 获得权值最小的边
            Edge<V, E> edge = heap.remove();
            // 判断是否成环 ，成环就抛弃 当前边
            if (unionFind.isSame(edge.from, edge.to)) continue;
            // 将最小的边加入到最小生成树中
            edgeInfos.add(edge.info());
            // 将当前边的两个顶点加入到并查集中
            unionFind.union(edge.from, edge.to);
        }
        return edgeInfos;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28