终于来到图这部分，一起了解下这种“最复杂”的数据结构。

之前提到的数组、树的各节点（元素）之间存在前后关系（左右节点），或者层次关系（父节点，子节点）。而图结构中一个节点可以有多个关联节点，多个节点又可以关联同一个节点。任意两个节点都可能存在关系。

我们这次从一个具体例子来看，最后再给出各个定义(复杂关系导致的基本概念较多）。

假设你是一名网络工程师，负责连三个小区a、b、c之间的网络。三个小区间可搭建的网络长度如下：a到b 1km，a到c 2km，b到c 3km，如图示

问：如何用最短的长度连接三个小区？（无需两两连接，两个小区间可以通过其他小区来连通）

三个小区，每个小区间都可以连接，所以会有三种组合，我们简单计算下就能得出如下结果：

方案一 a-c-b 2+3=5km

方案二 a-b-c 1+3=4km

方案三 c-a-b 2+1=3km

可以看出c-a-b这条线路是最短的，需要花费的线路成本也就最小，因此就选择这条路线。目前看三个小区的连接情况我们能轻松搞定，如果是再多的小区的呢，比如这种

甚至这种呢？

这时还能“简单计算”下吗，显然我们需要把这种问题进行提炼，抽象化成一个计算机问题，让计算机来帮助我们解决这种“复杂”的问题。所以数据结构可以看做是对现实问题的抽象，是一类问题及对应解决方法的提炼。那我们思考下，如何把小区间最短连接长度的问题映射成计算机可处理的模型呢？

先看下这些小区，现实中还可以是大厦、村庄、城市等等，我们把它抽象成“顶点（Vertex）”，当然你也可以叫它节点，只不过为了和树中的节点做个区分。这个顶点的顶并不是我们常说的“最高的，最上面”的意思。在小区连接线路的例子中，可以看作是各个连接的聚合点，类似几何里多条边相交的点。所以每个连接聚合点都可以是顶点，也就没有根节点一说了。

在看下小区间的网络连接，现实中还可以是城市间的交通方式，如航线，铁路，高速等等……我们把这种表示两个点直接存在连接的关系称为“边（Edge）”，当然这个边的条数现实中可能会有多个，我们这里假设只有一条。而且没有方向一说，也就是不存在小区a到b是连通的，但b到a是不连通的情况。所以也可以给边附加上方向限制，这种称为“有向边（Directed Edge）”，无方向的就是“无向边（Undirected Edge）”，对应的图就是“有向图（Directed Graph）”和“无向图（Undirected Graph）”。所以小区例子中涉及的都是无向边，是一个无向图。

最后在看下小区间线路的长度，现实中还可以是城市间的距离、道路的长度、高速时速限制、各种事物间的关联度等等这种用数值来表示的值，我们称为“权重（Weight）”。因此权重是用来丰富边的属性的，不同的边可以有不同的权重。

有了这三个基本概念及一些衍生概念，我们对图的理解就算入门了。我们再把这个最短连接距离的问题总结抽象一下，即求连接各顶点的边的权重之和的最小值，对应官方名称是“最小生成树（Minimum Spanning Tree）”。你可能会奇怪，我们明明是再讲图，怎么又出来树了？

让我们先回到小区连接这个例子上：当我们连通三个小区（顶点）时，理论上只需要两条线路（边）即可。我们用如下图例表示就是这三种

我们再转换下形式，就是这样了

这样看就是树的结构了。所以我们把这种通过最少边就能连通全部顶点的图称为“生成树 （Spanning Tree）”。因此树其实就是图的一个子集，是一种特殊的图。

*假设图的顶点数量为V个，图的边数量为E条，则生成树边树满足：E=V-1

而对于三个小区的这三颗生成树中，我们把连通距离最短（边的权重和最小）的那一颗就称为“最小生成树”。到这里我们就把求小区最短连接距离的问题，转换为求图的最小生成树的问题了。

只有问题的描述还不够，我们还要有相应的存储结构来支持。小区问题中，每个小区都对应了两个小区，我们很自然想到用列表的形式来表达：

[ a:[b,c], b:[a,c], c:[a,b] ]

再把距离加上

[ a:[b:1,c:2], b:[a:1,c:3], c:[a:2,b:3] ]

可以看到每个顶点对应的都是一个list，因此把这种存储结构称为“邻接表（Adjacency List）”，如图示

再换一种思路，由于是两两对应，就可以用二维数组的形式来存储，三个小区就对应了3*3的一个表格（矩阵），我们把这种n*n表格存储结构称为“邻接矩阵（Adjacency Matrix）”，如图示

这两种存储方法各有利弊，第一种方式查找某个顶点下是否和其他顶点连接，需要先找到顶点，再遍历所属的列表才能找到，而数组格式直接根据下标即可定位。例如查询a小区下是否和c连接，则需要定位到a:[b:1,c:2]后，再从[b:1,c:2]中查找c（当然a中的[b:1,c:2]也可以用HashTable来存储，这样就无需遍历了）。而对应数组中只需要[a][c]就能定位。但数组这种难免存在空间浪费，例如ab ba小区间的距离是相同的，但却存储了两次（无向图时）。

存储结构有了，接下来就看具体求解方法（算法）。先说两种基本的思路：

一种是从任意一个顶点x出发，找x的所有边中权重最小的那一个边e0，以及e0对应的顶点a，顶点x和a构成一个顶点集合S，再从顶点集合S对应的所有边中选取一个权重最小的边e1（当然不能包括上次选的e0），同时保证新加入的这个边不能和现有顶点集合形成一个环，然后把e1对应的新的顶点加入集合S，一直重复这个过程，直到连接所有的顶点。

另外一种是，先对图的各边权重进行从小到大的排序，先从最小的一个边开始连接，然后再连接第二小的边，且保证新加入的边不能和已经连接的顶点形成环。这样一直重复，最终连接起所有的顶点。

方法一称为普里姆算法（Prim's algorithm），另外一种称为克鲁斯卡尔算法（Kruskal's algorithm）。

这两种算法中都提到了“新加入的边不能和已有的边构成环”，类似图示这种结构，新加入的b-c边导致a b c顶点边构成了一个回路。这种结构下顶点数就等于边的数量，已不符合生成树的定义，所以各边的权重之和必然也不是最小的。

因此我们需要有一种检测是否形成环的机制。我们这里先介绍一种相对简单的方法：“并查集”（disjoint sets或union-find sets）。核心是只要节点有相同根节点，就属于同一颗树，就会导致环的形成。本质是不同集合的合并与查询，后续会单独介绍，我们先大概了解下。

演示用图的结构如下

两种最小生成树的算法实现如下

  1 import java.util.ArrayList;
  2 import java.util.Arrays;
  3 import java.util.Comparator;
  4 import java.util.List;
  5 
  6 public class MinSpanningTree {
  7     private final int vertexNum;
  8     private final int[][] vertices;
  9     private static final int MAX_WEIGHT = 99;
 10 
 11     public static void main(String[] args) {
 12         int vertexNum = 6;
 13         //用邻接矩阵存储顶点0-6共计6个顶点
 14         MinSpanningTree tree = new MinSpanningTree(vertexNum);
 15         initDemo(tree.vertices);
 16         tree.print();
 17         System.out.println("[prim]");
 18         printMinSpanningTree(tree.prim());
 19         System.out.println("[kruskal]");
 20         printMinSpanningTree(tree.kruskal());
 21     }
 22 
 23     private List<Edge> prim() {
 24         int minEdgeStart = 0;
 25         int minEdgeEnd = 0;
 26         boolean[] visitedVertices = new boolean[vertexNum];
 27         //默认从0顶点处理
 28         visitedVertices[0] = true;
 29         List<Edge> minSpanningTree = new ArrayList<>();
 30         int visitedVerticesNum = 1;
 31         while (visitedVerticesNum != vertexNum) {
 32             int minWeight = MAX_WEIGHT;
 33             for (int vertex = 0; vertex < vertexNum; vertex++) {
 34                 //未在访问过的顶点数组中，直接跳过
 35                 if (!visitedVertices[vertex]) {
 36                     continue;
 37                 }
 38                 for (int i = 0; i < vertexNum; i++) {
 39                     //同一个顶点、访问过的、形成环的都需要跳过（由于是一颗不断增加节点的树，当两个节点在树中都存在时，必然会形成环）
 40                     if (visitedVertices[vertex] && visitedVertices[i]) {
 41                         continue;
 42                     }
 43                     //取权重最小的边
 44                     if (vertices[vertex][i] < minWeight) {
 45                         minEdgeStart = vertex;
 46                         minEdgeEnd = i;
 47                         minWeight = vertices[vertex][i];
 48                     }
 49                 }
 50             }
 51             visitedVertices[minEdgeStart] = true;
 52             visitedVertices[minEdgeEnd] = true;
 53             visitedVerticesNum++;
 54             System.out.printf("minEdgeStart %d minEdgeEnd %d visitedVertices %s\n", minEdgeStart, minEdgeEnd, Arrays.toString(visitedVertices));
 55             minSpanningTree.add(new Edge(minEdgeStart, minEdgeEnd, minWeight));
 56         }
 57         return minSpanningTree;
 58     }
 59 
 60     private List<Edge> kruskal() {
 61         List<Edge> edges = sortByWeight();
 62         int[] rootNodes = new int[vertexNum];
 63         Arrays.fill(rootNodes, MAX_WEIGHT);
 64         List<Edge> minSpanningTree = new ArrayList<>();
 65         int edgeNum = 0;
 66         for (Edge edge : edges) {
 67             System.out.print(edge);
 68             int root1 = findRoot(rootNodes, edge.start);
 69             int root2 = findRoot(rootNodes, edge.end);
 70             if (root1 == root2) {
 71                 System.out.printf(" skip edge %d-%d root %d\n", edge.start, edge.end, root1);
 72                 continue;
 73             }
 74             minSpanningTree.add(edge);
 75             //合并树
 76             rootNodes[root1] = root2;
 77             edgeNum++;
 78             System.out.println(root1 + "->" + root2 + " rootNodes" + Arrays.toString(rootNodes));
 79             if (edgeNum == vertexNum - 1) {
 80                 break;
 81             }
 82         }
 83         System.out.println("rootNodes" + Arrays.toString(rootNodes) + " edgeNum " + edgeNum);
 84         return minSpanningTree;
 85     }
 86 
 87     public MinSpanningTree(int vertexNum) {
 88         this.vertexNum = vertexNum;
 89         this.vertices = new int[vertexNum][vertexNum];
 90         for (int i = 0; i < vertexNum; i++) {
 91             for (int j = 0; j < vertexNum; j++) {
 92                 this.vertices[i][j] = MAX_WEIGHT;
 93             }
 94         }
 95     }
 96 
 97     public static void printMinSpanningTree(List<Edge> minSpanningTree) {
 98         int totalWeight = 0;
 99         for (Edge edge : minSpanningTree) {
100             totalWeight += edge.getWeight();
101             System.out.println(edge.getStart() + "-" + edge.getEnd() + " " + edge.getWeight());
102         }
103         System.out.println("totalWeight " + totalWeight);
104     }
105 
106     public static void initDemo(int[][] vertices) {
107         //初始化边权重
108         vertices[0][4] = 2;
109         vertices[0][5] = 1;
110         vertices[0][1] = 5;
111 
112         vertices[1][0] = 5;
113         vertices[1][5] = 5;
114         vertices[1][2] = 3;
115 
116         vertices[2][1] = 3;
117         vertices[2][5] = 4;
118         vertices[2][3] = 7;
119 
120         vertices[3][2] = 7;
121         vertices[3][5] = 6;
122         vertices[3][4] = 4;
123 
124         vertices[4][3] = 4;
125         vertices[4][5] = 3;
126         vertices[4][0] = 2;
127 
128         vertices[5][0] = 1;
129         vertices[5][1] = 5;
130         vertices[5][2] = 4;
131         vertices[5][3] = 6;
132         vertices[5][4] = 3;
133     }
134 
135     private void print() {
136         System.out.print("+  ");
137         for (int i = 0; i < vertexNum; i++) {
138             System.out.printf("%d  ", i);
139         }
140         System.out.println();
141         int index = 0;
142         for (int[] ints : vertices) {
143             System.out.printf("%d  ", index++);
144             for (int j = 0; j < vertices.length; j++) {
145                 if (ints[j] == MAX_WEIGHT) {
146                     System.out.print("-  ");
147                 } else {
148                     System.out.printf("%d  ", ints[j]);
149                 }
150             }
151             System.out.println();
152         }
153     }
154 
155     private static int findRoot(int[] numbers, int num) {
156         while (true) {
157             if (numbers[num] == MAX_WEIGHT) {
158                 return num;
159             }
160             num = numbers[num];
161         }
162     }
163 
164     private List<Edge> sortByWeight() {
165         //生成各边的权重列表
166         List<Edge> vertexEdgeList = new ArrayList<>();
167         //存储边已经存在的数组
168         boolean[][] existsEdge = new boolean[vertexNum][vertexNum];
169         int tmpStart, tmpEnd;
170         for (int i = 0; i < vertexNum; i++) {
171             for (int j = 0; j < vertexNum; j++) {
172                 //排除顶点自己的边
173                 if (i == j) {
174                     continue;
175                 }
176                 //跳过不存在的边
177                 if (vertices[i][j] == MAX_WEIGHT) {
178                     continue;
179                 }
180                 //转换边的开始和结束顶点的位置 如0-3转换为3-0
181                 if (i > j) {
182                     tmpStart = i;
183                     tmpEnd = j;
184                 } else {
185                     tmpStart = j;
186                     tmpEnd = i;
187                 }
188                 if (existsEdge[tmpStart][tmpEnd]) {
189                     continue;
190                 }
191                 //记录下处理过的边
192                 existsEdge[tmpStart][tmpEnd] = true;
193                 vertexEdgeList.add(new Edge(i, j, vertices[i][j]));
194             }
195         }
196         //根据权重排序
197         vertexEdgeList.sort(Comparator.comparingInt(Edge::getWeight));
198         return vertexEdgeList;
199     }
200 
201     private static class Edge {
202         private final int start;
203         private final int end;
204         private final int weight;
205 
206         public int getStart() {
207             return start;
208         }
209 
210         public int getEnd() {
211             return end;
212         }
213 
214         public int getWeight() {
215             return weight;
216         }
217 
218         public Edge(int start, int end, int weight) {
219             this.start = start;
220             this.end = end;
221             this.weight = weight;
222         }
223 
224         @Override
225         public String toString() {
226             return "Edge{" +
227                     "start=" + start +
228                     ", end=" + end +
229                     ", weight=" + weight +
230                     '}';
231         }
232     }
233 }

输出

+  0  1  2  3  4  5  
0  -  5  -  -  2  1  
1  5  -  3  -  -  5  
2  -  3  -  7  -  4  
3  -  -  7  -  4  6  
4  2  -  -  4  -  3  
5  1  5  4  6  3  -  
[prim]
minEdgeStart 0 minEdgeEnd 5 visitedVertices [true, false, false, false, false, true]
minEdgeStart 0 minEdgeEnd 4 visitedVertices [true, false, false, false, true, true]
minEdgeStart 4 minEdgeEnd 3 visitedVertices [true, false, false, true, true, true]
minEdgeStart 5 minEdgeEnd 2 visitedVertices [true, false, true, true, true, true]
minEdgeStart 2 minEdgeEnd 1 visitedVertices [true, true, true, true, true, true]
0-5 1
0-4 2
4-3 4
5-2 4
2-1 3
totalWeight 14
[kruskal]
Edge{start=0, end=5, weight=1}0->5 rootNodes[5, 99, 99, 99, 99, 99]
Edge{start=0, end=4, weight=2}5->4 rootNodes[5, 99, 99, 99, 99, 4]
Edge{start=1, end=2, weight=3}1->2 rootNodes[5, 2, 99, 99, 99, 4]
Edge{start=4, end=5, weight=3} skip edge 4-5 root 4  #从当前的rootNodes[5, 2, 99, 99, 99, 4]可以看出，目前是有三棵树：0-5、1-2、5-4，所以4-5这条边已经存在了，需要跳过
Edge{start=2, end=5, weight=4}2->4 rootNodes[5, 2, 4, 99, 99, 4]
Edge{start=3, end=4, weight=4}3->4 rootNodes[5, 2, 4, 4, 99, 4]
rootNodes[5, 2, 4, 4, 99, 4] edgeNum 5
0-5 1
0-4 2
1-2 3
2-5 4
3-4 4
totalWeight 14

可以看出普里姆算法是从一个顶点出发，逐步连接各个顶点，从树的角度看就是一颗树不断长出各个节点。而克鲁斯卡尔算法是从最小权重的边出发，不断连接各顶点，可能会出现多颗树，涉及树的合并，导致判断是否形成环会复杂一些。

参考资料

普里姆算法 https://baike.baidu.com/item/Prim/10242166

克鲁斯卡尔算法 https://baike.baidu.com/item/%E5%85%8B%E9%B2%81%E6%96%AF%E5%8D%A1%E5%B0%94%E7%AE%97%E6%B3%95

https://algorithmtutor.com/Data-Structures/Graph/Graphs-and-Graph-Terminologies/

https://www.hackerearth.com/practice/algorithms/graphs/minimum-spanning-tree/tutorial/