常用的图算法：最小生成树（MST）
一、图的生成树和最小生成树
生成树(SpanningTree)：如果一个图的子图是一个包含图所有节点的树，那这个子图就称为生成树。图的生成树不惟一。从不同的顶点出发进行遍历，可以得到不同的生成树。专业的说法：在一个无向连通图中，如果存在一个连通子图包含原图中所有的结点和部分边，且这个子图不存在回路，那么我们称这个子图为原图的一棵生成树。
最小生成树：在带权图中，所有的生成树中边权和最小的那棵（或几棵）被称为最小生成树。
二、应用
1.问题（最小连通网问题）
要在n个城市之间铺设光缆，主要目标是要使这 n 个城市的任意两个之间都可以通信，但铺设光缆的费用很高，且各个城市之间铺设光缆的费用不同，因此另一个目标是要使铺设光缆的总费用最低。这就需要找到带权的最小生成树。
2.解决方案
如何在图中选择n-1条边使得n个顶点间两两可达，且这n-1条边的权值之和最小？
必须使用且仅使用该网络中的n-1条边来联结网络中的n个顶点；
不能使用产生回路的边；
各边上的权值的总和达到最小。
三、Prim（普里姆）算法-（适合稠密图）
Prime算法是一种贪心算法，它最初将无向连通图G中所有顶点V分成两个顶点集合VA和VB。在计算过程中VA中的点为已经选好连接入生成树的点，否则属于VB。最开始的时候VA只包含任意选取的图G中的一个点u，其余的点属于VB，每次添加一个VB中的点到VA，该点是集合VB到集合VA中距离最小的一个点。直到V个顶点全部属于VA，算法结束。显然出发点不同，最小生成树的形态就不同，但边权和的最小值是唯一的。
从图 N = { V, E }中选择某一顶点 u0 进行标记，之后选择与它关联的具有最小权值的边(u0, v)，并将顶点 v 进行标记
反复在一个顶点被标记，而另一个顶点未被标记的各条边中选择权值最小的边(u, v),并将未标记的顶点进行标记
如此继续下去，直到图中的所有顶点都被标记为止
有两个嵌套循环，所以时间复杂度为 O(n2)O(n2)。
是以某顶点为起点，逐步找各顶点上最小权值的边来构建最小生成树。
1.手工寻找最小连通网：
2.算法步骤
选定图中的任意一个顶点v0，从v0开始生成最小生成树。
（1）初始化dist[v0]=0，其他点的距离值dist[i]=∞。其中dist[i]表示集合VB中的点到VA中的点的距离值。
（2）经过N次如下步骤操作，最后得到一棵含N个顶点，N-1条边的最小生成树：
选择一个未标记的点k，并且dist[k]的值是最小的
标记点k进入集合VA
以k为中间点，修改未标记点j，即VB中的点到VA的距离值
（3）得到最小生成树T。
四、克鲁斯卡尔（Kruskal）算法（适合稀疏图）
用并查集优化后时间复杂度：O(mlogm+mα(n))，α(n)是一次并查集的复杂度。
1.算法思想
Kruskal算法也是一种贪心算法，它是将边按权值排序，每次从剩下的边集中选择权值最小且两个端点不在同一集合的边加入生成树中，反复操作，直到加入了n-1条边。
2.算法步骤
将G中的边按权值从小到大快排。
按照权值从小到大依次选边。若当前选取的边加入后使生成树T形成环，则舍弃当前边，否则标记当前边并计数。
重复上一步操作，直到生成树T中包含n-1条边，否则当遍历完所有边后，选取不到n-1条边，表示最小生成树不存在。
算法的关键在于如何判定新加入的边会不会使图G'产生环，在这里用并查集，如果新加入的边的两个端点在并查集的同一集合中，说明存在环，需要舍弃这条边，否则保留当前边，并合涉及的两个集合。
简单说就是首先构造一个只含n个顶点的森林，然后依权值从小到大从连通网中选择边加入到森林中，并使森林中不产生回路，直至森林变成一棵树为止。
五、代码实现
1public class MatrixUDG {
2 private int mEdgNum;//边的数量
3 private char[] mVexs;//顶点集合
4 private int[][] mMatrix;//邻接矩阵
5 private static final int INF = Integer.MAX_VALUE;//最大值
6
7 /**
8 * 创建图
9 * @param vexs --顶点数组
10 * @param matrix --矩阵数据
11 */
12 public MatrixUDG(char[] vexs, int[][] matrix){
13 this.mVexs = vexs;//初始化顶点
14 this.mMatrix = matrix;//初始化矩阵
15
16 //统计边:边有3种类型:0(自己到自己),数字(相邻边),INF(不是相邻边)
17 int vlen = vexs.length;
18 for(int i = 0; i < vlen; i++){
19 for(int j = i + 1; j < vlen; j++){
20 if(mMatrix[i][j] != INF){
21 mEdgNum++;
22 }
23 }
24 }
25 }
26
27 /**
28 * 返回在顶点的位置
29 * @param ch
30 * @return
31 */
32 private int getPosition(char ch){
33 for(int i = 0; i < mVexs.length; i++){
34 if(ch == mVexs[i]){
35 return i;
36 }
37 }
38 return -1;
39 }
40
41 /**
42 * 打印邻接矩阵
43 */
44 private void print(){
45 System.out.println("邻接矩阵:");
46 for (int[] matrix : mMatrix) {
47 for (int ch : matrix) {
48 System.out.print(ch + " ");
49 }
50 System.out.println();
51 }
52 }
53
54 /**
55 * prime最小生成树算法
56 */
57 public void prime(int start){
58 int num = mVexs.length;//顶点个数
59 int[] weights = new int[num];//顶点间边的权重
60 char[] prims = new char[num];//prime最小生成树的结果
61 int index = 0;//prime数组的当前索引
62
63 //第一个数是start顶点
64 prims[index ++] = mVexs[start];
65
66 //初始化权重
67 for(int i = 0; i < num; i++){
68 weights[i] = mMatrix[start][i];
69 }
70 weights[start] = 0;//自己到自己的权重为0
71
72
73 for(int i = 0; i < num; i++){
74 if(i == start){//由于从start开始不需要进行处理
75 continue;
76 }
77
78 //从剩余的边中找到最小权重
79 int min = INF;//最小权重
80 int minIndex = 0;//最小权重所在的索引
81 for(int j = 0; j < num; j++){
82 if(weights[j] != 0 && weights[j] < min){//0表示已经加入最小权重
83 min = weights[j];
84 minIndex = j;
85 }
86 }
87
88 //将最小权重加入到数组中,并设置为0
89 prims[index++] = mVexs[minIndex];
90 weights[minIndex] = 0;
91
92 //更新其他权重的值:取双方权重值最小的
93 for(int j = 0; j < num; j++){
94 if(weights[j] != 0 && mMatrix[minIndex][j] < weights[j]){
95 weights[j] = mMatrix[minIndex][j];
96 }
97 }
98 }
99
100 //计算最小生成树的权重
101 int sum = 0;
102 for(int i = 1; i < index; i++){
103 int min = INF;
104
105 int n = getPosition(prims[i]);
106 //求当前节点到上面其他节点的最小值
107 for(int j = 0; j < i; j++){
108 int m = getPosition(prims[j]);
109 if(mMatrix[m][n] < min){
110 min = mMatrix[m][n];
111 }
112 }
113
114 sum += min;
115 }
116
117 //打印最小生成树
118 System.out.printf("PRIME(%c)=%d:", mVexs[start], sum);
119 for(int i = 0; i < index; i ++){
120 System.out.printf("%c ", prims[i]);
121 }
122 System.out.printf("\n");
123 }
124
125 /**
126 * kruskal生成最小生成树
127 */
128 public void kruskal(){
129 int index = 0;//结果数组的当前索引
130 EData[] results = new EData[mEdgNum];//结果数组
131 int[] vends = new int[mEdgNum];//保存的是某个顶点在该最小生成树的终点
132
133
134 //获取图中所有的边
135 EData[] edges = getEdges();
136
137 //将边按权重从小到大排序
138 sortEdges(edges);
139
140 for(int i = 0; i < mEdgNum; i++){
141 int p1 = getPosition(edges[i].start);
142 int p2 = getPosition(edges[i].end);
143
144 int m = getEnd(vends, p1);
145 int n = getEnd(vends, p2);
146 if(m != n){//表示没有形成闭环
147 vends[m] = n;
148 results[index++] = edges[i];
149 }
150 }
151
152 //统计并打印最小生成树的信息
153 int length = 0;
154 for(int i = 0; i < index; i++){
155 length += results[i].weight;
156 }
157 System.out.printf("kruskal=%d", length);
158
159 for(int i = 0; i < index; i++){
160 System.out.printf("(%c,%c) ", results[i].start,results[i].end);
161 }
162 System.out.printf("\n");
163 }
164
165 /**
166 * 获取图中的边
167 */
168 private EData[] getEdges(){
169 int index = 0;
170 EData[] edges = new EData[mEdgNum];
171 for(int i = 0; i < mVexs.length; i++){
172 for(int j = i + 1; j < mVexs.length; j++){
173 if(mMatrix[i][j] != INF){
174 edges[index++] = new EData(mVexs[i],mVexs[j],mMatrix[i][j]);
175 }
176 }
177 }
178 return edges;
179 }
180
181 /**
182 * 根据权重大小排序(从小到大)
183 * @param edges
184 */
185 private void sortEdges(EData[] edges){
186 EData tmp;
187 for(int i = 0; i < edges.length; i++){
188 for(int j = (i + 1); j < edges.length; j++){
189 if(edges[i].weight > edges[j].weight){//若大于则交换位置
190 tmp = edges[i];
191 edges[i] = edges[j];
192 edges[j] = tmp;
193 }
194 }
195 }
196 }
197
198 /**
199 * 取终点
200 */
201 private int getEnd(int[] vends, int i){
202 //若C->D,D->F则取F的值
203 while(vends[i] != 0){
204 i = vends[i];
205 }
206 return i;
207 }
208
209 //边的数据结构
210 private static class EData{
211 char start;//边的起点
212 char end;//边的终点
213 int weight;//边的权重
214
215 public EData(char start, char end, int weight) {
216 this.start = start;
217 this.end = end;
218 this.weight = weight;
219 }
220 }
221
222 public static void main(String[] args) {
223 char[] vexs = {'A','B','C','D','E','F','G'};
224 int[][] matrix = {
225 //A //B //C //D //E //F //G
226 {0, 12, INF, INF, INF, 16, 14}, //A
227 {12, 0, 10, INF, INF, 7, INF}, //B
228 {INF, 10, 0, 3, 5, 6, INF}, //C
229 {INF, INF, 3, 0, 4, INF, INF}, //D
230 {INF, INF, 5, 4, 0, 2, 8}, //E
231 {16, 7, 6, INF, 2, 0, 9}, //F
232 {14, INF, INF, INF, 8, 9, 0} //G
233 };
234
235 MatrixUDG matrixUDG = new MatrixUDG(vexs, matrix);
236 matrixUDG.prime(0);//PRIME(A)=36:A B F E D C G
237 matrixUDG.kruskal();//kruskal=36(E,F) (C,D) (D,E) (B,F) (E,G) (A,B)
238 }
239}六、总结
Prim算法是针对顶点展开的，适合于边的数量较多的情况
Kruskal算法是针对边展开的，适合于边的数量较少的情况
参考资料：
https://blog.csdn.net/wonder233/article/details/79098728
https://blog.csdn.net/qq_39826163/article/details/81660819
https://www.jianshu.com/p/a5f0f46be8e2