13、算法与数据结构 - 实战：图
数据结构
点
/**
* 图中的点
* Created by huangjunyi on 2022/8/30.
*/
public class Node {
//点的值
public int value;
//入度
public int in;
//出度
public int out;
//从该节点出发，能找到的邻居节点集合
public List<Node> nexts;
//从该节点出发，能到的邻居节点的边的集合
public List<Edge> edges;
public Node(int value) {
this.value = value;
this.in = 0;
this.out = 0;
this.nexts = new ArrayList<>();
this.edges = new ArrayList<>();
}
}
边
/**
* 图中的边
* Created by huangjunyi on 2022/8/30.
*/
public class Edge {
//边的权重
public int value;
//边的起始点
public Node from;
//边的终点
public Node to;
public Edge(int value, Node from, Node to) {
this.value = value;
this.from = from;
this.to = to;
}
}
图
/**
* 图结构
* Created by huangjunyi on 2022/8/30.
*/
public class Graph {
//图中所有的点
public Map<Integer, Node> nodes;
//图中所有的边
public Set<Edge> edges;
public Graph() {
this.nodes = new HashMap<>();
this.edges = new HashSet<>();
}
}
给定一个样本集，初始化一个图结构
/**
* 给定一个样本集，初始化一个图结构
* Created by huangjunyi on 2022/8/30.
*/
public class Graph01 {
public static Graph create(int[][] samples) {
Graph graph = new Graph();
for (int[] sample : samples) {
int value = sample[0]; //边的权重
int from = sample[1]; //边的起始点的值
int to = sample[2]; //边的终点的值
//如果图中不包含该点，则添加
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 edge = new Edge(value, fromNode, toNode);
//把终点添加到起始点的邻居节点集合中
fromNode.nexts.add(toNode);
//起始点的出度+1
fromNode.out++;
//把边放入起始点
fromNode.edges.add(edge);
//终点入度+1
toNode.in++;
//把边放入图中
graph.edges.add(edge);
}
return graph;
}
}
图的广度优先遍历
- 队列 + set
- 队列用于放入待遍历的节点
- set记录一个节点是否遍历过，遍历过的节点不再入队列
- 一直遍历，直到队列为空
/**
* 图的广度优先遍历
* Created by huangjunyi on 2022/8/30.
*/
public class Graph02 {
public static void bfs(Node node) {
if (node == null) {
return;
}
// 队列用于放入待遍历的节点
Queue<Node> queue = new LinkedList<>();
// set记录一个节点是否入过队列，是则不再入队列
Set<Node> set = new HashSet<>();
// 头节点入队列
queue.offer(node);
// 记录头已经入过队列
set.add(node);
// 一直遍历，直到队列为空
while (!queue.isEmpty()) {
// 从队列弹出节点，打印
Node curr;
System.out.println((curr = queue.poll()).value);
// 看该节点是否有没有入过队列的节点，有则入队列，等待遍历
for (Node next : curr.nexts) {
if (!set.contains(next)) {
queue.offer(next);
set.add(next);
}
}
}
}
}
图的深度优先遍历
- 栈 + set
- 栈用于存储遍历过的节点，沿着节点路径一直往里遍历，遍历到的节点放入栈中
- set记录遍历过的节点，一个节点遍历过，就不在入栈
- 如果走到尽头了，从栈中弹出栈顶节点，继续遍历弹出节点的其他没有遍历过的邻居
- 一直遍历直到栈为空
/**
* 图的深度优先遍历
* Created by huangjunyi on 2022/8/30.
*/
public class Graph03 {
public static void dfs(Node node) {
if (node == null) {
return;
}
// 栈用于存储遍历过的节点，沿着节点路径一直往里遍历，遍历到的节点放入栈中
Deque<Node> stack = new LinkedList<>();
// set记录遍历过的节点，一个节点遍历过，就不在入栈
Set<Node> set = new HashSet<>();
// 入栈前先打印，表示已经遍历过
System.out.println(node.value);
// 头节点入栈
stack.push(node);
// 记录头节点遍历过
set.add(node);
// 一直遍历直到栈为空
while (!stack.isEmpty()) {
// 从栈中弹出栈顶节点，遍历弹出节点的邻居，把没有遍历过的邻居节点入栈
Node curr = stack.pop();
for (Node next : curr.nexts) {
if (!set.contains(next)) {
// 遍历到没有访问过的邻居，打印该邻居
System.out.println(next.value);
// 记录该邻居已经访问过
set.add(next);
// 当前节点和邻居节点入栈，返回，进入下一轮循环
stack.push(curr);
stack.push(next);
break;
}
}
}
}
}
拓扑排序
/**
* 拓扑排序
* 拓扑排序的图是有向无环图图
* Created by huangjunyi on 2022/8/30.
*/
public class Graph04 {
public static List<Node> sort(Graph graph) {
// 入度表 节点=>剩余入度
Map<Node, Integer> inMap = new HashMap<>();
// 剩余入度为0的节点，会入这个队列
Queue<Node> zeroInQueue = new LinkedList<>();
// 初始化zeroInQueue，入度为0的点入队列
for (Node node : graph.nodes.values()) {
inMap.put(node, node.in);
if (node.in == 0) {
zeroInQueue.offer(node);
}
}
List<Node> result = new ArrayList<>();
while (!zeroInQueue.isEmpty()) {
// 弹出zeroInQueue的一个节点，放入结果
Node curr = zeroInQueue.poll();
result.add(curr);
// 把当前节点的邻居节点的入度-1
for (Node next : curr.nexts) {
inMap.put(next, inMap.get(next) - 1);
// 如果节点入度减到0，入队列
if (inMap.get(next) == 0) {
zeroInQueue.offer(next);
}
}
}
return result;
}
}
利用kruskal算法生成最小生成树
kruskal算法是在无向图中求最小生成树的算法
最小生成树：在不破坏连通性的情况下，返回图中权重最小边的集合
1、 所有边根据权重从小到大排序；
2、 按顺序遍历每条边，没有形成环，就选这条边；
检查是否形成环：
1、 使用并查集，一条边的两个节点不在一个集合中的，则可以选；
2、 选了之后该边的两个节点所在的集合就要合并；
/**
* 最小生成树
* 在不破坏连通性的情况下，返回图中权重最小边的集合
* 利用kruskal算法生成最小生成树
* Created by huangjunyi on 2022/8/30.
*/
public class Graph05 {
static class UnionSet<T> {
/**
* 存放子Node到父Node的映射
*/
private Map<Node, Node> parentMap = new HashMap<>();
/**
* 存放根Node与集合大小的映射
*/
private Map<Node, Integer> sizeMap = new HashMap<>();
public UnionSet(Collection<Node> values) {
for (Node node : values) {
parentMap.put(node, node);
sizeMap.put(node, 1);
}
}
public Node findRootNode(Node node) {
Stack<Node> stack = new Stack<>();
//一直往上寻找，找到找到根Node，沿途的Node记录到stack
while (parentMap.get(node) != node) {
stack.push(node);
node = parentMap.get(node);
}
//修改沿途的Node的父节点，使得下次findRootNode的代价更小
while (!stack.isEmpty()) parentMap.put(stack.pop(), node);
return node;
}
public boolean isSameSet(Node a, Node b) {
//a对应的Node，和b对应的Node，同时找到根Node，如果是同一个根Node，代表a和b在一个集合中
return findRootNode(a) == findRootNode(b);
}
public void union(Node a, Node b) {
//a对应的Node，和b对应的Node，同时往上找到根Node
Node rootNodeA = findRootNode(a);
Node rootNodeB = findRootNode(b);
//在同一个集合中，不用合并
if (rootNodeA == rootNodeB) return;
int sizeA = sizeMap.get(rootNodeA);
int sizeB = sizeMap.get(rootNodeB);
//数量小的集合的根Node的父Node指向数量大的集合的跟Node
//然后更新sizeMap信息，sizeMap只需要存储根Node与集合大小的映射
if (sizeA <= sizeB) {
parentMap.put(rootNodeA, rootNodeB);
sizeMap.put(rootNodeB, sizeA + sizeB);
sizeMap.remove(rootNodeA);
} else {
parentMap.put(rootNodeB, rootNodeA);
sizeMap.put(rootNodeA, sizeA + sizeB);
sizeMap.remove(rootNodeB);
}
}
public int countSet() {
return sizeMap.size();
}
}
public static Set<Edge> kruskalMST(Graph graph) {
//根据图中的点构建一个并查集
UnionSet unionSet = new UnionSet(graph.nodes.values());
//对所有的边进行排序，权重小的牌前面
PriorityQueue<Edge> queue = new PriorityQueue<>(Comparator.comparingInt(o -> o.value));
queue.addAll(graph.edges);
//每次从堆中取出一条边，如果两个点不在一个集合里面，保留这条边到结果集中，并把两个点在并查集中合并
Set<Edge> result = new HashSet<>();
while (!queue.isEmpty()) {
Edge e = queue.poll();
if (!unionSet.isSameSet(e.from, e.to)) {
result.add(e);
unionSet.union(e.from, e.to);
}
}
return result;
}
}
Prim算法求最小生成树
- 从一个点出发，取与该点相邻的权重最小的边，然后把边加到结果集中
- 然后取该边对端的点，继续取权重最小的边，放入结果集
- 访问过的点和边要记录下来，如果取出的权重最小的边已经被记录访问过，则丢弃
- 如果取出的边对端的点已经被访问过，该边也丢弃
- 周而复始，直到访问完所有的边
/**
* Prim算法求最小生成树
* 从一个点出发，取与该点相邻的权重最小的边，然后把边加到结果集中
* 然后取该边对端的点，继续取权重最小的边，放入结果集
* 访问过的点和边要记录下来，如果取出的权重最小的边已经被记录访问过，则丢弃
* 如果取出的边对端的点已经被访问过，该边也丢弃
* 周而复始，直到访问完所有的边
* Created by huangjunyi on 2022/8/31.
*/
public class Graph06 {
public static Set<Edge> primMST(Graph graph) {
// 记录访问过的节点
Set<Node> visitedNodes = new HashSet<>();
// 记录访问过的边
Set<Edge> visitedEdges = new HashSet<>();
// 最小生成树的边集
Set<Edge> result = new HashSet<>();
// 解锁了的边会放到小根堆中，按权重从小到大排序
PriorityQueue<Edge> queue = new PriorityQueue<>(Comparator.comparingInt(o -> o.value));
//图有可能是森林（多个互相不连通的图），所以通过for循环遍历
for (Node node : graph.nodes.values()) {
if (!visitedNodes.contains(node)) {
// 如果一个节点没有访问过，访问，并看看边是否没有访问过，如果没有访问过，解锁
visitedNodes.add(node);
for (Edge edge : node.edges) {
if (!visitedEdges.contains(edge)) {
visitedEdges.add(edge);
queue.offer(edge);
}
}
// 遍历，直到小根堆为空，这一个子图就遍历完了
while (!queue.isEmpty()) {
// 小根堆弹出已解锁的权值最小的边
Edge currEdge = queue.poll();
// 访问to节点
Node toNode = currEdge.to;
// 如果to节点没有访问过，访问，并看看边是否没有访问过，如果没有访问过，解锁
if (!visitedNodes.contains(toNode)) {
visitedNodes.add(toNode);
result.add(currEdge);
for (Edge edge : toNode.edges) {
if (!visitedEdges.contains(edge)) {
visitedEdges.add(edge);
queue.offer(edge);
}
}
}
}
}
}
return result;
}
}
Dijkstra算法求一个起始点到所有点的最短距离
Dijkstra算法用于在有向无负权重的图（可以有环）中，算出某一个节点到图中所有节点的距离，返回一张距离表
1、 定义一个堆，并且该堆可以调整元素的value（到原点的距离），然后重写排序；
2、 一开始先放入原点到堆中，并且距离是0；
3、 循环判断堆是否为空，不为空则弹出一个节点并进行堆调整，此时该节点到原点的距离就是最短距离，放入结果集中；
4、 取出该点的所有邻接点，遍历所有邻接点，并判断邻接点是否未进入过堆，是则直接放入堆中然后进行堆调整；如果该节点在堆中但是未弹出，则判断当前算出的距离（当前弹出的node与原点的距离+该邻接点与当前弹出结点间的边的权重）是否更小，是则更新该节点在堆中记录的value（与原点的距离）并进行堆调整；如果以上两个条件不满足，表示该节点曾经进入过堆并且已经弹出，忽略该节点；
5、 直到堆为空，退出循环；
/**
* Dijkstra算法求一个起始点到所有点的最短距离
* Created by huangjunyi on 2022/8/31.
*/
public class Graph07 {
private static class NodeHeap {
private Node[] heap;
private Map<Node, Integer> distanceMap;
private Map<Node, Integer> indexMap;
private int size;
public NodeHeap(int size) {
this.size = size;
this.heap = new Node[size];
this.distanceMap = new HashMap<>();
this.indexMap = new HashMap<>();
}
/**
* 往堆中放入节点，如果存在则更新，如果已经已经出队则忽略
* @param node
* @param distance
*/
public void push(Node node, int distance) {
if (!indexMap.containsKey(node)) {
//如果indexMap中的key不包含该node，则表示该node从未进过堆，直接添加
heap[size] = node;
distanceMap.put(node, distance);
indexMap.put(node, size);
floatUp(size++);
} else if (indexMap.get(node) != -1 && distance < distanceMap.get(node)) {
//如果indexMap中的key包含该node，且value不等于-1，则表示该node在堆中未弹出
//如果该node与起始点新的距离比distanceMap中记录的小，则更新distanceMap同时进行堆调整
distanceMap.put(node, distance);
floatUp(indexMap.get(node));
}
}
/**
* 弹出堆顶节点，返回其与起始点的最小距离
* @return
*/
public PopNode pop() {
PopNode popNode = new PopNode(heap[0], distanceMap.get(heap[0]));
distanceMap.remove(heap[0]);
indexMap.put(heap[0], -1);
swap(0, size - 1);
heap[--size] = null;
sink(0);
return popNode;
}
/**
* 堆向下调整
* @param i
*/
private void sink(int i) {
int left = i * 2 + 1;
while (left < size) {
int smallChild = distanceMap.get(heap[left]) < distanceMap.get(heap[left + 1]) ? left : left + 1;
if (distanceMap.get(heap[smallChild]) < distanceMap.get(heap[i])) {
swap(smallChild, i);
i = smallChild;
left = i * 2 + 1;
} else {
break;
}
}
}
/**
* 堆向上调整
* @param i
*/
private void floatUp(int i) {
while (i > 0) {
if (distanceMap.get(heap[i]) < distanceMap.get(heap[(i - 1) / 2])) {
swap(i, (i - 1) / 2);
i = (i - 1) / 2;
} else {
break;
}
}
}
private void swap(int i, int j) {
indexMap.put(heap[i], j);
indexMap.put(heap[j], i);
Node temp = heap[i];
heap[i] = heap[j];
heap[j] = temp;
}
public boolean isEmpty() {
return size == 0;
}
}
private static class PopNode {
private Node node;
private int distance;
public PopNode(Node node, int distance) {
this.node = node;
this.distance = distance;
}
}
public static Map<Node, Integer> dijkstra(Node head, int size) {
//创建一个堆结构
NodeHeap nodeHeap = new NodeHeap(size);
/**
* push方法三种处理：
* 1、如果该节点未进入过堆，则直接添加，并进行堆调整
* 2、如果该节点进入过堆，但是未弹出，如果与起始点新的距离更短，则更新距离并调整堆
* 3、如果该节点进入过堆，但是已经弹出，直接忽略
*/
nodeHeap.push(head, 0);
Map<Node, Integer> result = new HashMap<>();
//循环直到堆为空
while (!nodeHeap.isEmpty()) {
//弹出的就是最终该节点与起始点的最短距离
PopNode popNode = nodeHeap.pop();
result.put(popNode.node, popNode.distance);
//遍历该节点的邻接边，调用push方法尝试放入或更新对端的点
for (Edge edge : popNode.node.edges) {
nodeHeap.push(edge.to, popNode.distance + edge.value);
}
}
return result;
}
}
附加-Dinic算法解决最大网络流问题
给定一个有向图，边代表水管，而边的权重代表水管最大的承载水量
然后再给定图中的一个出发点和目标点
问从出发点到目标点的最大灌水量
比如，这样一副有向图，出发点是a，目标点是d，最大灌水量就是100+30=130
红色的水管就是瓶颈
解法一：深度优先遍历取每条路线的最小值，然后走过的路都减去流过的水量，最后累加每条路线得出的最小值？
看似可以，但是会得到错误解
比如 这样一副有向图，出发点是a，目标点是d
如果第一次深度优先遍历，走的路线是这样
然后得出该路线最小值是50，然后沿途都扣减50
此时发现无路可走了，返回了一个错误答案50
那么，在走过的路上，补一条反向边，反向边权重就是正向边扣减调的承载水量
那么就不会因为路线选的不好，导致无路可走的情况
第二次遍历的时候，a到d还是有路可走的，并且最后得出正确答案
这就是Dinic算法的其中一个优化
Dinic算法第二个优化，建立高度
宽度优先遍历，得到高度信息 a高度为0，b/c高度为1，d的高度为2，有一个数组记录[0,1,1,2]
这样就可以优化深度优先遍历的常数时间，相同层的路径不要走，这样就规避了b到c的路径
还有一个优化，就是解决这种情况：
一条路径走过一个点，流经某个点，而这个点又流经某些边，去往下一个点
拿这条路径返回到上层节点，继续往下尝试其他的支路，又走到了这个点，那么之前走过的边，如果载水量耗尽，是不能再走的，因此每次都要判断一下载水量再走
那为了优化这种判断，搞一个cur数组，cur[s]表示s这个点，从cur[s]这条边开始，cur[s]往下的都是别的支路占用的，不能再走了
代码：
/**
* Dinic算法解决最大网络流问题
* Created by huangjunyi on 2022/12/11.
*/
public class _18DinicAlgorithm {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StreamTokenizer in = new StreamTokenizer(br);
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
while (in.nextToken() != StreamTokenizer.TT_EOF) {
int cases = (int) in.nval;
for (int i = 1; i <= cases; i++) {
in.nextToken();
int n = (int) in.nval;
in.nextToken();
int s = (int) in.nval;
in.nextToken();
int t = (int) in.nval;
in.nextToken();
int m = (int) in.nval;
Dinic dinic = new Dinic(n);
for (int j = 0; j < m; j++) {
in.nextToken();
int from = (int) in.nval;
in.nextToken();
int to = (int) in.nval;
in.nextToken();
int weight = (int) in.nval;
dinic.addEdge(from, to, weight);
dinic.addEdge(to, from, weight);
}
int ans = dinic.maxFlow(s, t);
out.println("Case " + i + ": " + ans);
out.flush();
}
}
}
/**
* 边
*/
public static class Edge {
public int from; // 从哪
public int to; // 到哪
public int available; // 权重（承载水量）
public Edge(int a, int b, int c) {
from = a;
to = b;
available = c;
}
}
public static class Dinic {
private int N; // 边数
private ArrayList<ArrayList<Integer>> nexts; // 城市编号 => [能走的边的边号]
private ArrayList<Edge> edges; // 边号 => 边
private int[] depth; // 高度数组
private int[] cur; // cur数组，边号 => 从哪条边开始尝试，比如cur[s]=2，表示s这个点还能走nexts.get(s)中大于等于2的边，小于的是别的支路走过的，不能重复往里灌水
public Dinic(int nums) {
N = nums + 1;
nexts = new ArrayList<>();
for (int i = 0; i <= N; i++) {
nexts.add(new ArrayList<>());
}
edges = new ArrayList<>();
depth = new int[N];
cur = new int[N];
}
public void addEdge(int u, int v, int r) {
int m = edges.size();
// 加正向边
edges.add(new Edge(u, v, r));
nexts.get(u).add(m);
// 加反向边
edges.add(new Edge(v, u, 0));
nexts.get(v).add(m + 1);
}
/**
* 算法主流程
* @param s 起始点
* @param t 目标点
* @return 最大灌水量
*/
public int maxFlow(int s, int t) {
int flow = 0;
while (bfs(s, t)) {
// s -> t，还有路能走？
Arrays.fill(cur, 0); // 还原cur数组
flow += dfs(s, t, Integer.MAX_VALUE); // 走 =>
Arrays.fill(depth, 0); // 还原高度数组
}
return flow;
}
/**
* 宽度优先遍历，建立高度数组
*/
private boolean bfs(int s, int t) {
LinkedList<Integer> queue = new LinkedList<>();
queue.addFirst(s);
boolean[] visited = new boolean[N];
visited[s] = true;
while (!queue.isEmpty()) {
int u = queue.pollLast();
for (int i = 0; i < nexts.get(u).size(); i++) {
Edge e = edges.get(nexts.get(u).get(i));
int v = e.to;
if (!visited[v] && e.available > 0) {
visited[v] = true;
// 子节点高度 = 父节点高度 + 1
depth[v] = depth[u] + 1;
if (v == t) {
break;
}
queue.addFirst(v);
}
}
}
return visited[t];
}
/**
* 当前来到了s点，s为可变参数，最终目标是t，t固定参数，r收到的任务
* 收集到的流，作为结果返回，ans <= r
* @param s 当前来到了s点
* @param t 最终目标是t
* @param r 收到的任务
* @return 收集到的流
*/
private int dfs(int s, int t, int r) {
if (s == t || r == 0) {
return r;
}
int f = 0;
int flow = 0;
// s点从哪条边开始试 -> cur[s]
for (; cur[s] < nexts.get(s).size(); cur[s]++) {
// cur[s]++，别的支路也走到当前节点，就接着往下尝试
int ei = nexts.get(s).get(cur[s]);
Edge e = edges.get(ei); // 正向边
Edge o = edges.get(ei ^ 1); // 方向边
if (depth[e.to] == depth[s] + 1 // 高度更大的才走
&& (f = dfs(e.to, t, Math.min(e.available, r))) != 0) {
e.available -= f; // 正向边扣减
o.available += f; // 反向边增加
flow += f; // 收集流
r -= f; // 要完成的任务扣减
if (r <= 0) {
// 任务都完成了，返回
break;
}
}
}
return flow;
}
}
}