图的一些基本概念
2022/7/23 23:26:46
本文主要是介绍图的一些基本概念，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
终于来到图这部分，一起了解下这种“最复杂”的数据结构。
之前提到的数组、树的各节点（元素）之间存在前后关系（左右节点），或者层次关系（父节点，子节点）。而图结构中一个节点可以有多个关联节点，多个节点又可以关联同一个节点。任意两个节点都可能存在关系。
我们这次从一个具体例子来看，最后再给出各个定义(复杂关系导致的基本概念较多）。
假设你是一名网络工程师，负责连三个小区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/
这篇关于图的一些基本概念的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
- 2024-11-23JAVA语音识别项目入门教程
- 2024-11-23Java云原生学习：从入门到实践
- 2024-11-22Java创业学习：初学者的全面指南
- 2024-11-22JAVA创业学习：零基础入门到实战应用教程
- 2024-11-22Java创业学习：从零开始的Java编程入门教程
- 2024-11-22Java对接阿里云智能语音服务学习教程
- 2024-11-22JAVA对接阿里云智能语音服务学习教程
- 2024-11-22Java对接阿里云智能语音服务学习教程
- 2024-11-22Java副业学习：零基础入门到实战项目
- 2024-11-22Java副业学习：零基础入门指南
