10-并查集结构和图相关的算法
并查集
定义：
- 有若干个样本a、b、c、d…类型假设是V
- 在并查集中一开始认为每个样本都在单独的集合里
- 用户可以在任何时候调用如下两个方法 ：
boolean isSameSet(V x, V y) : 查询样本x和样本y是否属于一个集合
void union(V x, V y) : 把x和y各自所在集合的所有样本合并成一个集合 - isSameSet和union方法的代价越低越好
要点
- 每个节点都有一条往上指的指针
- 节点a往上找到的头节点，叫做a所在集合的代表节点
- 查询x和y是否属于同一个集合，就是看看找到的代表节点是不是一个
- 把x和y各自所在集合的所有点合并成一个集合，只需要小集合的代表点挂在大集合的代表点的下方即可
思想就是：用集合中的一个元素去代表集合。这个元素相当于这个集合的首领。如果有另外一个集合想合并，其实就是union方法，加入到这个集合中来。但“首领”只有一个。所以在union中，一般是个数少的来“投靠“个数多的。
并查集代码：
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);
}
}
}
并查集的优化
-
节点往上找代表点的过程，把沿途的链变成扁平的
-
小集合挂在大集合的下面
-
如果方法调用很频繁，那么单次调用的代价为O(1)，两个方法都如此
并查集的应用
-
连通性的问题
-
元素分组
-
解决两大块区域的合并问题
-
常用在图等领域中
相关练习题：
图
-
由点的集合和边的集合构成
-
虽然存在有向图和无向图的概念，但实际上都可以用有向图来表达
-
边上可能带有权值
图结构的表达
-
邻接表法
-
邻接矩阵法
-
除此之外还有其他众多的方式
图的面试题如何搞定
图的算法都不算难，只不过coding的代价比较高
- 先用自己最熟练的方式，实现图结构的表达
- 在自己熟悉的结构上，实现所有常用的图算法作为模板
- 把面试题提供的图结构转化为自己熟悉的图结构，再调用模板或改写即可
图结构
上面说了，因为图结构有许多种的表达，对应到算法上，也会有些区别。
所以我一般会用自己熟悉的图结构，而对应到是算法上，也更熟练。
提供的图结构，也可以转化为自己熟悉的图结构。
我常用的图结构
/**
* @Description: 点结构的描述
* @author li
* @create 2022/8/8 10:04
*/
public class Node {
//编号，也可为string
public int value;
//入度
public int in;
//出度
public int 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<>();
}
}
/**
* @Description: 边描述、有向边
* @author li
* @create 2022/8/8 10:06
*/
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;
}
}
/**
* @Description: 图结构的描述
* @author li
* @create 2022/8/8 10:07
*/
public class Graph {
//点集
public HashMap<Integer, Node> nodes;
//边集
public HashSet<Edge> edges;
public Graph() {
nodes = new HashMap<>();
edges = new HashSet<>();
}
}
转换
因为会提供不同的图结构，所以可以转换成自己熟悉的图结构。
下面是个转换的例子
/**
* @Description: 其他图结构，转为自己用的顺手的图结构
* @author li
* @create 2022/8/8 10:10
*/
public class GraphGenerator {
// matrix 所有的边
// N*3 的矩阵
// [weight, from节点上面的值，to节点上面的值]
//
// [ 5 , 0 , 7]
// [ 3 , 0, 1]
//
public static Graph createGraph(int[][] matrix) {
Graph graph = new Graph();
for (int i = 0; i < matrix.length; i++) {
// 拿到每一条边， matrix[i]
int weight = matrix[i][0];
int from = matrix[i][1];
int to = matrix[i][2];
//得到from、to 点，然后通过graph先建立点集
if (!graph.nodes.containsKey(from)) {
graph.nodes.put(from, new Node(from));
}
if (!graph.nodes.containsKey(to)) {
graph.nodes.put(to, new Node(to));
}
Node fromNode = graph.nodes.get(from);
Node toNode = graph.nodes.get(to);
//建边
Edge newEdge = new Edge(weight, fromNode, toNode);
//设置点的next
fromNode.nexts.add(toNode);
//设置出度
fromNode.out++;
//设置入度
toNode.in++;
//添加点的直接边
fromNode.edges.add(newEdge);
//添加到大图图的边集
graph.edges.add(newEdge);
}
return graph;
}
}
下面的代码，都基于上面的图结构
图的宽度优先遍历
理论：
其实在之前的树的学习中，就学习过宽度优先遍历。其实就是树中的层序遍历。
- 利用队列实现
- 从源节点开始依次按照宽度进队列，然后弹出
- 每弹出一个点，把该节点所有没有进过队列的邻接点放入队列
- 直到队列变空
代码：
// 从node出发，进行宽度优先遍历
public static void bfs(Node start) {
if (start == null) {
return;
}
Queue<Node> queue = new LinkedList<>();
HashSet<Node> set = new HashSet<>();
queue.add(start);
set.add(start);
while (!queue.isEmpty()) {
//弹出打印
Node cur = queue.poll();
System.out.println(cur.value);
//没进入过set的的直接邻居，放入set和队列
for (Node next : cur.nexts) {
if (!set.contains(next)) {
set.add(next);
queue.add(next);
}
}
}
}
图的深度优先遍历
理论：
深度优先遍历，见名知意，以深度优先。
一直向下走，走不同了掉头，与之前树的先序遍历很像。
- 利用栈实现
- 从源节点开始把节点按照深度放入栈，然后弹出
- 每弹出一个点，把该节点下一个没有进过栈的邻接点放入栈
- 直到栈变空
代码：
public static void dfs(Node node) {
if (node == null) {
return;
}
Stack<Node> stack = new Stack<>();
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;
}
}
}
}
DFS主要用栈实现，因为我会一直往下走。走的时候，会将其放入栈和HashSet中，HashSet主要是用来记录这个节点是否已经走过。
栈其实记录是的路径状态。因为栈记录了路径，所有走到尽头后，可以pop弹出回溯，回到上一个节点，找有没有其他的路。
因为栈和for循环的结合，所以节点找到第一条路，开始走时，会break，不去走当前这个节点的其他路。这条路走完，因为是栈，所以可pop弹出回溯。
回溯回来时， 会继续for循环找路，因为第一条路以及走了，会在set中注册。所以会循环找到第二条路，开始走。
大致思路就是这样
图的拓扑排序算法
理论：
拓扑排序：其实就是安排先后顺序，箭头是依赖关系。例如A，指向A的，必须先按，然后安排A。
就和编译顺序一样，先要把依赖的部分编译了。
步骤：
- 在图中找到所有入度为0的点输出
- 把所有入度为0的点在图中删掉，继续找入度为0的点输出，周而复始
- 图的所有点都被删除后，依次输出的顺序就是拓扑排序
要求：有向图且其中没有环
应用：事件安排、编译顺序
代码：
public static List<Node> sortedTopology(Graph graph) {
// key 某个节点 value 剩余的入度
HashMap<Node, Integer> inMap = new HashMap<>();
// 只有剩余入度为0的点，才进入这个队列
Queue<Node> zeroInQueue = new LinkedList<>();
//拿到图所有的点集
for (Node node : graph.nodes.values()) {
//放入原始剩余入度的点集
inMap.put(node, node.in);
//入度为0，放入zeroInQueue
if (node.in == 0) {
zeroInQueue.add(node);
}
}
//拓扑排序的结果
List<Node> result = new ArrayList<>();
while (!zeroInQueue.isEmpty()) {
//将入度0的，放入结果
Node cur = zeroInQueue.poll();
result.add(cur);
//因为我已经放入结果，消除我对邻居的影响。如果邻居的入度也为0，就加入zeroInQueue
for (Node next : cur.nexts) {
inMap.put(next, inMap.get(next) - 1);
if (inMap.get(next) == 0) {
zeroInQueue.add(next);
}
}
}
return result;
}
最小生成树算法之Kruskal
理论
提到**最小生成树一定是无向图，**有向图的最小生成树要给出发点
并查集(点)+优先队列(边权值)
- 总是从权值最小的边开始考虑，依次考察权值依次变大的边
- 当前的边要么进入最小生成树的集合，要么丢弃
- 当前的边进入最小生成树的集合中不会形成环，就要当前边
- 如果当前的边进入最小生成树的集合中会形成环，就不要当前边
- 考察完所有边之后，最小生成树的集合也得到了
可以用并查集检查是否出现环
主要用并查集来实现。
会用到3个结构，并查集、小根堆、HashSet。
并查集是点用的，小根堆是边用的，HashSet是结果
生成一个点集，然后边通过小根堆，权值排序。
然后从权值边最小的开始，从小到大弹出，如果通过并查集发现是不同一个集合，就添加到HashSet结果中，并将这条边的2点union。
如果是同一个集合，就然后继续弹出下一条边
代码：
public static class EdgeComparator implements Comparator<Edge> {
@Override
public int compare(Edge o1, Edge o2) {
return o1.weight - o2.weight;
}
}
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 条边
Edge edge = priorityQueue.poll(); // O(logM)
if (!unionFind.isSameSet(edge.from, edge.to)) { // O(1)
result.add(edge);
unionFind.union(edge.from, edge.to);
}
}
return result;
}
最小生成树算法之Prim
理论：
思路就是点解锁边, 边解锁点
小根堆(解锁的边) + 哈希Set(被解锁的点，已经考虑过的边)
从开始点走，解锁开始点，并加入set代表已经被解锁。然后去解锁当前点的边，并将其加入到边的小根堆里。
边加入到小根堆后，也要加入set里，代表这条边已经被考虑过了。
通过小根堆里的边，去解锁点，然后通过点，去解锁边。
set主要就是判断是否被解锁用过了。
- 可以从任意节点出发来寻找最小生成树
- 某个点加入到被选取的点中后，解锁这个点出发的所有新的边
- 在所有解锁的边中选最小的边，然后看看这个边会不会形成环
- 如果会，不要当前边，继续考察剩下解锁的边中最小的边，重复3
- 如果不会，要当前边，将该边的指向点加入到被选取的点中，重复2
- 当所有点都被选取，最小生成树就得到了
2个prim方法，一个得到的是最小生成树边的set，一个是最小生成树边的路径和
代码：
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<>();
//已经考虑过的边，不要重复考虑
HashSet<Edge> edgeSet = new HashSet<>();
// 依次挑选的的边在result里
Set<Edge> result = new HashSet<>();
//for循环，防森林，如果无向图无森林，可以不用for循环
for (Node node : graph.nodes.values()) { // 随便挑了一个点
// node 是开始点
if (!nodeSet.contains(node)) {
nodeSet.add(node);
for (Edge edge : node.edges) { // 由一个点，解锁所有相连的边
if(!edgeSet.contains(edge)){
//解锁的边，进入priorityQueue
priorityQueue.add(edge);
//进入priorityQueue，代表该边已经被考虑过，进入set
edgeSet.add(edge);
}
}
//弹出最小边，得到点，看其是否是新的点，是新的加入，然后继续通过点解锁边，并将这些边加入小根堆
while (!priorityQueue.isEmpty()) {
Edge edge = priorityQueue.poll(); // 弹出解锁的边中，最小的边
Node toNode = edge.to; // 可能的一个新的点
// 不含有的时候，就是新的点
if (!nodeSet.contains(toNode)) {
nodeSet.add(toNode);
result.add(edge);
for (Edge nextEdge : toNode.edges) {
priorityQueue.add(nextEdge);
}
}
}
}
// 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;
}
Dijkstra算法
理论：
Dijkstra 算法是一个基于「贪心」、「广度优先搜索」、「动态规划」求一个图中一个点到其他所有点的最短路径的算法 。
且Dijkstra算法必须指定一个源点，要求的是从出发点到所有点的最短距离的一张表 。
-
生成一个源点到各个点的最小距离表，一开始只有一条记录，即原点到自己的最小
距离为0，源点到其他所有点的最小距离都为正无穷大
-
从距离表中拿出没拿过记录里的最小记录，通过这个点发出的边，更新源点到各个
点的最小距离表，不断重复这一步
-
源点到所有的点记录如果都被拿过一遍，过程停止，最小距离表得到了
其实就是一张表，各个点和源点到各个点的最小距离。
从源点开始，遍历edges所有边，如果没有到过这个点，直接放，距离为之前的路的最小距离distance + 当前这条路距离。
如果已经到过，有路径，就判断是否是最小距离，然后更新。
然后跳到下一个点，再去循环下一个点的边。已经求过距离的点，存在selectNodes中，以后再也碰。
方法1：
public static HashMap<Node, Integer> dijkstra1(Node from) {
//从head出发到所有点的距离
//key：从head出发到达key
//value：从head出发到达key的最小距离
//如果在表中。没有T的记录，含义是从head出发到T这个点的距离为正无穷
HashMap<Node, Integer> distanceMap = new HashMap<>();
distanceMap.put(from, 0);
// 已经求过距离的点，存在selectNodes中，以后再也碰
HashSet<Node> selectedNodes = new HashSet<>();
//从map中找到没有锁过，且最小距离的节点
Node minNode = getMinDistanceAndUnselectedNode(distanceMap, selectedNodes);
while (minNode != null) {
// 原始点 -> minNode(跳转点) 最小距离distance
int distance = distanceMap.get(minNode);
for (Edge edge : minNode.edges) {
Node toNode = edge.to;
//没有到过这个点，放入map，距离为之前的路的最小距离distance + 当前这条路距离
if (!distanceMap.containsKey(toNode)) {
distanceMap.put(toNode, distance + edge.weight);
}
//已经到过，有路径，判断是否是最小距离，然后更新
else {
distanceMap.put(edge.to, Math.min(distanceMap.get(toNode), distance + edge.weight));
}
}
selectedNodes.add(minNode);
minNode = getMinDistanceAndUnselectedNode(distanceMap, selectedNodes);
}
return distanceMap;
}
/**
*
* 遍历从map中找到没有锁过，且最小的距离的节点
* @author: Li
* @dateTime: 2022/8/8 14:13
*/
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;
}
上面的方法，其实不是最优的，因为再选择的时候，一直在遍历。而我们可以对这个过程进行优化，用堆。Java提供的堆是不能完成的，所以我们需要针对其，自己实现一个堆。
方法2:
public static class NodeRecord {
public Node node;
public int distance;
public NodeRecord(Node node, int distance) {
this.node = node;
this.distance = distance;
}
}
public static class NodeHeap {
private Node[] nodes; // 实际的堆结构
// key 某一个node， value 上面堆中的位置
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++);
}
}
public NodeRecord pop() {
NodeRecord nodeRecord = new NodeRecord(nodes[0], distanceMap.get(nodes[0]));
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;
}
}
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算法
// 从head出发，所有head能到达的节点，生成到达每个节点的最小路径记录并返回
public static HashMap<Node, Integer> dijkstra2(Node head, int size) {
NodeHeap nodeHeap = new NodeHeap(size);
nodeHeap.addOrUpdateOrIgnore(head, 0);
HashMap<Node, Integer> result = new HashMap<>();
while (!nodeHeap.isEmpty()) {
NodeRecord record = nodeHeap.pop();
Node cur = record.node;
int distance = record.distance;
for (Edge edge : cur.edges) {
nodeHeap.addOrUpdateOrIgnore(edge.to, edge.weight + distance);
}
result.put(cur, distance);
}
return result;
}
10-并查集结构和图相关的算法
https://blog.isle.ink//archives/bing-cha-ji-jie-gou-he-tu-xiang-guan-de-suan-fa