forked from dairongpeng/algorithm-note
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path10.md
More file actions
1185 lines (960 loc) · 34.8 KB
/
10.md
File metadata and controls
1185 lines (960 loc) · 34.8 KB
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
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
- [1 并查集、图相关算法](#1)
* [1.1 并查集](#11)
+ [1.1.1 并查集基本结构和操作](#111)
+ [1.1.2 例题](#112)
* [1.2 图相关算法](#12)
+ [1.2.1 图的概念](#121)
+ [1.2.2 图的表示方法](#122)
- [1.2.2.1 邻接表表示法](#1221)
- [1.2.2.2 邻接矩阵表示法](#1222)
+ [1.2.3 图的遍历](#123)
- [1.2.3.1 宽度优先遍历](#1231)
- [1.2.3.2 深度优先遍历](#1232)
+ [1.2.4 图的拓扑排序](#124)
+ [1.2.5 图的最小生成树算法](#125)
- [1.2.5.1 Kruskal（克鲁斯卡尔）算法](#1251)
- [1.2.5.2 Prim算法](#1252)
+ [1.2.6 图的最短路径算法](#126)
- [1.2.6.1 Dijkstra(迪杰特斯拉)算法](#1261)
- [1.2.6.2 floyd算法](#1262)
<h1 id='1'>1 并查集、图相关算法</h1>
<h2 id='11'>1.1 并查集</h2>
<h3 id='111'>1.1.1 并查集基本结构和操作</h3>
1、有若干个样本a、b、c、d...类型假设是V
2、在并查集中一开始认为每个样本都在单独的集合里
3、用户可以在任何时候调用如下两个方法：
boolean isSameSet(V x, V y)：查询样本x和样本y是否属于一个集合
void union(V x, V y)：把x和y各自所在集合的所有样本合并成一个集合
4、isSameSet和union方法的代价越低越好，最好O(1)
> 思路：isSameSet方法，我们设计为每个元素有一个指向自己的指针，成为代表点。判断两个元素是否在一个集合中，分别调用这两个元素的向上指针，两个元素最上方的指针如果内存地址相同，那么两个元素在一个集合中，反之不在
> 思路：union方法，例如将a所在的集合和e所在的集合合并成一个大的集合union(a,e)。a的代表点指针是a，e的代表点指针是e，我们拿较小的集合挂在大的集合下面，比如e小，那么e放在a的下面。链接的方式为小集合e头结点本来指向自己的代表节点，现在要指向a节点
> 并查集的优化点主要有两个，一个是合并的时候小的集合挂在大的集合下面，第二个优化是找某节点最上方的代表节点，把沿途节点全部拍平，下次再找该沿途节点，都变为O(1)。两种优化的目的都是为了更少的遍历节点。
> 由于我们加入了优化，如果N个节点，我们调用findFather越频繁，我们的时间复杂度越低，因为第一次调用我们加入了优化。如果findFather调用接近N次或者远远超过N次，我们并查集的时间复杂度就是O(1)。该复杂度只需要记住结论，证明无须掌握。该证明从1964年一直研究到1989年，整整25年才得出证明！算法导论23章，英文版接近50页的证明。
```Java
package class10;
import java.util.HashMap;
import java.util.List;
import java.util.Stack;
public class Code01_UnionFind {
// 并查集结构中的节点类型
public static class Node<V> {
V value;
public Node(V v) {
value = v;
}
}
public static class UnionSet<V> {
// 记录样本到样本代表点的关系
public HashMap<V, Node<V>> nodes;
// 记录某节点到父亲节点的关系。
// 比如b指向a，c指向a，d指向a，a指向自身
// map中保存的a->a b->a c->a d->a
public HashMap<Node<V>, Node<V>> parents;
// 只有当前点，他是代表点，会在sizeMap中记录该代表点的连通个数
public HashMap<Node<V>, Integer> sizeMap;
// 初始化构造一批样本
public UnionSet(List<V> values) {
// 每个样本的V指向自身的代表节点
// 每个样本当前都是独立的，parent是自身
// 每个样本都是代表节点放入sizeMap
for (V cur : values) {
Node<V> node = new Node<>(cur);
nodes.put(cur, node);
parents.put(node, node);
sizeMap.put(node, 1);
}
}
// 从点cur开始，一直往上找，找到不能再往上的代表点，返回
// 通过把路径上所有节点指向最上方的代表节点，目的是把findFather优化成O(1)的
public Node<V> findFather(Node<V> cur) {
// 在找father的过程中，沿途所有节点加入当前容器，便于后面扁平化处理
Stack<Node<V>> path = new Stack<>();
// 当前节点的父亲不是指向自己，进行循环
while (cur != parents.get(cur)) {
path.push(cur);
cur = parents.get(cur);
}
// 循环结束，cur是最上的代表节点
// 把沿途所有节点拍平，都指向当前最上方的代表节点
while (!path.isEmpty()) {
parents.put(path.pop(), cur);
}
return cur;
}
// isSameSet方法
public boolean isSameSet(V a, V b) {
// 先检查a和b有没有登记
if (!nodes.containsKey(a) || !nodes.containsKey(b)) {
return false;
}
// 比较a的最上的代表点和b最上的代表点
return findFather(nodes.get(a)) == findFather(nodes.get(b));
}
// union方法
public void union(V a, V b) {
// 先检查a和b有没有都登记过
if (!nodes.containsKey(a) || !nodes.containsKey(b)) {
return;
}
// 找到a的最上面的代表点
Node<V> aHead = findFather(nodes.get(a));
// 找到b的最上面的代表点
Node<V> bHead = findFather(nodes.get(b));
// 只有两个最上代表点内存地址不相同，需要union
if (aHead != bHead) {
// 由于aHead和bHead都是代表点，那么在sizeMap里可以拿到大小
int aSetSize = sizeMap.get(aHead);
int bSetSize = sizeMap.get(bHead);
// 哪个小，哪个挂在下面
Node<V> big = aSetSize >= bSetSize ? aHead : bHead;
Node<V> small = big == aHead ? bHead : aHead;
// 把小集合直接挂到大集合的最上面的代表节点下面
parents.put(small, big);
// 大集合的代表节点的size要吸收掉小集合的size
sizeMap.put(big, aSetSize + bSetSize);
// 把小的记录删除
sizeMap.remove(small);
}
}
}
}
```
==并查集用来处理连通性的问题特别方便==
<h3 id='112'>1.1.2 例题</h3>
学生实例有三个属性，身份证信息，B站ID,Github的Id。我们认为，任何两个学生实例，只要身份证一样，或者B站ID一样，或者Github的Id一样，我们都算一个人。给定一打拼学生实例，输出有实质有几个人？
> 思路：把实例的三个属性建立三张映射表，每个实例去对比，某个实例属性在表中能查的到，需要联通该实例到之前保存该实例属性的头结点下
```Java
package class10;
import java.util.HashMap;
import java.util.List;
import java.util.Stack;
public class Code07_MergeUsers {
public static class Node<V> {
V value;
public Node(V v) {
value = v;
}
}
public static class UnionSet<V> {
public HashMap<V, Node<V>> nodes;
public HashMap<Node<V>, Node<V>> parents;
public HashMap<Node<V>, Integer> sizeMap;
public UnionSet(List<V> values) {
for (V cur : values) {
Node<V> node = new Node<>(cur);
nodes.put(cur, node);
parents.put(node, node);
sizeMap.put(node, 1);
}
}
// 从点cur开始，一直往上找，找到不能再往上的代表点，返回
public Node<V> findFather(Node<V> cur) {
Stack<Node<V>> path = new Stack<>();
while (cur != parents.get(cur)) {
path.push(cur);
cur = parents.get(cur);
}
// cur头节点
while (!path.isEmpty()) {
parents.put(path.pop(), cur);
}
return cur;
}
public boolean isSameSet(V a, V b) {
if (!nodes.containsKey(a) || !nodes.containsKey(b)) {
return false;
}
return findFather(nodes.get(a)) == findFather(nodes.get(b));
}
public void union(V a, V b) {
if (!nodes.containsKey(a) || !nodes.containsKey(b)) {
return;
}
Node<V> aHead = findFather(nodes.get(a));
Node<V> bHead = findFather(nodes.get(b));
if (aHead != bHead) {
int aSetSize = sizeMap.get(aHead);
int bSetSize = sizeMap.get(bHead);
Node<V> big = aSetSize >= bSetSize ? aHead : bHead;
Node<V> small = big == aHead ? bHead : aHead;
parents.put(small, big);
sizeMap.put(big, aSetSize + bSetSize);
sizeMap.remove(small);
}
}
public int getSetNum() {
return sizeMap.size();
}
}
public static class User {
public String a;
public String b;
public String c;
public User(String a, String b, String c) {
this.a = a;
this.b = b;
this.c = c;
}
}
// (1,10,13) (2,10,37) (400,500,37)
// 如果两个user，a字段一样、或者b字段一样、或者c字段一样，就认为是一个人
// 请合并users，返回合并之后的用户数量
public static int mergeUsers(List<User> users) {
UnionSet<User> unionFind = new UnionSet<>(users);
HashMap<String, User> mapA = new HashMap<>();
HashMap<String, User> mapB = new HashMap<>();
HashMap<String, User> mapC = new HashMap<>();
for(User user : users) {
if(mapA.containsKey(user.a)) {
unionFind.union(user, mapA.get(user.a));
}else {
mapA.put(user.a, user);
}
if(mapB.containsKey(user.b)) {
unionFind.union(user, mapB.get(user.b));
}else {
mapB.put(user.b, user);
}
if(mapC.containsKey(user.c)) {
unionFind.union(user, mapC.get(user.c));
}else {
mapC.put(user.c, user);
}
}
// 向并查集询问，合并之后，还有多少个集合？
return unionFind.getSetNum();
}
}
```
<h2 id='12'>1.2 图相关算法</h2>
<h3 id='121'>1.2.1 图的概念</h3>
1、由点的集合和边的集合构成
2、虽然存在有向图和无向图的概念，但实际上都可以用有向图来表达，无向图可以理解为两个联通点互相指向
3、边上可能带有权值
<h3 id='122'>1.2.2 图的表示方法</h3>
对于下面一张无向图，可以改为有向图：
```
graph LR;
A-->C
C-->A
C-->B
B-->C
B-->D
D-->B
D-->A
A-->D
```
<h4 id='1221'>1.2.2.1 邻接表表示法</h4>
记录某个节点，直接到达的邻居节点：
A: C,D
B: C,D
C: A,B
D: B,A
如果是带有权重的边，可以封装我们的结构，例如A到C的权重是3,那么我们可以表示为A: C(3),D
<h4 id='1222'>1.2.2.2 邻接矩阵表示法</h4>
我们把不存在路径的用正无穷表示，这里用'-'表示，例如A到C的边权重是3，可把上图表示为：
```
A B C D
A 0 0 3 -
B - 0 0 0
C 3 0 0 -
D 0 0 - 0
```
> 图算法并不难，难点在于图有很多种表示方式，表达一张图的篇幅比较大，coding容易出错。我们的套路就是熟悉一种结构，遇到不同的表达方式，尝试转化成为我们熟悉的结构，进行操作
点结构的描述：
```Java
package class10;
import java.util.ArrayList;
// 点结构的描述 A 0
public class Node {
// 点的编号，标识
public int value;
// 入度，表示有多少个点连向该点
public int in;
// 出度，表示从该点出发连向别的节点多少
public int out;
// 直接邻居：表示由自己出发，直接指向哪些节点。nexts.size==out
public ArrayList<Node> nexts;
// 直接下级边：表示由自己出发的边有多少
public ArrayList<Edge> edges;
public Node(int value) {
this.value = value;
in = 0;
out = 0;
nexts = new ArrayList<>();
edges = new ArrayList<>();
}
}
```
边结构的描述：
```Java
package class10;
// 由于任何图都可以理解为有向图，我们定义有向的边结构
public class Edge {
// 边的权重信息
public int weight;
// 出发的节点
public Node from;
// 指向的节点
public Node to;
public Edge(int weight, Node from, Node to) {
this.weight = weight;
this.from = from;
this.to = to;
}
}
```
图结构的描述：
```Java
package class10;
import java.util.HashMap;
import java.util.HashSet;
// 图结构
public class Graph {
// 点的集合，编号为1的点是什么，用map
public HashMap<Integer, Node> nodes;
// 边的集合
public HashSet<Edge> edges;
public Graph() {
nodes = new HashMap<>();
edges = new HashSet<>();
}
}
```
任意图结构的描述，向我们上述的图结构转化：
例如，我们有一种图的描述是，变的权重，从from节点指向to节点
```Java
package class10;
public class GraphGenerator {
// matrix 所有的边
// N*3 的矩阵
// [weight, from节点上面的值，to节点上面的值]
public static Graph createGraph(Integer[][] matrix) {
// 定义我们的图结构
Graph graph = new Graph();
// 遍历给定的图结构进行转换
for (int i = 0; i < matrix.length; i++) {
// matrix[0][0], matrix[0][1] matrix[0][2]
Integer weight = matrix[i][0];
Integer from = matrix[i][1];
Integer to = matrix[i][2];
// 我们的图结构不包含当前from节点，新建该节点
if (!graph.nodes.containsKey(from)) {
graph.nodes.put(from, new Node(from));
}
// 没有to节点，建立该节点
if (!graph.nodes.containsKey(to)) {
graph.nodes.put(to, new Node(to));
}
// 拿出我们图结构的from节点
Node fromNode = graph.nodes.get(from);
// 拿出我们图结构的to节点
Node toNode = graph.nodes.get(to);
// 建立我们的边结构。权重，from指向to
Edge newEdge = new Edge(weight, fromNode, toNode);
// 把to节点加入到from节点的直接邻居中
fromNode.nexts.add(toNode);
// from的出度加1
fromNode.out++;
// to的入度加1
toNode.in++;
// 该边需要放到from的直接边的集合中
fromNode.edges.add(newEdge);
// 把该边加入到我们图结构的边集中
graph.edges.add(newEdge);
}
return graph;
}
}
```
<h3 id='123'>1.2.3 图的遍历</h3>
例如该图：
```
graph LR;
A-->B
A-->C
A-->D
B-->C
B-->E
C-->A
C-->B
C-->D
C-->E
```
<h4 id='1231'>1.2.3.1 宽度优先遍历</h4>
1、利用队列实现
2、从源节点开始依次按照宽度进队列，然后弹出
3、每弹出一个点，把该节点所有没有进过队列的邻接点放入队列
4、直到队列变空
> 宽度优先的思路：实质先遍历自己，再遍历自己的下一跳节点(同一层节点的顺序无需关系)，再下下跳节点......
我们从A点开始遍历：
1、A进队列--> Q[A]；A进入Set--> S[A]
2、A出队：Q[],**打印A**；A直接邻居为BCD,都不在Set中，进入队列Q[D,C,B], 进入S[A,B,C,D]
3、B出队：Q[D,C], B有CE三个邻居，C已经在Set中, 放入E, S[A,B,C,D,E]，队列放E, Q[E,D,C]
4、 C出队，周而复始
```Java
package class10;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
public class Code02_BFS {
// 从node出发，进行宽度优先遍历
public static void bfs(Node node) {
if (node == null) {
return;
}
Queue<Node> queue = new LinkedList<>();
// 图需要用set结构，因为图相比于二叉树有可能存在环
// 即有可能存在某个点多次进入队列的情况
HashSet<Node> set = new HashSet<>();
queue.add(node);
set.add(node);
while (!queue.isEmpty()) {
Node cur = queue.poll();
System.out.println(cur.value);
for (Node next : cur.nexts) {
// 直接邻居，没有进入过Set的进入Set和队列
// 用set限制队列的元素，防止有环队列一直会加入元素
if (!set.contains(next)) {
set.add(next);
queue.add(next);
}
}
}
}
}
```
<h4 id='1232'>1.2.3.2 深度优先遍历</h4>
1、利用栈实现
2、从源节点开始把节点按照深度放入栈，然后弹出
3、每弹出一个点，把该节点下一个没有进过栈的邻接点放入栈
4、直到栈变空
> 深度优先思路：表示从某个节点一直往下深入，知道没有路了，返回。我们的栈实质记录的是我们深度优先遍历的路径
我们从A点开始遍历：
1、A进栈，Stack[A] **打印A**。弹出A，当前弹出的节点A去枚举它的后代BCD，B没加入过栈中。压入A再压入B,Stack[B,A]。**打印B**
2、弹出B,B的直接后代邻居为CE,C再栈中而E不在栈中。重新压B,压E，Stack[E,B,A]。**打印E**
3、弹出E,E有邻居D,D不在栈中。压回E，再压D,此时Stack[D,E,B,A]。**打印D**
4、 弹出D,D的直接邻居是A,A已经在栈中了。说明A-B-E-D这条路径走到了尽头。弹出D之后，当前循环结束。继续while栈不为空，重复操作
```Java
package class10;
import java.util.HashSet;
import java.util.Stack;
public class Code02_DFS {
public static void dfs(Node node) {
if (node == null) {
return;
}
Stack<Node> stack = new Stack<>();
// Set的作用和宽度优先遍历类似，保证重复的点不要进栈
HashSet<Node> set = new HashSet<>();
stack.add(node);
set.add(node);
// 打印实时机是在进栈的时候
// 同理该步可以换成其他处理逻辑，表示深度遍历处理某件事情
System.out.println(node.value);
while (!stack.isEmpty()) {
Node cur = stack.pop();
// 枚举当前弹出节点的后代
for (Node next : cur.nexts) {
// 只要某个后代没进入过栈，进栈
if (!set.contains(next)) {
// 把该节点的父亲节点重新压回栈中
stack.push(cur);
// 再把自己压入栈中
stack.push(next);
set.add(next);
// 打印当前节点的值
System.out.println(next.value);
// 直接break，此时栈顶是当前next节点，达到深度优先的目的
break;
}
}
}
}
}
```
<h3 id='124'>1.2.4 图的拓扑排序</h3>
1、在图中找到所有入度为0的点输出
2、把所有入度为0的点在图中删掉，切消除这些点的影响边。继续找入度为0的点输出，删除，消边，周而复始
3、图的所有点都被删除后，依次输出的顺序就是图的拓扑排序
**要求：有向图且其中没有环**
**应用：事件安排，编译顺序**
> 在我们的项目中，项目之间互相依赖，就是拓扑排序的一个应用，从最底层依赖的包往上层编译，最终把总的项目编译通过。所以项目中循环依赖是编译不通过的
例如下列的有向无环图：
```
graph LR;
A-->B
B-->C
A-->C
C-->E
E-->F
C-->T
F-->T
```
图中的字母代表事情，做事情的先后顺序就是按照有向图的描述，请安排事情的先后顺序（拓扑排序）。
拓扑排序为：A B C E F T
```Java
package class10;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
public class Code03_TopologySort {
// 有向无环图，返回拓扑排序的顺序list
public static List<Node> sortedTopology(Graph graph) {
// key：某一个node
// value：该节点剩余的入度
HashMap<Node, Integer> inMap = new HashMap<>();
// 剩余入度为0的点，才能进这个队列
Queue<Node> zeroInQueue = new LinkedList<>();
// 拿到该图中所有的点集
for (Node node : graph.nodes.values()) {
// 初始化每个点，每个点的入度是原始节点的入度信息
// 加入inMap
inMap.put(node, node.in);
// 由于是有向无环图，则必定有入度为0的起始点。放入到zeroInQueue
if (node.in == 0) {
zeroInQueue.add(node);
}
}
// 拓扑排序的结果，依次加入result
List<Node> result = new ArrayList<>();
while (!zeroInQueue.isEmpty()) {
// 该有向无环图初始入度为0的点，直接弹出放入结果集中
Node cur = zeroInQueue.poll();
result.add(cur);
// 该节点的下一层邻居节点，入度减一且加入到入度的map中
for (Node next : cur.nexts) {
inMap.put(next, inMap.get(next) - 1);
// 如果下一层存在入度变为0的节点，加入到0入度的队列中
if (inMap.get(next) == 0) {
zeroInQueue.add(next);
}
}
}
return result;
}
}
```
<h3 id='125'>1.2.5 图的最小生成树算法</h3>
> 最小生成树解释，就是在不破坏原有图点与点的连通性基础上，让连通的边的整体权值最小。返回最小权值或者边的集合
<h4 id='1251'>1.2.5.1 Kruskal（克鲁斯卡尔）算法</h4>
> 连通性借助并查集实现
1、总是从权值最小的边开始考虑，依次考察权值依次变大的边
2、当前的边要么进入最小生成树的集合，要么丢弃
3、如果当前的边进入最小生成树的集合中不会形成环，就要当前边
4、如果当前的边进入最小生成树的集合中会形成环，就不要当前边
5、考察完所有边之后，最小生成树的集合也就得到了
```Java
package class10;
import java.util.Collection;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;
import java.util.Stack;
//undirected graph only
public class Code04_Kruskal {
// Union-Find Set 我们的并查集结构
public static class UnionFind {
// key 某一个节点， value key节点往上的节点
private HashMap<Node, Node> fatherMap;
// key 某一个集合的代表节点, value key所在集合的节点个数
private HashMap<Node, Integer> sizeMap;
public UnionFind() {
fatherMap = new HashMap<Node, Node>();
sizeMap = new HashMap<Node, Integer>();
}
public void makeSets(Collection<Node> nodes) {
fatherMap.clear();
sizeMap.clear();
for (Node node : nodes) {
fatherMap.put(node, node);
sizeMap.put(node, 1);
}
}
private Node findFather(Node n) {
Stack<Node> path = new Stack<>();
while(n != fatherMap.get(n)) {
path.add(n);
n = fatherMap.get(n);
}
while(!path.isEmpty()) {
fatherMap.put(path.pop(), n);
}
return n;
}
public boolean isSameSet(Node a, Node b) {
return findFather(a) == findFather(b);
}
public void union(Node a, Node b) {
if (a == null || b == null) {
return;
}
Node aDai = findFather(a);
Node bDai = findFather(b);
if (aDai != bDai) {
int aSetSize = sizeMap.get(aDai);
int bSetSize = sizeMap.get(bDai);
if (aSetSize <= bSetSize) {
fatherMap.put(aDai, bDai);
sizeMap.put(bDai, aSetSize + bSetSize);
sizeMap.remove(aDai);
} else {
fatherMap.put(bDai, aDai);
sizeMap.put(aDai, aSetSize + bSetSize);
sizeMap.remove(bDai);
}
}
}
}
public static class EdgeComparator implements Comparator<Edge> {
@Override
public int compare(Edge o1, Edge o2) {
return o1.weight - o2.weight;
}
}
// K算法
public static Set<Edge> kruskalMST(Graph graph) {
// 先拿到并查集结构
UnionFind unionFind = new UnionFind();
// 该图的所有点加入到并查集结构
unionFind.makeSets(graph.nodes.values());
// 边按照权值从小到大排序，加入到堆
PriorityQueue<Edge> priorityQueue = new PriorityQueue<>(new EdgeComparator());
for (Edge edge : graph.edges) { // M 条边
priorityQueue.add(edge); // O(logM)
}
Set<Edge> result = new HashSet<>();
// 堆不为空，弹出小根堆的堆顶
while (!priorityQueue.isEmpty()) {
// 假设M条边，O(logM)
Edge edge = priorityQueue.poll();
// 如果该边的左右两侧不在同一个集合中
if (!unionFind.isSameSet(edge.from, edge.to)) { // O(1)
// 要这条边
result.add(edge);
// 联合from和to
unionFind.union(edge.from, edge.to);
}
}
return result;
}
}
```
> K算法求无向图的最小生成树，求权值是没问题的，如果纠结最小生成树的连通结构，实质是少了一侧，即A指向B, B指向A只会保留其一。可以手动补齐
<h4 id='1252'>1.2.5.2 Prim算法</h4>
> P算法无需并查集结构，普通set即可满足
1、任意指定一个出发点，譬如A, A的直接边被解锁
2、在A解锁的边里选择一个最小的边，该边两侧有没有新节点，如果有选择该边。没有就舍弃该边
3、在被选择的新节点中再解锁该节点的直接边
4、周而复始，直到所有点被解锁
```Java
package class10;
import java.util.Comparator;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;
// undirected graph only
public class Code05_Prim {
public static class EdgeComparator implements Comparator<Edge> {
@Override
public int compare(Edge o1, Edge o2) {
return o1.weight - o2.weight;
}
}
public static Set<Edge> primMST(Graph graph) {
// 解锁的边进入小根堆
PriorityQueue<Edge> priorityQueue = new PriorityQueue<>(new EdgeComparator());
// 哪些点被解锁出来了
HashSet<Node> nodeSet = new HashSet<>();
// 已经考虑过的边，不要重复考虑
Set<Edge> result = new HashSet<>();
// 依次挑选的的边在result里
Set<Edge> result = new HashSet<>();
// 随便挑了一个点,进入循环处理完后直接break
for (Node node : graph.nodes.values()) {
// node 是开始点
if (!nodeSet.contains(node)) {
// 开始节点保留
nodeSet.add(node);
// 开始节点的所有邻居节点全部放到小根堆
// 即由一个点，解锁所有相连的边
for (Edge edge : node.edges) {
if (!edgeSet.contains(edge)) {
edgeSet.add(edge);
priorityQueue.add(edge);
}
}
while (!priorityQueue.isEmpty()) {
// 弹出解锁的边中，最小的边
Edge edge = priorityQueue.poll();
// 可能的一个新的点,from已经被考虑了，只需要看to
Node toNode = edge.to;
// 不含有的时候，就是新的点
if (!nodeSet.contains(toNode)) {
nodeSet.add(toNode);
result.add(edge);
for (Edge nextEdge : toNode.edges) {
// 没加过的，放入小根堆
if (!edgeSet.contains(edge)) {
edgeSet.add(edge);
priorityQueue.add(edge);
}
}
}
}
}
// 直接break意味着我们不用考虑森林的情况
// 如果不加break我们可以兼容多个无向图的森林的生成树
// break;
}
return result;
}
// 请保证graph是连通图
// graph[i][j]表示点i到点j的距离，如果是系统最大值代表无路
// 返回值是最小连通图的路径之和
public static int prim(int[][] graph) {
int size = graph.length;
int[] distances = new int[size];
boolean[] visit = new boolean[size];
visit[0] = true;
for (int i = 0; i < size; i++) {
distances[i] = graph[0][i];
}
int sum = 0;
for (int i = 1; i < size; i++) {
int minPath = Integer.MAX_VALUE;
int minIndex = -1;
for (int j = 0; j < size; j++) {
if (!visit[j] && distances[j] < minPath) {
minPath = distances[j];
minIndex = j;
}
}
if (minIndex == -1) {
return sum;
}
visit[minIndex] = true;
sum += minPath;
for (int j = 0; j < size; j++) {
if (!visit[j] && distances[j] > graph[minIndex][j]) {
distances[j] = graph[minIndex][j];
}
}
}
return sum;
}
public static void main(String[] args) {
System.out.println("hello world!");
}
}
```
<h3 id='126'>1.2.6 图的最短路径算法</h3>
<h4 id='1261'>1.2.6.1 Dijkstra(迪杰特斯拉)算法</h4>
> Dijkstra算法必须要求边的权值不为负，且必须指定出发点。则可以求出发点到所有节点的最短距离是多少。如果到达不了，为正无穷
1、Dijkstra算法必须指定一个源点
2、生成一个源点到各个点的最小距离表，一开始只有一条记录，即原点到自己的最小距离为0，源点到其他所有点的最小距离都未正无穷大
3、从距离表中拿出没拿过记录里的最小记录，通过这个点出发的边，更新源点到各个点的最小距离表，不断重复这一步
4、源点到所有的点记录如果都被拿过一遍，过程停止，最小距离表得到了
```Java
package class10;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map.Entry;
// 没改进之前的版本
public class Code06_Dijkstra {
// 返回的map表就是从from到表中key的各个的最小距离
// 某个点不在map中记录，则from到该点位正无穷
public static HashMap<Node, Integer> dijkstra1(Node from) {
// 从from出发到所有点的最小距离表
HashMap<Node, Integer> distanceMap = new HashMap<>();
// from到from距离为0
distanceMap.put(from, 0);
// 已经求过距离的节点，存在selectedNodes中，以后再也不碰
HashSet<Node> selectedNodes = new HashSet<>();
// from 0 得到没选择过的点的最小距离
Node minNode = getMinDistanceAndUnselectedNode(distanceMap, selectedNodes);
// 得到minNode之后
while (minNode != null) {
// 把minNode对应的距离取出,此时minNode就是桥连点
int distance = distanceMap.get(minNode);
// 把minNode上所有的邻边拿出来
// 这里就是要拿到例如A到C和A到桥连点B再到C哪个距离小的距离
for (Edge edge : minNode.edges) {
// 某条边对应的下一跳节点toNode
Node toNode = edge.to;
// 如果关于from的distencMap中没有去toNode的记录，表示正无穷，直接添加该条
if (!distanceMap.containsKey(toNode)) {
// from到minNode的距离加上个minNode到当前to节点的边距离
distanceMap.put(toNode, distance + edge.weight);