图的一些基本概念

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/



这篇关于图的一些基本概念的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程