图论理论学习笔记整理

目录

• 零、图的存储
• • 0.1 邻接矩阵
  • 0.2 邻接表
  • 0.3 边集数组
  • 0.4 链式前向星
• 一、并查集
• • 1.1 并查集的初始化
  • 1.2 QuickFind
  • 1.3 QuickUnion
  • 1.4 按秩合并（基于QuickUnion改Union
  • 1.5 路径压缩(基于QuickUnion改find）
  • 1.6 路径压缩+按秩合并（代码模板）
  • LeetCode 547.省份数量
• 二、深度优先搜索 栈
• • 2.1 遍历所有顶点
  • 2.2 遍历两点之间所有路径
  • [LeetCode 797.所有可能的路径](https://leetcode-cn.com/problems/all-paths-from-source-to-target/) DFS实现
• 三、广度优先搜索 队列
• • 3.1 遍历所有顶点
  • 3.2 遍历两点之间所有路径（可顺便求两点之间最短路径 限权重相等且均为正数）
  • [LeetCode 797.所有可能的路径](https://leetcode-cn.com/problems/all-paths-from-source-to-target/) BFS实现
• 四、最小生成树
• • 4.1 理论基石——切分定律
  • 4.2 Kruskal算法
  • 4.3 Prim算法
  • LeetCode 1584. 连接所有点的最小费用
  • • Kruskal
    • Prim
• 五、单源最短路径
• • 5.1 Dijkstra算法
  • [LeetCode 743.网络延迟时间](https://leetcode-cn.com/problems/network-delay-time/)
  • • Dijkstra + 堆 + 邻接矩阵
  • 5.2 Bellman-Ford算法（可以记录经过k条边）
  • • Bellman-Ford 算法如何检测「负权环」
  • [LeetCode 787.K 站中转内最便宜的航班](https://leetcode-cn.com/problems/cheapest-flights-within-k-stops/)
  • 5.3 SPFA算法 （不能记录经过k条边）
  • • 优缺点比较
• 六、拓扑排序
• • [LeetCode 210. 课程表 II](https://leetcode-cn.com/problems/course-schedule-ii/)

零、图的存储

0.1 邻接矩阵

0.2 邻接表

0.3 边集数组

0.4 链式前向星

一、并查集

在「并查集」数据结构中，其中心思想是将所有连接的顶点，无论是直接连接还是间接连接，都将他们指向同一个父节点或者根节点。此时，如果要判断两个顶点是否具有连通性，只要判断它们的根节点是否为同一个节点即可。

1.1 并查集的初始化

一个root数组，下标i表示为节点i，值为其父节点（当前集合的代表节点）
Find(x)方法用来返回当前元素所在集合的代表节点
union(x,y)将两个元素所在的集合union起来
connected方法来调用两个节点的find方法，判断是否相等来判断两个节点是否在同一个集合内

这些也是并查集这个数据结构的灵魂所在

1.2 QuickFind

root数组直接记录根节点，union时间复杂度为O(N)
union需要把每个指向Y的节点变为指向X
（这里顺序无关，也可以把指向X的指向Y，因为这里还没有引入秩的概念）

public int find(int x) {return root[x];
}
public void union(int x, int y) {int rootX = find(x);int rootY = find(y);if (rootX != rootY) {for (int i = 0; i < root.length; i++) {if (root[i] == rootY) {root[i] = rootX;}}}
};

1.3 QuickUnion

root数组记录父节点
因为记录父节点，所以find的时候需要去找其根节点(代表节点)，时间复杂度为O(H)
union的时间复杂度为：O(1)

public int find(int x) {while (x != root[x]) {x = root[x];}return x;
}public void union(int x, int y) {int rootX = find(x);int rootY = find(y);if (rootX != rootY) {root[rootY] = rootX;}
};

1.4 按秩合并（基于QuickUnion改Union

root数组记录父节点
rank数组记录每个元素的秩

这里的「秩」指的是每个顶点所处的高度。我们每次 union 两个顶点的时候，选择根节点的时候不是随机的选择某个顶点的根节点，而是按照秩(子树的深度) 秩小的拼到树大的地方去，这样就不会加深度了

public int find(int x) {while (x != root[x]) {x = root[x];}return x;}public void union(int x, int y) {int rootX = find(x);int rootY = find(y);if (rootX != rootY) {if (rank[rootX] > rank[rootY]) {root[rootY] = rootX;} else if (rank[rootX] < rank[rootY]) {root[rootX] = rootY;} else {root[rootY] = rootX;rank[rootX] += 1;}}
}

1.5 路径压缩(基于QuickUnion改find）

优化的思想：
因为root数组记录父节点，所以我们在调用find方法找到其根节点的时候顺便赋值给root数组，这样第二次find路径上任一节点就能达到QuickFind的效果啦

public int find(int x) {if (x == root[x]) {return x;}return root[x] = find(root[x]);
}public void union(int x, int y) {int rootX = find(x);int rootY = find(y);if (rootX != rootY) {root[rootY] = rootX;}
};

1.6 路径压缩+按秩合并（代码模板）

就是将路径压缩和按秩合并的代码融合，达到

class RankQuickunionfind {private int[] root;private int[] rank;public RankQuickunionfind(int size) {root = new int[size];rank = new int[size];for (int i = 0; i < root.length; i++) {root[i] = i;}for (int i = 0; i < rank.length; i++) {rank[i] = 1;}}//修改find，基于路径压缩，用递归public int find(int num) {if (num == root[num]) {return num;}root[num] = find(root[num]);return root[num];}public void union(int x, int y) {int rootx = find(x);int rooty = find(y);//改善union函数，根据秩的大小来决定谁拼接谁if (rootx != rooty) {if (rank[rootx] > rank[rooty]) {root[rooty] = rootx;} else if (rank[rootx] < rank[rooty]) {root[rootx] = rooty;} else {root[rooty] = rootx;rank[rootx] += 1;}}}public boolean connected(int x, int y) {return find(x) == find(y);}
}

LeetCode 547.省份数量

二、深度优先搜索 栈

在搜索无向图的时候，我们需要建立一个visited数组来判断当前元素是否已经被访问过了。

2.1 遍历所有顶点

栈中存放节点，配合visited数组，一条路死磕到底

2.2 遍历两点之间所有路径

栈中存放path，每次取出栈中path并把path中最后一个元素存的所有边加入栈中。
回退的时候要把深搜的visited改回false
如果取出的path.get(path.size()-1)正好是目标节点，那么加入res

最短路径：res中最短的路

LeetCode 797.所有可能的路径 DFS实现

class Solution {//因为是有向图，所以不需要visited数组public List<List<Integer>> allPathsSourceTarget(int[][] graph) {ArrayList<List<Integer>> res  = new ArrayList<List<Integer>>();if(graph.length<1){return res;}dfs(graph,0,new ArrayList<Integer>(),res);return res;}public void dfs(int[][] graph,int node,ArrayList<Integer>path,ArrayList<List<Integer>>paths){path.add(node);if(node==graph.length-1){paths.add(new ArrayList(path));return;}//得到当前节点所连接的节点int[] connected = graph[node];for(int nodes : connected){dfs(graph,nodes,path,paths);path.remove(path.size()-1);}}
}

三、广度优先搜索 队列

在搜索无向图的时候，我们需要建立一个visited数组来判断当前元素是否已经被访问过了。

3.1 遍历所有顶点

队列中存放节点，配合visited数组，层层死磕到底
队列中取出元素，判断是否visited，并将其邻居节点加入队列中

3.2 遍历两点之间所有路径（可顺便求两点之间最短路径 限权重相等且均为正数）

「广度优先遍历」算法只能解决「无权图」的「最短路径」问题；但现实生活中，我们往往将「最短路径」应用在「加权图」
和dfs同理，将从队列中取出的path的末尾顶点连接的所有边加入队列中，并将末尾顶点标记为visited

最短路径求法：第一次遇到末尾顶点为目标顶点时的path

LeetCode 797.所有可能的路径 BFS实现

class Solution {public List<List<Integer>> allPathsSourceTarget(int[][] graph) {ArrayList<List<Integer>> res = new ArrayList<>();if (graph == null || graph.length == 0) return res;//制作bfs的队列LinkedList<List<Integer>> queue = new LinkedList<>();ArrayList<Integer> path = new ArrayList<>();path.add(0);queue.offer(path);while (queue.size() > 0) {List<Integer> poll = queue.poll();Integer node = poll.get(poll.size() - 1);for (int i : graph[node]) {ArrayList<Integer> newpoll = new ArrayList<>(poll);newpoll.add(i);if (i == graph.length - 1) {res.add(newpoll);} else {queue.offer(newpoll);}}}return res;}
}

四、最小生成树

4.1 理论基石——切分定律

在一幅连通加权无向图中，给定任意的切分，如果有一条横切边的权值严格小于所有其他横切边，则这条边必然属于图的最小生成树中的一条边。

4.2 Kruskal算法

「Kruskal 算法」是求解「加权无向图」的「最小生成树」的一种算法。
通过增加边数将森林合并成树
将所有边加入优先队列，取出最小边并且用并查集判断这个最小边不会构成环时，加入结果中，直到加入了n-1条边（让N个顶点连接起来至少要N-1条边）

4.3 Prim算法

「 Prim算法」是求解「加权无向图」的「最小生成树」的另一种算法 增加顶点
让一棵小树长大
Visited数组标记点是否已访问，将点连接的所有边加入优先队列

LeetCode 1584. 连接所有点的最小费用

Kruskal

class Solution {public int minCostConnectPoints(int[][] points) {PriorityQueue<Edge> pq = new PriorityQueue<>((x, y) -> x.cost - y.cost);UnionFind uf = new UnionFind(points.length);for (int i = 0; i < points.length; i++) {for (int j = i + 1; j < points.length; j++) {int[] pointi = points[i];int[] pointj = points[j];int cost = Math.abs(pointi[0] - pointj[0]) + Math.abs(pointi[1] - pointj[1]);pq.add(new Edge(cost, i, j));}}int cost = 0;int n = points.length - 1;while (!pq.isEmpty() & n > 0) {Edge e = pq.poll();if (!uf.isConnected(e.point1, e.point2)) {uf.union(e.point1, e.point2);n--;cost += e.cost;}}return cost;}}class Edge {public int cost;public int point1;public int point2;public Edge(int cost, int point1, int point2) {this.cost = cost;this.point1 = point1;this.point2 = point2;}
}//基于路径压缩和按秩合并的 并查集
class UnionFind {private int[] root;private int[] rank;public UnionFind(int size) {root = new int[size];rank = new int[size];for (int i = 0; i < size; i++) {root[i] = i;rank[i] = 1;}}//找到当前节点所在集合的代表节点public int find(int x) {if (x == root[x]) {return root[x];}return root[x] = find(root[x]);}public void union(int x, int y) {int rootx = find(x);int rooty = find(y);if (rank[rootx] > rank[rooty]) {root[rooty] = rootx;} else if (rank[rootx] < rank[rooty]) {root[rootx] = rooty;} else {root[rooty] = rootx;rank[rootx] += 1;}}public boolean isConnected(int x, int y) {return find(x) == find(y);}}

Prim

class Solution {public int minCostConnectPoints(int[][] points) {//存储当前节点是否访问过了boolean[] visited = new boolean[points.length];//用来存储最短花费的边PriorityQueue<Edge> pq = new PriorityQueue<>((x, y) -> x.cost - y.cost);//Prim算法讲究通过顶点增加visited[0] = true;for (int i = 0; i < points.length; i++) {if (visited[i]) continue;int cost = Math.abs(points[0][1] - points[i][1]) + Math.abs(points[0][0] - points[i][0]);pq.add(new Edge(0, i, cost));}int n = points.length - 1;int res = 0;while (!pq.isEmpty() && n > 0) {Edge e = pq.poll();if (!visited[e.node2]) {visited[e.node2] = true;res += e.cost;n--;for (int i = 0; i < points.length; i++) {if (visited[i]) continue;int cost = Math.abs(points[e.node2][1] - points[i][1]) + Math.abs(points[e.node2][0] - points[i][0]);pq.add(new Edge(e.node2, i, cost));}}}return res;}class Edge {int node1;int node2;int cost;public Edge(int node1, int node2, int cost) {this.node1 = node1;this.node2 = node2;this.cost = cost;}}
}

五、单源最短路径

松弛操作：找到更短的距离并更新

5.1 Dijkstra算法

「Dijkstra 算法」只能解决加权有向图的权重为非负数的「单源最短路径」问题。

LeetCode 743.网络延迟时间

Dijkstra + 堆 + 邻接矩阵

class Solution {int _n, _k;int[][] w;int[] dist;boolean[] visited;static final int INF = 0x3f3f3f3f;public int networkDelayTime(int[][] times, int n, int k) {_n = n;_k = k;w = new int[_n + 1][_n + 1];dist = new int[_n + 1];visited = new boolean[_n + 1];//初始化边for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {w[i][j] = w[j][i] = i == j ? 0 : INF;}}//存图for (int i = 0; i < times.length; i++) {int u = times[i][0], v = times[i][1], c = times[i][2];w[u][v] = c;}dijkstraByheap();int max = 0;for (int i = 1; i <= _n; i++) {max = dist[i] > max ? dist[i] : max;}return max > INF/2 ? -1 : max;}public void dijkstraByheap(){Arrays.fill(visited, false);Arrays.fill(dist, INF);dist[_k]=0;PriorityQueue<int[]> queue = new PriorityQueue<>((x,y)->{return x[1]-y[1];});queue.add(new int[]{_k,0});while(!queue.isEmpty()){int[] shortest = queue.poll();if(visited[shortest[0]])continue;int index =shortest[0] ;//更新这个节点的所有节点for(int i=1;i<=_n;i++){if(dist[index]+w[index][i]<dist[i]) {dist[i] = dist[index] + w[index][i];queue.add(new int[]{i,dist[i]});}}}}
}

5.2 Bellman-Ford算法（可以记录经过k条边）

Bellman-Ford 算法」能解决加权有向图中包含权重为负数的「单源最短路径」问题。可以处理正权环的情况，但无法处理图中有负权环的情况，不过可以检测负权环。

基础定理：组成N个顶点两点之间最多要经过N-1条边

动态规划解决正权环问题【一切都是基于不是负权环，负权环也没法做了】：
求A到B之间经过1、2、3、4、5…到N-1条边的时候的最短路径

行：0到节点i
列：经历j条边（maxj = n-1)
格子：最短距离
递推公式：min(到达节点i的所以节点的j-1条边的最短路径+与节点i的权重,节点i的j-1条边的最短路径)

• Bellman-Ford 就是简化了动态规划的空间复杂度（两个数组 ）（其实就是滚动数组）

（还顺便说了一下值传递和引用传递关于动态规划拷贝问题，其实就是让我们用深拷贝）

Bellman-Ford 算法如何检测「负权环」

检测方法： 当小伙伴对所有边进行 N-1次松弛之后，再进行第 N 次松弛。

对每条边进行一次for循环，看看distances[u] + weight(u, v) < distances(v)

根据「Bellman-Ford 算法」，所有的边在 N-1次松弛之后，所有的距离必然是最短距离。如果在进行第 N次松弛后，对于一条边 edge(u, v)，还存在 distances[u] + weight(u, v) < distances(v) 的情况，也就是说，还存在更短的路径。此时就能说明「图」中存在「负权环」。

LeetCode 787.K 站中转内最便宜的航班

class Solution {public static final int INF = 0x3f3f3f3f;public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {if (src == dst) return 0;//dpint[] previous = new int[n];int[] current = new int[n];Arrays.fill(previous, INF);Arrays.fill(current, INF);previous[src] = 0;//最多中转K站for (int i = 0; i < k + 1; i++) {current[src]=0;for (int[] flight : flights) {//if(previous[flight[0]] current[flight[1]] = Math.min(current[flight[1]], previous[flight[0]] + flight[2]);}previous = current.clone();}return current[dst] == INF ? -1 : current[dst];}
}

5.3 SPFA算法 （不能记录经过k条边）

Bellman-Ford 的再优化时间复杂度，让循环不一定跑满n-1： （无法记录具体经过及条边）

【如果不能记录经过k条边，那么相对于Dijkstra，优势只有能跑负边】

**方法：**循环遍历整张图的所有的边，直到和上一次循环结果不变

具体使用：

1. 一维数组arr初始化全部为正无穷，i为节点i；
2. edge(x1,x2,cost)循环的时候，就更新min(arr[x1]+cost,arr[x2])

优缺点比较

上面Bellman - Ford 算法优化的缺陷：
选取边的顺序不同，需要运行的次数也不一定相同，我们选边遍历是随机的。

而

「SPFA 算法」主要是通过「队列」来维护我们接下来要遍历边的起点，而不是「Bellman Ford」算法中的任意还没有遍历过的边。每次只有当某个顶点的最短距离更新之后，并且该顶点不在「队列」中，我们就将该顶点加入到「队列」中。一直循环以上步骤，直到「队列」为空，我们就可以终止算法。此时，我们就可以得到「图」中其他顶点到给定顶点的最短距离了。

取出队头元素，遍历元素的所有边，如果dist[i]变更，那么把节点i当前加入队列，并标记i
（标记来防止元素在队列里重复出现，就是队列本来下一元素是2，但队头1让dist[2]变更了，标记就可以避免2的重复入队。

六、拓扑排序

应用场景：大学先修课顺序，适用于有向无环图。

如果是有环图那么拓扑排序就失效了，因为找不到入度为0的节点，即永远找不到哪个节点先开始。

Kahn算法的基本思想是：

1. 找到入度为0 的顶点找到并记录到队列或者栈中；
2. 移除找到的入度为0的顶点和对应的以该顶点为起点的边，并将被移除的顶点加入到list集合中，同时移除的顶点作为起点的边的终点的如度减去1；继续循环1的步骤，直至队列或者栈为空。
3. 此时list集合中的顶点的顺序输出就是拓扑排序的结果；如果list集合的元素数量少于顶点数量则说明该有向图存在环。

LeetCode 210. 课程表 II

class Solution {public int[] findOrder(int numCourses, int[][] prerequisites) {if(numCourses==1) return new int[]{0};//存储图ArrayList<ArrayList<Integer>> store = new ArrayList<>();//初始化图for(int i=0;i<numCourses;i++){store.add(new ArrayList<Integer>());}//定义入度数组int[] indegree=new int[numCourses];//存边和初始化入度数组for(int[] edge:prerequisites){store.get(edge[1]).add(edge[0]);indegree[edge[0]]++;}//返回的结果int[] res = new int[numCourses];int resindex = 0;//开始Kahn算法，按照入度为0的进入队列LinkedList<Integer> queue = new LinkedList<>();//初始化入度数组for(int i=0;i<indegree.length;i++){if(indegree[i]==0){queue.add(i);}}while(!queue.isEmpty()){int index = queue.poll();res[resindex++]=index;for(Integer i :store.get(index)){--indegree[i];if(indegree[i]==0){queue.add(i);}}}return resindex==numCourses?res:new int[]{};}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！