1 并查集、图相关算法
1.1 并查集
1.1.1 并查集基本结构和操作
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页的证明。
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);
}
}
}
}
==并查集用来处理连通性的问题特别方便==
1.1.2 例题
学生实例有三个属性，身份证信息，B站ID,Github的Id。我们认为，任何两个学生实例，只要身份证一样，或者B站ID一样，或者Github的Id一样，我们都算一个人。给定一打拼学生实例，输出有实质有几个人？
思路：把实例的三个属性建立三张映射表，每个实例去对比，某个实例属性在表中能查的到，需要联通该实例到之前保存该实例属性的头结点下
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();
}
}
1.2 图相关算法
1.2.1 图的概念
1、由点的集合和边的集合构成
2、虽然存在有向图和无向图的概念，但实际上都可以用有向图来表达，无向图可以理解为两个联通点互相指向
3、边上可能带有权值
1.2.2 图的表示方法
对于下面一张无向图，可以改为有向图：
graph LR;
A-->C
C-->A
C-->B
B-->C
B-->D
D-->B
D-->A
A-->D
1.2.2.1 邻接表表示法
记录某个节点，直接到达的邻居节点：
A: C,D
B: C,D
C: A,B
D: B,A
如果是带有权重的边，可以封装我们的结构，例如A到C的权重是3,那么我们可以表示为A: C(3),D
1.2.2.2 邻接矩阵表示法
我们把不存在路径的用正无穷表示，这里用’-‘表示，例如A到C的边权重是3，可把上图表示为：
A B C D
A 0 0 3 -
B - 0 0 0
C 3 0 0 -
D 0 0 - 0
图算法并不难，难点在于图有很多种表示方式，表达一张图的篇幅比较大，coding容易出错。我们的套路就是熟悉一种结构，遇到不同的表达方式，尝试转化成为我们熟悉的结构，进行操作
点结构的描述：
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<>();
}
}
边结构的描述：
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;
}
}
图结构的描述：
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节点
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;
}
}
1.2.3 图的遍历
例如该图：
graph LR;
A-->B
A-->C
A-->D
B-->C
B-->E
C-->A
C-->B
C-->D
C-->E
1.2.3.1 宽度优先遍历
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出队，周而复始
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);
}
}
}
}
}
1.2.3.2 深度优先遍历
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栈不为空，重复操作
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;
}
}
}
}
}
1.2.4 图的拓扑排序
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
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;
}
}
1.2.5 图的最小生成树算法
最小生成树解释，就是在不破坏原有图点与点的连通性基础上，让连通的边的整体权值最小。返回最小权值或者边的集合
1.2.5.1 Kruskal（克鲁斯卡尔）算法
连通性借助并查集实现
1、总是从权值最小的边开始考虑，依次考察权值依次变大的边
2、当前的边要么进入最小生成树的集合，要么丢弃
3、如果当前的边进入最小生成树的集合中不会形成环，就要当前边
4、如果当前的边进入最小生成树的集合中会形成环，就不要当前边
5、考察完所有边之后，最小生成树的集合也就得到了
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只会保留其一。可以手动补齐
1.2.5.2 Prim算法
P算法无需并查集结构，普通set即可满足
1、任意指定一个出发点，譬如A, A的直接边被解锁
2、在A解锁的边里选择一个最小的边，该边两侧有没有新节点，如果有选择该边。没有就舍弃该边
3、在被选择的新节点中再解锁该节点的直接边
4、周而复始，直到所有点被解锁
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!");
}
}
1.2.6 图的最短路径算法
1.2.6.1 Dijkstra(迪杰特斯拉)算法
Dijkstra算法必须要求边的权值不为负，且必须指定出发点。则可以求出发点到所有节点的最短距离是多少。如果到达不了，为正无穷
1、Dijkstra算法必须指定一个源点
2、生成一个源点到各个点的最小距离表，一开始只有一条记录，即原点到自己的最小距离为0，源点到其他所有点的最小距离都未正无穷大
3、从距离表中拿出没拿过记录里的最小记录，通过这个点出发的边，更新源点到各个点的最小距离表，不断重复这一步
4、源点到所有的点记录如果都被拿过一遍，过程停止，最小距离表得到了
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);
// 如果有，看该距离是否更小，更小就更新
} else {
distanceMap.put(edge.to,
Math.min(distanceMap.get(toNode), distance + edge.weight));
}
}
// 锁上minNode，表示from通过minNode到其他节点的最小值已经找到
// minNode将不再使用
selectedNodes.add(minNode);
// 再在没有选择的节点中挑选MinNode当成from的桥接点
minNode = getMinDistanceAndUnselectedNode(distanceMap, selectedNodes);
}
// 最终distanceMap全部更新，返回
return distanceMap;
}
// 得到没选择过的点的最小距离
public static Node getMinDistanceAndUnselectedNode(
HashMap<Node, Integer> distanceMap,
HashSet<Node> touchedNodes) {
Node minNode = null;
int minDistance = Integer.MAX_VALUE;
for (Entry<Node, Integer> entry : distanceMap.entrySet()) {
Node node = entry.getKey();
int distance = entry.getValue();
// 没有被选择过，且距离最小
if (!touchedNodes.contains(node) && distance < minDistance) {
minNode = node;
minDistance = distance;
}
}
return minNode;
}
/**
* 我们可以借助小根堆来替代之前的distanceMap。达到优化算法的目的
* 原因是之前我们要遍历hash表选出最小距离，现在直接是堆顶元素
* 但是我们找到通过桥节点更小的距离后，需要临时更该堆结构中元素数据
* 所以系统提供的堆我们需要改写
**/
public static class NodeRecord {
public Node node;
public int distance;
public NodeRecord(Node node, int distance) {
this.node = node;
this.distance = distance;
}
}
// 自定义小根堆结构
// 需要提供add元素的方法，和update元素的方法
// 需要提供ignore方法，表示我们已经找到from到某节点的最短路径
// 再出现from到该节点的其他路径距离，我们直接忽略
public static class NodeHeap {
private Node[] nodes; // 实际的堆结构
// key 某一个node， value 上面堆中的位置
// 如果节点曾经进过堆，现在不在堆上，则node对应-1
// 用来找需要ignore的节点
private HashMap<Node, Integer> heapIndexMap;
// key 某一个节点， value 从源节点出发到该节点的目前最小距离
private HashMap<Node, Integer> distanceMap;
private int size; // 堆上有多少个点
public NodeHeap(int size) {
nodes = new Node[size];
heapIndexMap = new HashMap<>();
distanceMap = new HashMap<>();
size = 0;
}
// 该堆是否空
public boolean isEmpty() {
return size == 0;
}
// 有一个点叫node，现在发现了一个从源节点出发到达node的距离为distance
// 判断要不要更新，如果需要的话，就更新
public void addOrUpdateOrIgnore(Node node, int distance) {
// 如果该节点在堆上，就看是否需要更新
if (inHeap(node)) {
distanceMap.put(node, Math.min(distanceMap.get(node), distance));
// 该节点进堆，判断是否需要调整
insertHeapify(node, heapIndexMap.get(node));
}
// 如果没有进入过堆。新建，进堆
if (!isEntered(node)) {
nodes[size] = node;
heapIndexMap.put(node, size);
distanceMap.put(node, distance);
insertHeapify(node, size++);
}
// 如果不在堆上，且进来过堆上，什么也不做，ignore
}
// 弹出from到堆顶节点的元素，获取到该元素的最小距离，再调整堆结构
public NodeRecord pop() {
NodeRecord nodeRecord = new NodeRecord(nodes[0], distanceMap.get(nodes[0]));
// 把最后一个元素放在堆顶，进行heapify
swap(0, size - 1);
heapIndexMap.put(nodes[size - 1], -1);
distanceMap.remove(nodes[size - 1]);
// free C++同学还要把原本堆顶节点析构，对java同学不必
nodes[size - 1] = null;
heapify(0, --size);
return nodeRecord;
}
private void insertHeapify(Node node, int index) {
while (distanceMap.get(nodes[index])
< distanceMap.get(nodes[(index - 1) / 2])) {
swap(index, (index - 1) / 2);
index = (index - 1) / 2;
}
}
private void heapify(int index, int size) {
int left = index * 2 + 1;
while (left < size) {
int smallest = left + 1 < size && distanceMap.get(nodes[left + 1]) < distanceMap.get(nodes[left])
? left + 1
: left;
smallest = distanceMap.get(nodes[smallest])
< distanceMap.get(nodes[index]) ? smallest : index;
if (smallest == index) {
break;
}
swap(smallest, index);
index = smallest;
left = index * 2 + 1;
}
}
// 判断node是否进来过堆
private boolean isEntered(Node node) {
return heapIndexMap.containsKey(node);
}
// 判断某个节点是否在堆上
private boolean inHeap(Node node) {
return isEntered(node) && heapIndexMap.get(node) != -1;
}
private void swap(int index1, int index2) {
heapIndexMap.put(nodes[index1], index2);
heapIndexMap.put(nodes[index2], index1);
Node tmp = nodes[index1];
nodes[index1] = nodes[index2];
nodes[index2] = tmp;
}
}
// 使用自定义小根堆，改进后的dijkstra算法
// 从from出发，所有from能到达的节点，生成到达每个节点的最小路径记录并返回
public static HashMap<Node, Integer> dijkstra2(Node from, int size) {
// 申请堆
NodeHeap nodeHeap = new NodeHeap(size);
// 在堆上添加from节点到from节点距离为0
nodeHeap.addOrUpdateOrIgnore(from, 0);
// 最终的结果集
HashMap<Node, Integer> result = new HashMap<>();
while (!nodeHeap.isEmpty()) {
// 每次在小根堆弹出堆顶元素
NodeRecord record = nodeHeap.pop();
// 拿出的节点
Node cur = record.node;
// from到该节点的距离
int distance = record.distance;
// 以此为桥接点，找是否有更小的距离到该节点的其他to节点
// addOrUpdateOrIgnore该方法保证如果from到to的节点没有，就add
// 如果有,看是否需要Ignore，如果不需要Ignore且更小，就Update
for (Edge edge : cur.edges) {
nodeHeap.addOrUpdateOrIgnore(edge.to, edge.weight + distance);
}
result.put(cur, distance);
}
return result;
}
}
1.2.6.2 floyd算法
图节点的最短路径，处理权值可能为负的情况。三层for循环，比较简单