此文总结一下常见图论算法，代码可以为后续遇见类似题目提供参考：
1. 图的表示：
- 邻接矩阵：可通过创建数组得到
- 邻接表：我个人喜欢通过LinkedList<int[]>[] graph = new LinkedList[n];得到。
- Edge List：同样可以通过LinkedList<int[]>[] graph = new LinkedList[n];得到。
2. 图遍历：
DFS:
import java.util.LinkedList;
import java.util.List;
public class Graph {
List<Integer> res = new LinkedList<>();
boolean hasCycle = false;
public List<Integer> dfs(int[][] graph){
//已经给出graph就可以不构建，但有时会需要根据题目构建graph，可以按照具体情况构建
//假设这里的graph是有向图，并且0-indexed
int n = graph.length;
boolean[] visited = new boolean[n];
//onPath可以用来判断成环（对于有向图，必须要通过onPath，而无向图通过visited也行
boolean[] onPath = new boolean[n];
traverse(graph, 0, visited, onPath);
if(hasCycle) System.out.println("Has cycle!");
return res;
}
public void traverse(int[][] graph, int node, boolean[] visited, boolean[] onPath){
if(onPath[node]) hasCycle = true;
if(visited[node]) return;
//在外循环修改visited和onPath
visited[node] = true;
onPath[node] = true;
res.add(node);
for(int neighbor : graph[node]){
traverse(graph, neighbor, visited, onPath);
}
//结束函数之前要把onPath[node]置为false
onPath[node] = false;
}
public static void main(String[] args){
//构建一个有环有向图
int[][] graph1 = new int[][]{{1,2},{0,2},{0,1,3},{2,4},{3}};
//构建一个无环有向图
int[][] graph2 = new int[][]{{1,2},{},{}};
Graph g1 = new Graph();
List<Integer> res1 = g1.dfs(graph1);
System.out.println(res1);
Graph g2 = new Graph();
List<Integer> res2 = g2.dfs(graph2);
System.out.println(res2);
}
}
结果为：
Has cycle! [0, 1, 2, 3, 4] [0, 1, 2]
BFS:
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
public class Graph{
List<Integer> res;
public List<Integer> bfs(int[][] graph){
res = new LinkedList<>();
int n = graph.length;
//bfs判断成环或许要通过Khan算法
boolean[] visited = new boolean[n];
Queue<Integer> queue = new LinkedList<>();
//把起点放进queue同时修改visited
queue.offer(0);
visited[0] = true;
while(queue.size() > 0){
//从queue中拿出元素
int u = queue.poll();
res.add(u);
for(int neighbor : graph[u]){
if(visited[neighbor]) continue;
//如果未遍历，则加入queue中并修改visited
visited[neighbor] = true;
queue.offer(neighbor);
}
}
return res;
}
public static void main(String[] args){
//构建一个有环有向图
int[][] graph1 = new int[][]{{1,2},{0,2},{0,1,3},{2,4},{3}};
//构建一个无环有向图
int[][] graph2 = new int[][]{{1,2},{},{}};
Graph g = new Graph();
List<Integer> res1 = g.bfs(graph1);
System.out.println(res1);
List<Integer> res2 = g.bfs(graph2);
System.out.println(res2);
}
}
结果为：
[0, 1, 2, 3, 4] [0, 1, 2]
3. 环检测及拓扑排序
leetcode中的207. 课程表 - 力扣（LeetCode）以及210. 课程表 II - 力扣（LeetCode）
207. 课程表考察如何判断一个图是否成环，代码如下：
DFS版本：
class Solution {
boolean res = true;
//本质上是判断是否有环
public boolean canFinish(int numCourses, int[][] prerequisites) {
//构建图
LinkedList<Integer>[] graph = new LinkedList[numCourses];
//java构建邻接矩阵还挺麻烦。。
for(int i = 0; i < numCourses; i++){
graph[i] = new LinkedList<Integer>();
}
for(int[] p : prerequisites){
graph[p[0]].add(p[1]);
}
//判断图是否有环需要借助onPath
boolean[] visited = new boolean[numCourses];
boolean[] onPath = new boolean[numCourses];
//这里很重要，因为不一定是连通图
for(int i = 0; i < numCourses; i++){
if(visited[i]) continue;
traverse(graph, i, visited, onPath);
}
return res;
}
public void traverse(LinkedList<Integer>[] graph, int node, boolean[] visited, boolean[] onPath){
//注意onPath和visited判断的顺序，onPath得在前面，要不就return了
if(onPath[node]) res = false;
//!res是优化，发现有环就全部return
if(visited[node] || !res) return;
visited[node] = true;
onPath[node] = true;
for(int neighbor : graph[node]){
traverse(graph, neighbor, visited, onPath);
}
onPath[node] = false;
}
}
BFS：（Khan's algorithm，如果有环则无法遍历到所有的节点）
class Solution {
//BFS版本，其实和Khan's algorithm很像
//当有环的时候，Khan's algorithm无法遍历到所有的节点
public boolean canFinish(int numCourses, int[][] prerequisites) {
//构建graph，记录indegrees
LinkedList<Integer>[] graph = new LinkedList[numCourses];
int[] indegrees = new int[numCourses];
for(int i = 0; i < numCourses; i++){
graph[i] = new LinkedList<Integer>();
}
for(int[] p : prerequisites){
int from = p[0], to = p[1];
graph[from].add(to);
indegrees[to]++;
}
//执行Khan's algorithm
Queue<Integer> queue = new LinkedList<>();
for(int i = 0; i < numCourses; i++){
if(indegrees[i] == 0) queue.offer(i);
}
while(queue.size() > 0){
int u = queue.poll();
for(int neighbor : graph[u]){
//不用真的把入边删除，只需要改变indegrees
indegrees[neighbor]--;
if(indegrees[neighbor] == 0) queue.offer(neighbor);
}
}
for(int indegree : indegrees){
if(indegree != 0) return false;
}
return true;
}
}
210. 课程表II
这道题在207. 课程表I的基础上要求给出课程之间的先后关系，这是一道很典型的求拓扑排序的题目，代码如下：
DFS得到拓扑排序：（注意一般情况下DFS得到的节点顺序需要反转之后才能得到答案）
class Solution {
LinkedList<Integer> res = new LinkedList<>();
boolean hasCycle = false;
//本质上是得到拓扑排序
//DFS版本
public int[] findOrder(int numCourses, int[][] prerequisites) {
//构造graph
LinkedList<Integer>[] graph = new LinkedList[numCourses];
for(int i = 0; i < numCourses; i++){
graph[i] = new LinkedList<Integer>();
}
for(int[] p : prerequisites){
graph[p[0]].add(p[1]);
}
boolean[] visited = new boolean[numCourses];
boolean[] onPath = new boolean[numCourses];
for(int i = 0; i < numCourses; i++){
traverse(graph, i, visited, onPath);
if(hasCycle) return new int[]{};
}
//反转res
int[] ans = new int[numCourses];
for(int i = 0; i < numCourses; i++){
ans[i] = res.remove();
}
return ans;
}
public void traverse(LinkedList<Integer>[] graph, int node, boolean[] visited, boolean[] onPath){
if(onPath[node]) hasCycle = true;
if(hasCycle || visited[node]) return;
visited[node] = true;
onPath[node] = true;
for(int neighbor : graph[node]){
traverse(graph, neighbor, visited, onPath);
}
onPath[node] = false;
res.add(node);
}
}
BFS得到拓扑排序（Khan's algorithm），因为和BFS有些许差异，做一些简单的解释：
Khan's algorithm做下面几件事：
i. 记录所有节点的入度，维护一个队列并将所有入度为0的节点加入到队列中；
ii. pop出队列当前节点并加入到结果中，遍历其邻居，将当前节点删除（即更新邻居节点的入度），如果该更新后的邻居节点的入度为0，则加入到队列中
iii. 反复ii.直到队列为空，最终结果无需反转。
代码如下：
class Solution {
LinkedList<Integer> res = new LinkedList<>();
//BFS版本（Khan算法）
public int[] findOrder(int numCourses, int[][] prerequisites) {
//构建graph和indegrees
LinkedList<Integer>[] graph = new LinkedList[numCourses];
int[] indegrees = new int[numCourses];
for(int i = 0; i < numCourses; i++){
graph[i] = new LinkedList<Integer>();
}
for(int[] p : prerequisites){
int from = p[1], to = p[0];
graph[from].add(to);
indegrees[to]++;
}
//执行Khan算法
Queue<Integer> queue = new LinkedList<>();
for(int i = 0; i < numCourses; i++){
if(indegrees[i] == 0) queue.offer(i);
}
while(queue.size() > 0){
int u = queue.poll();
res.add(u);
for(int neighbor : graph[u]){
indegrees[neighbor]--;
if(indegrees[neighbor] == 0) queue.offer(neighbor);
}
}
//检查是否成环
for(int indegree : indegrees){
if(indegree != 0) return new int[]{};
}
int[] ans = new int[numCourses];
for(int i = 0; i < numCourses; i++){
ans[i] = res.remove();
}
return ans;
}
}
4. 二分图判断问题
二分图判断问题很简单，其实就是双色问题，一边遍历一边涂色，如果发现颜色冲突则说明不是二分图。
相关力扣题有785. 判断二分图 - 力扣（LeetCode）、886. 可能的二分法 - 力扣（LeetCode）。
以785. 判断二分图举例：
DFS版本：
class Solution {
boolean res = true;
//判断二分图本质上就是遍历+双色问题，能涂成双色就是二分图，不行就不是
//DFS版本
public boolean isBipartite(int[][] graph) {
int n = graph.length;
boolean[] visited = new boolean[n];
//color用true和false表示
boolean[] color = new boolean[n];
//可能有多个连通子图
for(int i = 0; i < n; i++){
if(!res) break;
if(visited[i]) continue;
traverse(graph, i, visited, color);
}
return res;
}
public void traverse(int[][] graph, int node, boolean[] visited, boolean[] color){
//!res优化
if(!res) {
return;
}
visited[node] = true;
for(int neighbor : graph[node]){
//如果邻居还没被visited，更新颜色，traverse
if(!visited[neighbor]){
color[neighbor] = !color[node];
traverse(graph, neighbor, visited, color);
}
else{
if(color[neighbor] == color[node]){
res = false;
return;
}
}
}
}
}
BFS版本：
class Solution {
boolean res = true;
//BFS版本
public boolean isBipartite(int[][] graph) {
int n = graph.length;
boolean[] visited = new boolean[n];
boolean[] color = new boolean[n];
for(int i = 0; i < n; i++){
if(!res) break;
if(!visited[i]) bfs(graph, i, visited, color);
}
return res;
}
public void bfs(int[][] graph, int node, boolean[] visited, boolean[] color){
Queue<Integer> queue = new LinkedList<>();
queue.offer(node);
visited[node] = true;
while(queue.size() > 0){
int u = queue.poll();
for(int neighbor : graph[u]){
if(!visited[neighbor]){
visited[neighbor] = true;
color[neighbor] = !color[u];
queue.offer(neighbor);
}
else{
if(color[neighbor] == color[u]){
res = false;
return;
}
}
}
}
}
}
5. 最小生成树问题
最小生成树有两种算法，比较复杂，这里做一点简单的解释：
以1584. 连接所有点的最小费用 - 力扣（LeetCode）为例：
i. Kruskal算法
Kruskal算法利用了查并集，其基本步骤如下：
1. 构建edge list，按照权重对edge list进行排序（从小到大）；
2. 创建一个查并集的对象（具体实现单独用一篇文章解释），也可以参考下面的Kruskal代码;
3. 遍历所有的edge，如果edge的两个端点已经连接了，则pass，否则就将两个端点连接起来，并更新最小生成树mst。
class Solution {
int mst = 0;
//典型的最小生成树问题
//手写一个Kruskal算法
public int minCostConnectPoints(int[][] points) {
//构建edge list（EL）
List<int[]> edges = new ArrayList<>();
for(int i = 0; i < points.length; i++){
for(int j = i + 1; j < points.length; j++){
edges.add(new int[]{i, j, Math.abs(points[i][0] - points[j][0]) + Math.abs(points[i][1] - points[j][1])});
}
}
//对EL进行排序
//记得输入comparator
Collections.sort(edges, (a, b) -> a[2] - b[2]);
UF uf = new UF(points.length);
//遍历所有的edge
for(int[] edge : edges){
int i = edge[0], j = edge[1], dist = edge[2];
//联通了就pass，否则就在UF中给连起来，同时更新MST
if(uf.connected(i, j)) continue;
mst += dist;
uf.union(i, j);
}
return mst;
}
//kruskal依赖于联通域问题，需要手写
class UF{
//记录连通分量数量
int count;
//记录连通分量的大小
int[] size;
//记录每个节点的根节点
int[] parents;
public UF(int n){
// 一开始有n个连通分量
count = n;
size = new int[n];
parents = new int[n];
//一开始所有parents[i]都指向自己
for(int i = 0; i < n; i++){
parents[i] = i;
}
}
//UF主要的函数有find、connected、union、count
//union主要用于连接两个节点(一般是q接到p上)
public void union(int p, int q){
int rootp = find(p);
int rootq = find(q);
//如果已经联通就不需要再连了
if(rootp == rootq) return;
//平衡，小树连大树
//因为find采用递归，所以其实不需要size平衡了
// if(size[rootp] < size[rootq]){
// parents[rootp] = rootq;
// //记得更新size
// size[rootq] += size[rootp];
// }
// else {
// parents[rootq] = rootp;
// size[rootp] += size[rootq];
// }
parents[rootq] = rootp;
size[rootp] += size[rootq];
count--;
}
//find主要用于找到指定节点的根节点
//这个先死记硬背吧。。。之后再看原理(递归版本比较好)
public int find(int x) {
if (parents[x] != x) {
parents[x] = find(parents[x]);
}
return parents[x];
}
public boolean connected(int p, int q){
int rootp = find(p);
int rootq = find(q);
return rootp == rootq;
}
//count直接返回count
public int count(){
return count;
}
}
}
2. Prim算法：
Prim算法利用了优先队列来得到权重最小的edge，我认为过程和Kruskal有异曲同工之妙（但是是通过visited来判断是否已连接），但其过程又类似于BFS和狄杰斯特拉，大概步骤如下：
i. 构建邻接表，维护一个优先队列，从起始节点开始，把其邻居以及到邻居这条边的权重加入到优先队列中；
ii. pop出优先队列的第一个节点u，如果visited[u]，则pass，否则更新mst；
iii. 遍历u的邻居，将其邻居及到邻居这条边的权重加入到优先队列中；
iiii. 重复ii和iii直到优先队列为空（或者维护一个count，当count == # of nodes时提前终止循环）。
代码如下：
class Solution {
int mst = 0;
//试试Prim算法
public int minCostConnectPoints(int[][] points) {
//构建graph
int n = points.length;
LinkedList<int[]>[] graph = new LinkedList[n];
for(int i = 0; i < n; i++){
graph[i] = new LinkedList<int[]>();
}
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(j == i) continue;
graph[i].add(new int[]{j, Math.abs(points[i][0] - points[j][0]) + Math.abs(points[i][1] - points[j][1])});
}
}
//执行Prim
//类似BFS(狄杰斯特拉)
//count记录树中节点个数，以优化算法
int count = 0;
boolean[] visited = new boolean[n];
Queue<int[]> queue = new PriorityQueue<>((a, b) -> a[2] - b[2]);
//从0节点开始
visited[0] = true;
count++;
//把0的所有邻边加入到优先队列中
for(int[] edge : graph[0]){
queue.offer(new int[]{0, edge[0], edge[1]});
}
while(queue.size() > 0){
int[] u = queue.poll();
int from = u[0], to = u[1], dist = u[2];
//和BFS不同的是，visited的判断和修改放在了外循环
if(visited[to]) continue;
visited[to] = true;
mst += dist;
count++;
//优化
if(count == n) break;
//把to节点的所有邻边也加入到优先队列中
for(int[] edge : graph[to]){
queue.offer(new int[]{to, edge[0], edge[1]});
}
}
return mst;
}
}
6. 最短路径问题
最短路径问题可以采用狄杰斯特拉算法（不能处理负环的情况），狄杰斯特拉算法利用优先队列计算出从初始节点到其他所有节点的最短路径。刷过的相关题目有743. 网络延迟时间 - 力扣（LeetCode）、1514. 概率最大的路径 - 力扣（LeetCode）、1631. 最小体力消耗路径 - 力扣（LeetCode）
以1514. 概率最大的路径举例，下面的代码可以作为狄杰斯特拉的模板：
class Solution {
//最大路径问题，有意思，但其实只需要改一下PriorityQueue对大小的判断就好了
public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {
int e = edges.length;
//构建graph
LinkedList<double[]>[] graph = new LinkedList[n];
for(int i = 0; i < n; i++){
graph[i] = new LinkedList<double[]>();
}
for(int i = 0; i < e; i++){
int a = edges[i][0], b = edges[i][1];
double prob = succProb[i];
graph[a].add(new double[]{(double)b, prob});
graph[b].add(new double[]{(double)a, prob});
}
double[] dists = new double[n];
Arrays.fill(dists, 0);
Queue<State> queue = new PriorityQueue<>((a, b) -> {
if (b.dist - a.dist > 0) return 1;
else if(b.dist - a.dist < 0) return -1;
else return 0;});
dists[start] = 1;
queue.offer(new State(start, 1));
while(queue.size() > 0){
State u = queue.poll();
if(u.id == end) return u.dist;
if(u.dist < dists[u.id]) continue;
for(double[] temp : graph[u.id]){
int cur_id = (int)temp[0];
double prob = temp[1];
double pre_prob = dists[u.id];
if(prob * pre_prob > dists[cur_id]){
dists[cur_id] = prob * pre_prob;
queue.offer(new State(cur_id, dists[cur_id]));
}
}
}
return dists[end];
}
class State{
int id;
double dist;
public State(int id, double dist){
this.id = id;
this.dist = dist;
}
// public String toString(){
// return ("u.id: " + id + ", u.dist: " + dist);
// }
}
}
在狄杰斯特拉算法中，外层循环第一次遇见某个节点node，其dist一定是最小的（除非存在负权重的边），所以如果要求初始节点到某个节点n的最短路径，可以在外循环中判断当前节点是否为node，如果是，则直接返回当前dist。
标签：总结,图论,LinkedList,int,graph,boolean,visited,new,leetcode From： https://www.cnblogs.com/xkge/p/17459139.html