wordpress 网站禁用全屏代码,wordpress termmeta,哪个代运营公司比较好,高大上网站欣赏一、概念
图是有顶点#xff08;vertex#xff09;和边#xff08;edge#xff09;组成的数据结构#xff0c;例如 该图有4个顶点#xff1a;A、B、C、D以及四条有向边#xff0c;有向图中#xff0c;边是单向的。 1. 有向图 VS 无向图
如果是无向图#xff0c;那么…一、概念
图是有顶点vertex和边edge组成的数据结构例如 该图有4个顶点A、B、C、D以及四条有向边有向图中边是单向的。 1. 有向图 VS 无向图
如果是无向图那么边是双向的下面是一个无向图的例子 2. 度
度是指与该顶点相邻的边的数量 例如上图中
A、B、C、E、F这几个顶点的度数为2D顶点度数为4 有向图中细分为入度和出度参见下图 A2out / 0 inB、C、E1 out / 1 inD2 out / 2 inF0 out / 2 in 3. 权
边可以有权重代表从源顶点到目标顶点的距离、费用、时间或其他度量。 4. 路径
路径被定义为从一个顶点到另一个顶点的另一个顶点的一系列连续边例如上图中【北京】到【上海有多条路径
北京 - 上海北京 - 武汉 - 上海
路径长度
不考虑权重长度就是边的数量考虑权重一般就是权重累加 5. 环
在有向图中从一个顶点开始可以通过若干条有向边返回到该顶点那么就形成了一个环 6. 图的连通性
如果两个顶点之间存在路径则这两个顶点是连通的所有顶点都连通则该图被称为连通图。若子图连通则称为连通分量。 二、图的表示
比如说下面的无向图 用邻接矩阵可以表示为 A B C D
A 0 1 1 0
B 1 0 0 1
C 1 0 0 1
D 0 1 1 0
用邻接表可以表示为
A - B - C
B - A - D
C - A - D
D - B - C
有向图的例子 A B C D
A 0 1 1 0
B 0 0 0 1
C 0 0 0 1
D 0 0 0 0
A - B - C
B - D
C - D
D - empty 三、Java表示
顶点
package com.itheima.datastructure.graph;import java.util.List;
import java.util.Objects;/*** 顶点*/
public class Vertex {String name;public ListEdge edges;boolean visited; // 是否被访问过用在BFS和DFSint inDegree; // 入度用在拓扑排序int status; // 状态 0-未访问 1-访问中 2-访问过用在拓扑排序static final Integer INF Integer.MAX_VALUE;int dist INF; // 距离Vertex prev null; // 记录从何而来public Vertex(String name) {this.name name;}public String getName() {return name;}Overridepublic String toString() {String n name;if (visited) {n \u001B[31m name \u001B[0m;}return n ( (dist Integer.MAX_VALUE ? ∞ : String.valueOf(dist)) ) - (prev null ? null : prev.name);}Overridepublic boolean equals(Object o) {if (this o) return true;if (o null || getClass() ! o.getClass()) return false;Vertex vertex (Vertex) o;return Objects.equals(name, vertex.name);}Overridepublic int hashCode() {return name ! null ? name.hashCode() : 0;}
}边
package com.itheima.datastructure.graph;public class Edge {public Vertex linked;public int weight;public Edge(Vertex linked) {this(linked, 1);}public Edge(Vertex linked, int weight) {this.linked linked;this.weight weight;}
}四、DFS深度优先搜索 package com.itheima.datastructure.graph;import java.util.LinkedList;
import java.util.List;public class Dfs {public static void main(String[] args) {Vertex v1 new Vertex(v1);Vertex v2 new Vertex(v2);Vertex v3 new Vertex(v3);Vertex v4 new Vertex(v4);Vertex v5 new Vertex(v5);Vertex v6 new Vertex(v6);v1.edges List.of(new Edge(v3), new Edge(v2), new Edge(v6));v2.edges List.of(new Edge(v4));v3.edges List.of(new Edge(v4), new Edge(v6));v4.edges List.of(new Edge(v5));v5.edges List.of();v6.edges List.of(new Edge(v5));dfs2(v1);}/*** 递归方式实现深度优先遍历* param v*/private static void dfs(Vertex v) {v.visited true;System.out.print(v.name );for (Edge edge : v.edges) {if(!edge.linked.visited) {dfs(edge.linked);}}}/*** 非递归方式深度优先遍历* param v*/public static void dfs2(Vertex v) {LinkedListVertex stack new LinkedList();stack.push(v);while (!stack.isEmpty()) {Vertex pop stack.pop();pop.visited true;System.out.println(pop.name);for (Edge edge : pop.edges) {if(!edge.linked.visited) {stack.push(edge.linked);}}}}}五、BFS广度优先搜索
package com.itheima.datastructure.graph;import java.util.LinkedList;
import java.util.List;public class Bfs {public static void main(String[] args) {Vertex v1 new Vertex(v1);Vertex v2 new Vertex(v2);Vertex v3 new Vertex(v3);Vertex v4 new Vertex(v4);Vertex v5 new Vertex(v5);Vertex v6 new Vertex(v6);v1.edges List.of(new Edge(v3), new Edge(v2), new Edge(v6));v2.edges List.of(new Edge(v4));v3.edges List.of(new Edge(v4), new Edge(v6));v4.edges List.of(new Edge(v5));v5.edges List.of();v6.edges List.of(new Edge(v5));bfs(v1);}/*** 广度优先遍历 - 队列* param v*/private static void bfs(Vertex v) {LinkedListVertex queue new LinkedList();v.visited true;queue.offer(v);while(!queue.isEmpty()) {Vertex poll queue.poll();System.out.println(poll.name);for (Edge edge : poll.edges) {if(!edge.linked.visited) {edge.linked.visited true;queue.offer(edge.linked);}}}}
}六、拓扑排序 1. Kahn
package com.itheima.datastructure.graph;import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;public class TopologicalSort {public static void main(String[] args) {Vertex v1 new Vertex(网页基础);Vertex v2 new Vertex(Java基础);Vertex v3 new Vertex(JavaWeb);Vertex v4 new Vertex(Spring框架);Vertex v5 new Vertex(微服务框架);Vertex v6 new Vertex(数据库);Vertex v7 new Vertex(实战项目);v1.edges List.of(new Edge(v3)); // 1v2.edges List.of(new Edge(v3)); // 1v3.edges List.of(new Edge(v4));v6.edges List.of(new Edge(v4));v4.edges List.of(new Edge(v5));v5.edges List.of(new Edge(v7));v7.edges List.of();ListVertex graph List.of(v1, v2, v3, v4, v5, v6, v7);topologicalSort(graph);}private static void topologicalSort(ListVertex graph) {// 1. 统计每个顶点的入度for (Vertex v : graph) { // 顶点集for (Edge edge : v.edges) { // 边集edge.linked.inDegree;}}// 2. 将入度为0的顶点加入队列LinkedListVertex queue new LinkedList();for (Vertex v : graph) {if(v.inDegree 0) {queue.offer(v);}}// 3. 队列中不断移除顶点每移除一个顶点把他相邻顶点入度减1若减到0则入队ListString result new ArrayList();while(!queue.isEmpty()) {Vertex poll queue.poll();result.add(poll.name);for (Edge edge : poll.edges) {edge.linked.inDegree--;if(edge.linked.inDegree 0) {queue.offer(edge.linked);}}}if(result.size() ! graph.size()) {System.out.println(图中出现环);} else {for (String key : result) {System.out.println(key);}}}
}2. DFS
package com.itheima.datastructure.graph;import java.util.LinkedList;
import java.util.List;public class TopologicalSortDFS {public static void main(String[] args) {Vertex v1 new Vertex(网页基础);Vertex v2 new Vertex(Java基础);Vertex v3 new Vertex(JavaWeb);Vertex v4 new Vertex(Spring框架);Vertex v5 new Vertex(微服务框架);Vertex v6 new Vertex(数据库);Vertex v7 new Vertex(实战项目);v1.edges List.of(new Edge(v3));v2.edges List.of(new Edge(v3));v3.edges List.of(new Edge(v4));v6.edges List.of(new Edge(v4));v4.edges List.of(new Edge(v5));v5.edges List.of(new Edge(v7));v7.edges List.of();ListVertex graph List.of(v1, v2, v3, v4, v5, v6, v7);LinkedListString result new LinkedList();for (Vertex v : graph) {if(v.status0) {dfs(v, result);}}System.out.println(result);}private static void dfs(Vertex v, LinkedListString result) {if(v.status 2) {// 已经访问过了return;}if(v.status 1) {// 访问中throw new RuntimeException(发现环);}v.status 1;// 遍历相邻节点for (Edge edge : v.edges) {dfs(edge.linked, result);}v.status 2;// 向回走再压栈result.push(v.name);}
}七、最短路径
1. Dijkstra 算法描述
1. 将所有顶点标记为未访问创建一个未访问顶点的集合
2. 为每个顶点分配一个临时距离值
对于我们的初始顶点将其设置为零对于所有其他顶点将其设置为无穷大
3. 每次选择最小临时距离的未访问顶点作为新的当前顶点
4. 对于当前顶点遍历其所有未访问的邻居并更新他们的临时距离为更小
例如1-6的距离为14而1-3-6的距离是11.这时将距离更新为11否则将保留上次距离值
5. 当前顶点的邻居处理完成后把它从未访问集合中删除
代码
package com.itheima.datastructure.graph;import java.util.ArrayList;
import java.util.List;public class Dijkstra {public static void main(String[] args) {Vertex v1 new Vertex(v1);Vertex v2 new Vertex(v2);Vertex v3 new Vertex(v3);Vertex v4 new Vertex(v4);Vertex v5 new Vertex(v5);Vertex v6 new Vertex(v6);v1.edges List.of(new Edge(v3, 9), new Edge(v2, 7), new Edge(v6, 14));v2.edges List.of(new Edge(v4, 15));v3.edges List.of(new Edge(v4, 11), new Edge(v6, 2));v4.edges List.of(new Edge(v5, 6));v5.edges List.of();v6.edges List.of(new Edge(v5, 9));ListVertex graph List.of(v1, v2, v3, v4, v5, v6);dijkstra(graph, v1);}private static void dijkstra(ListVertex graph, Vertex source) {// 1. 将所有顶点标记为未访问创建一个未访问顶点的集合ArrayListVertex list new ArrayList(graph);// 2. 初始顶点距离设置为0source.dist 0;while(!list.isEmpty()) {// 3. 选择最小临时距离的未访问节点作为新的当前顶点Vertex curr chooseMinDistVertex(list);// 4. 对于当前顶点遍历其所有未访问的邻居并更新它们的临时距离为更小updateNeighbourDist(curr, list);// 5. 当前顶点的邻居处理完成后把它从未访问集合中移除list.remove(curr);}for (Vertex v : graph) {System.out.println(v.name v.dist);}}/*** 对于当前顶点遍历其所有未访问的邻居并更新它们的临时距离为更小* param curr* param list*/private static void updateNeighbourDist(Vertex curr, ArrayListVertex list) {for (Edge edge : curr.edges) {Vertex n edge.linked;if(list.contains(n)) {int dist curr.dist edge.weight;if(dist n.dist) {n.dist dist;}}}}/*** 选取当前顶点 - 找到距离值最小的顶点* param list* return*/private static Vertex chooseMinDistVertex(ArrayListVertex list) {Vertex min list.get(0);for (int i 1; i list.size(); i) {if(list.get(i).dist min.dist) {min list.get(i);}}return min;}
}改进优先级队列
1. 创建一个优先级队列放入所有顶点队列大小会达到边的数量
2. 为每个顶点分配一个临时距离值
对于初始顶点将其设置为零对于其他所有顶点将其设置为无穷大
3. 每次选择最小临时距离的未访问顶点作为新的当前顶点
4. 对于当前顶点遍历其所有未访问的邻居并更新它们的临时距离为更小若距离更新需要加入队列
例如1-6的距离是14而1-3-6的距离是11。这时将距离更新为11否则将保留上次距离值
5. 当前顶点的邻居处理完成后把它从队列中删除
package com.itheima.datastructure.graph;import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;public class DijkstraPriorityQueue {public static void main(String[] args) {Vertex v1 new Vertex(v1);Vertex v2 new Vertex(v2);Vertex v3 new Vertex(v3);Vertex v4 new Vertex(v4);Vertex v5 new Vertex(v5);Vertex v6 new Vertex(v6);v1.edges List.of(new Edge(v3, 9), new Edge(v2, 7), new Edge(v6, 14));v2.edges List.of(new Edge(v4, 15));v3.edges List.of(new Edge(v4, 11), new Edge(v6, 2));v4.edges List.of(new Edge(v5, 6));v5.edges List.of();v6.edges List.of(new Edge(v5, 9));ListVertex graph List.of(v1, v2, v3, v4, v5, v6);dijkstra(graph, v1);}private static void dijkstra(ListVertex graph, Vertex source) {// 1. 创建一个优先级队列放入所有顶点小根堆PriorityQueueVertex queue new PriorityQueue(Comparator.comparing(v - v.dist));// 2. 对于初始顶点将其临时距离值设置为0source.dist 0;for (Vertex v : graph) {queue.offer(v);}while(!queue.isEmpty()) {System.out.println(queue);// 3. 选取当前顶点距离值最小的顶点Vertex curr queue.peek();// 4. 更新当前顶点邻居距离if(!curr.visited) {updateNeighbourDist(curr, queue);curr.visited true;}// 5. 移除当前节点queue.poll();}for (Vertex v : graph) {System.out.println(v.name v.dist (v.prev ! null ? v.prev.name : null));}}private static void updateNeighbourDist(Vertex curr, PriorityQueueVertex queue) {for (Edge edge : curr.edges) {Vertex n edge.linked;if(!n.visited) {int dist curr.dist edge.weight;if(dist n.dist) {n.dist dist;n.prev curr;queue.offer(n);}}}}
}2. Bellman-Ford
问题 按照Dijkstra算法得出
v1 - v2最短距离2v1 - v3最短距离1v1 - v4最短距离2
事实应当是
v1 - v2最短距离2v1 - v3最短距离0v1 - v4最短距离1
package com.itheima.datastructure.graph;import java.util.List;/*** Bellman-Ford算法可以处理负边*/
public class BellmanFord {public static void main(String[] args) {// 正常情况/*Vertex v1 new Vertex(v1);Vertex v2 new Vertex(v2);Vertex v3 new Vertex(v3);Vertex v4 new Vertex(v4);Vertex v5 new Vertex(v5);Vertex v6 new Vertex(v6);v1.edges List.of(new Edge(v3, 9), new Edge(v2, 7), new Edge(v6, 14));v2.edges List.of(new Edge(v4, 15));v3.edges List.of(new Edge(v4, 11), new Edge(v6, 2));v4.edges List.of(new Edge(v5, 6));v5.edges List.of();v6.edges List.of(new Edge(v5, 9));ListVertex graph List.of(v4, v5, v6, v1, v2, v3);*/// 负边情况/*Vertex v1 new Vertex(v1);Vertex v2 new Vertex(v2);Vertex v3 new Vertex(v3);Vertex v4 new Vertex(v4);v1.edges List.of(new Edge(v2, 2), new Edge(v3, 1));v2.edges List.of(new Edge(v3, -2));v3.edges List.of(new Edge(v4, 1));v4.edges List.of();ListVertex graph List.of(v1, v2, v3, v4);*/// 负环情况Vertex v1 new Vertex(v1);Vertex v2 new Vertex(v2);Vertex v3 new Vertex(v3);Vertex v4 new Vertex(v4);v1.edges List.of(new Edge(v2, 2));v2.edges List.of(new Edge(v3, -4));v3.edges List.of(new Edge(v4, 1), new Edge(v1, 1));v4.edges List.of();ListVertex graph List.of(v1, v2, v3, v4);bellmanFord(graph, v1);}private static void bellmanFord(ListVertex graph, Vertex source) {source.dist 0;int size graph.size();for (int i 0; i size - 1; i) {for (Vertex s : graph) {for (Edge edge : s.edges) {Vertex e edge.linked;if(s.dist ! Integer.MAX_VALUE s.dist edge.weight e.dist) {e.dist s.dist edge.weight;e.prev s;}}}}for (Vertex v : graph) {System.out.println(v);}}
}负环 如果在【顶点-1】轮处理完成后还能继续找到更短距离表示发现了负环。比如在上面这张图中经过了3轮处理后还能继续找到更短距离直到无穷小。 3. Floy-Warshall package com.itheima.datastructure.graph;import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;/*** Floyd - Warshall多源最短路径算法*/
public class FloydWarshall {public static void main(String[] args) {Vertex v1 new Vertex(v1);Vertex v2 new Vertex(v2);Vertex v3 new Vertex(v3);Vertex v4 new Vertex(v4);v1.edges List.of(new Edge(v3, -2));v2.edges List.of(new Edge(v1, 4), new Edge(v3, 3));v3.edges List.of(new Edge(v4, 2));v4.edges List.of(new Edge(v2, -1));ListVertex graph List.of(v1, v2, v3, v4);// 负环情况/*Vertex v1 new Vertex(v1);Vertex v2 new Vertex(v2);Vertex v3 new Vertex(v3);Vertex v4 new Vertex(v4);v1.edges List.of(new Edge(v2, 2));v2.edges List.of(new Edge(v3, -4));v3.edges List.of(new Edge(v4, 1), new Edge(v1, 1));v4.edges List.of();ListVertex graph List.of(v1, v2, v3, v4);*/floydWarshall(graph);}private static void floydWarshall(ListVertex graph) {int size graph.size();int[][] dist new int[size][size];Vertex[][] prev new Vertex[size][size];// 1. 初始化for (int i 0; i size; i) {Vertex v graph.get(i);MapVertex, Integer map v.edges.stream().collect(Collectors.toMap(e - e.linked, e - e.weight));for (int j 0; j size; j) {Vertex u graph.get(j);if (v u) {dist[i][j] 0;} else {dist[i][j] map.getOrDefault(u, Integer.MAX_VALUE);prev[i][j] map.get(u) ! null ? v : null;}}}// print(dist);print(prev);// 2. 看能否借路到达其他顶点/*** v2 - v1* dist[1][0]*/for (int k 0; k size; k) { // 借助第k个顶点到达其他顶点for (int i 0; i size; i) { // 第i行for (int j 0; j size; j) { // 第j列// 第i行的顶点借助第k个顶点到达第j列顶点// 可达且距离更小if (dist[i][k] ! Integer.MAX_VALUE dist[k][j] ! Integer.MAX_VALUE dist[i][k] dist[k][j] dist[i][j]) {dist[i][j] dist[i][k] dist[k][j];prev[i][j] prev[k][j];}}}// 如果对角线上有一个值小于0则出现了负环// print(dist);}print(prev);for (int i 0; i size; i) {for (int j 0; j size; j) {path(prev, graph, i, j);}}}private static void print(int[][] dist) {System.out.println(---------------------);for (int[] row : dist) {System.out.println(Arrays.stream(row).boxed().map(x - x Integer.MAX_VALUE ? ∞ : String.valueOf(x)).map(s - String.format(%2s, s)).collect(Collectors.joining(,, [, ])));}}private static void print(Vertex[][] prev) {System.out.println(---------------------);for (Vertex[] row : prev) {System.out.println(Arrays.stream(row).map(v - v null ? null : v.name).map(s - String.format(%5s, s)).collect(Collectors.joining(,, [, ])));}}private static void path(Vertex[][] prev, ListVertex graph, int i, int j) {LinkedListString stack new LinkedList();System.out.println([ graph.get(i).name , graph.get(j).name ]);stack.push(graph.get(j).name);while(i ! j) {Vertex p prev[i][j];stack.push(p.name);j graph.indexOf(p);}System.out.println(stack);}
}八、最小生成树
1. Prim
Prim算法是一个用于寻找带权图的最小生成树的贪心算法其基本思路如下
1. 初始化选择一个初始顶点将其加入到生成树中设置一个优先队列或最小堆来存储边边的权重作为优先级。
2. 扩展树
从已加入生成树的顶点出发找到与生成树中顶点相连的所有边并选择其中权重最小的边将这条边的另一个顶点加入生成树同时更新优先队列中与新加入顶点相连的边
3. 重复步骤重复以上过程直到所有顶点都被加入到生成树中。
时间复杂度O(E log V)其中E是边的数量V是顶点的数量。 package com.itheima.datastructure.graph;import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;/*** 最小生成树*/
public class Prim {public static void main(String[] args) {Vertex v1 new Vertex(v1);Vertex v2 new Vertex(v2);Vertex v3 new Vertex(v3);Vertex v4 new Vertex(v4);Vertex v5 new Vertex(v5);Vertex v6 new Vertex(v6);Vertex v7 new Vertex(v7);v1.edges List.of(new Edge(v2, 2), new Edge(v3, 4), new Edge(v4, 1));v2.edges List.of(new Edge(v1, 2), new Edge(v4, 3), new Edge(v5, 10));v3.edges List.of(new Edge(v1, 4), new Edge(v4, 2), new Edge(v6, 5));v4.edges List.of(new Edge(v1, 1), new Edge(v2, 3), new Edge(v3, 2),new Edge(v5, 7), new Edge(v6, 8), new Edge(v7, 4));v5.edges List.of(new Edge(v2, 10), new Edge(v4, 7), new Edge(v7, 6));v6.edges List.of(new Edge(v3, 5), new Edge(v4, 8), new Edge(v7, 1));v7.edges List.of(new Edge(v4, 4), new Edge(v5, 6), new Edge(v6, 1));ListVertex graph List.of(v1, v2, v3, v4, v5, v6, v7);prim(graph, v1);}private static void prim(ListVertex graph, Vertex source) {// 1. 创建一个未访问顶点的集合ArrayListVertex list new ArrayList(graph);// 2. 为初始顶点设置临时距离值为0source.dist 0;while(!list.isEmpty()) {// 3. 选择最小临时距离的未访问顶点作为新的当前顶点Vertex min chooseMinDistVertex(list);// 4. 对于当前顶点遍历其所有未访问的邻居并更新它们的临时距离为更小updateNeighboursDist(min);// 5. 当前顶点的邻居处理完成后把它从未访问集合中删除list.remove(min);min.visited true;System.out.println(------------------);for (Vertex v : graph) {System.out.println(v);}}}private static void updateNeighboursDist(Vertex curr) {for (Edge edge : curr.edges) {Vertex n edge.linked;if(!n.visited) {int dist edge.weight;if(dist n.dist) {n.dist dist;n.prev curr;}}}}private static Vertex chooseMinDistVertex(ArrayListVertex list) {Vertex min list.get(0);for (int i 1; i list.size(); i) {if(list.get(i).dist min.dist) {min list.get(i);}}return min;}
}2. Kruskal
package com.itheima.datastructure.graph;import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;public class Kruskal {static class Edge implements ComparableEdge {ListVertex vertices;int start;int end;int weight;public Edge(ListVertex vertices, int start, int end, int weight) {this.vertices vertices;this.start start;this.end end;this.weight weight;}public Edge(int start, int end, int weight) {this.start start;this.end end;this.weight weight;}Overridepublic int compareTo(Edge o) {return Integer.compare(this.weight, o.weight);}Overridepublic String toString() {return vertices.get(start).name - vertices.get(end).name ( weight );}}public static void main(String[] args) {Vertex v1 new Vertex(v1);Vertex v2 new Vertex(v2);Vertex v3 new Vertex(v3);Vertex v4 new Vertex(v4);Vertex v5 new Vertex(v5);Vertex v6 new Vertex(v6);Vertex v7 new Vertex(v7);ListVertex vertices List.of(v1, v2, v3, v4, v5, v6, v7);// 优先队列小根堆 - 根据边的权重比较PriorityQueueEdge queue new PriorityQueue(List.of(new Edge(vertices,0, 1, 2),new Edge(vertices,0, 2, 4),new Edge(vertices,0, 3, 1),new Edge(vertices,1, 3, 3),new Edge(vertices,1, 4, 10),new Edge(vertices,2, 3, 2),new Edge(vertices,2, 5, 5),new Edge(vertices,3, 4, 7),new Edge(vertices,3, 5, 8),new Edge(vertices,3, 6, 4),new Edge(vertices,4, 6, 6),new Edge(vertices,5, 6, 1)));kruskal(vertices.size(), queue);}private static void kruskal(int size, PriorityQueueEdge queue) {ListEdge result new ArrayList();DisjointSet set new DisjointSet(size);// 小于顶点的个数减1 - 还没找完while(result.size() size - 1) {// 获取权重最小的边进行处理Edge poll queue.poll();int start set.find(poll.start);int end set.find(poll.end);// 如果结果不相等说明这两个顶点不相交 - 不连通if(start ! end) {result.add(poll);// 相交 - 连通set.union(start, end);}}for (Edge edge : result) {System.out.println(edge);}}
}九、不相交集合并查集合
使用并查集Union-Find来管理连通分量从而有效地检查边的连通性。
package com.itheima.datastructure.graph;import java.util.Arrays;/*** 不相交集合并查集合*/
public class DisjointSet {int[] s; // 老大int[] size; // 顶点个数public DisjointSet(int size) {s new int[size];this.size new int[size];/*** 索引对应顶点* 元素是用来表示与之有关系的顶点* 索引 0 1 2 3 4 5 6* 元素 [0, 1, 2, 3, 4, 5, 6] 表示一开始顶点直接没有联系只与自己有联系*/for (int i 0; i size; i) {s[i] i;this.size[i] 1;}}// find是找到集合中的老大 - 优化1路径压缩public int find(int x) {// 索引和值相等的就是老大if(x s[x]) {return x;}// 路径压缩return s[x] find(s[x]);}// union是让两个集合“相交”即选出新老大x、y是原老大索引// 把顶点个数少的集合连接到顶点个数多的集合public void union(int x, int y) {if(size[x] size[y]) {// y是新老大x新小弟s[x] y;// 更新老大的元素个数size[y] size[y] size[x];} else {// x是新老大y新小弟s[y] x;// 更新老大的元素个数size[x] size[x] size[y];}// 可以优化代码为/*if(size[x] size[y]) {int t x;x y;y t;}s[y] x;size[x] size[x] size[y];*/}Overridepublic String toString() {return 内容 Arrays.toString(s) \n大小 Arrays.toString(size);}public static void main(String[] args) {DisjointSet set new DisjointSet(7);System.out.println(set);int x set.find(0);int y set.find(3);System.out.println(老大分别是 x y);if(x ! y) {set.union(x, y);System.out.println(set);}}
}十、习题
1. 省份数量
有 n 个城市其中一些彼此相连另一些没有相连。如果城市 a 与城市 b 直接相连且城市 b 与城市 c 直接相连那么城市 a 与城市 c 间接相连。
省份 是一组直接或间接相连的城市组内不含其他没有相连的城市。
给你一个 n x n 的矩阵 isConnected 其中 isConnected[i][j] 1 表示第 i 个城市和第 j 个城市直接相连而 isConnected[i][j] 0 表示二者不直接相连。
返回矩阵中 省份 的数量。
示例 1 输入isConnected [[1,1,0],[1,1,0],[0,0,1]]
输出2示例 2 输入isConnected [[1,0,0],[0,1,0],[0,0,1]]
输出3提示
1 n 200n isConnected.lengthn isConnected[i].lengthisConnected[i][j] 为 1 或 0isConnected[i][i] 1isConnected[i][j] isConnected[j][i]
解法一深度优先搜索DFS。时间复杂度O(n^2)与输入矩阵大小成正比适合n的最大值为200
class Solution {public int findCircleNum(int[][] isConnected) {int n isConnected.length;boolean[] visited new boolean[n];int provinceCount 0;for (int i 0; i n; i) {if(!visited[i]) {// 在未访问的城市上进行DFSdfs(isConnected, visited, i);// 每遍历完一个省份增加计数provinceCount;}}return provinceCount;}private void dfs(int[][] isConnected, boolean[] visited, int city) {// 标记城市为已访问visited[city] true;for (int j 0; j isConnected.length; j) {// 如果有连接且问访问的城市则继续DFS。结束时会访问完一个省份的所有城市if(isConnected[city][j] 1 !visited[j]) {dfs(isConnected, visited, j);}}}
}
解法二广度优先搜索BFS。时间复杂度O(n^2)与输入矩阵大小成正比适合n的最大值为200
class Solution {public int findCircleNum(int[][] isConnected) {int n isConnected.length;boolean[] visited new boolean[n];int provinceCount 0;for (int i 0; i n; i) {if (!visited[i]) {// 在未访问的城市上进行BFSbfs(isConnected, visited, i);// 每遍历完一个省份增加计数provinceCount;}}return provinceCount;}private void bfs(int[][] isConnected, boolean[] visited, int city) {LinkedListInteger queue new LinkedList();queue.offer(city);// 标记城市为已访问visited[city] true;while (!queue.isEmpty()) {// 取出队列中的城市int currentCity queue.poll();for (int j 0; j isConnected.length; j) {// 如果有连接且未访问则加入队列if (isConnected[currentCity][j] 1 !visited[j]) {visited[j] true;queue.offer(j);}}}}
}
解法三并查集
class Solution {static class DisjionSet {private int[] parent;private int count;public DisjionSet(int n) {parent new int[n];for (int i 0; i n; i) {// 初始化每个城市的父节点为自身parent[i] i;}count n; // 初始时省份数量为城市数}public int find(int city) {if (parent[city] ! city) {// 路径压缩parent[city] find(parent[city]);}return parent[city];}public void union(int city1, int city2) {int root1 find(city1);int root2 find(city2);if (root1 ! root2) {// 合并两个省份parent[root1] root2;// 合并后省份数量减少count--;}}public int getCount() {return count;}}public int findCircleNum(int[][] isConnected) {int n isConnected.length;DisjionSet set new DisjionSet(n);for (int i 0; i n; i) {for (int j i 1; j n; j) {// 如果两个城市连接则合并if (isConnected[i][j] 1) {set.union(i, j);}}}return set.getCount();}
} 2. 所有可能路径
给你一个有 n 个节点的 有向无环图DAG请你找出所有从节点 0 到节点 n-1 的路径并输出不要求按特定顺序 graph[i] 是一个从节点 i 可以访问的所有节点的列表即从节点 i 到节点 graph[i][j]存在一条有向边。
示例 1 输入graph [[1,2],[3],[3],[]]
输出[[0,1,3],[0,2,3]]
解释有两条路径 0 - 1 - 3 和 0 - 2 - 3示例 2 输入graph [[4,3,1],[3,2,4],[3],[4],[]]
输出[[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]提示
n graph.length2 n 150 graph[i][j] ngraph[i][j] ! i即不存在自环graph[i] 中的所有元素 互不相同保证输入为 有向无环图DAG
解法一深度优先搜索DFS
class Solution {public ListListInteger allPathsSourceTarget(int[][] graph) {ListListInteger result new ArrayList();ListInteger path new ArrayList();path.add(0);// 从节点0开始深度优先搜索dfs(graph, 0, path, result);return result;}private void dfs(int[][] graph, int node, ListInteger path, ListListInteger result) {// 到了第n - 1个节点if (node graph.length - 1) {result.add(new ArrayList(path));return;}for (int neighbor : graph[node]) {path.add(neighbor);// 从相邻节点继续递归dfs(graph, neighbor, path, result);path.remove(path.size() - 1); // 回溯}}
}
解法二广度优先搜索BFS
class Solution {public ListListInteger allPathsSourceTarget(int[][] graph) {ListListInteger result new ArrayList();QueueListInteger queue new LinkedList();ListInteger startPath new ArrayList();startPath.add(0);queue.offer(startPath);while (!queue.isEmpty()) {ListInteger currentPath queue.poll();// 获取某条路径的最后一个节点int lastNode currentPath.get(currentPath.size() - 1);if (lastNode graph.length - 1) {result.add(new ArrayList(currentPath));}for (int neighbor : graph[lastNode]) {// 在当前路径基础上添加新的节点ListInteger newPath new ArrayList(currentPath);newPath.add(neighbor);queue.offer(newPath);}}return result;}
} 3. 连接所有点的最小费用
给你一个points 数组表示 2D 平面上的一些点其中 points[i] [xi, yi] 。
连接点 [xi, yi] 和点 [xj, yj] 的费用为它们之间的 曼哈顿距离 |xi - xj| |yi - yj| 其中 |val| 表示 val 的绝对值。
请你返回将所有点连接的最小总费用。只有任意两点之间 有且仅有 一条简单路径时才认为所有点都已连接。
示例 1
输入points [[0,0],[2,2],[3,10],[5,2],[7,0]]
输出20
解释我们可以按照上图所示连接所有点得到最小总费用总费用为 20 。
注意到任意两个点之间只有唯一一条路径互相到达。示例 2
输入points [[3,12],[-2,5],[-4,1]]
输出18示例 3
输入points [[0,0],[1,1],[1,0],[-1,1]]
输出4示例 4
输入points [[-1000000,-1000000],[1000000,1000000]]
输出4000000示例 5
输入points [[0,0]]
输出0提示
1 points.length 1000-10^6 xi, yi 10^6所有点 (xi, yi) 两两不同。
解法一最小生成树Prim
class Solution {public int minCostConnectPoints(int[][] points) {int n points.length;if (n 1) {return 0;}boolean[] inMST new boolean[n]; // 是否在最小生成树中int[] minWeight new int[n];Arrays.fill(minWeight, Integer.MAX_VALUE);// 从第一个节点开始minWeight[0] 0; // 初始化第一个点的权重为0int totalCost 0;for (int i 0; i n; i) {// 找到下一个未包含在MST中 且 权重最小的点int u -1;for (int j 0; j n; j) {if (!inMST[j] (u -1 || minWeight[j] minWeight[u])) {u j;}}// 将该点加入到MST中inMST[u] true;totalCost minWeight[u];// 更新其他点的最小权重for (int v 0; v n; v) {if (!inMST[v]) {// u到v的权重int weight manhattanDistance(points[u], points[v]);// 更新点v的权重minWeight[v] Math.min(minWeight[v], weight);}}}return totalCost;}/*** 计算曼哈顿距离* * param p1 连接点1* param p2 连接点2* return*/private int manhattanDistance(int[] p1, int[] p2) {return Math.abs(p1[0] - p2[0]) Math.abs(p1[1] - p2[1]);}
}
解法二Kruskal算法
class Solution {// 边的类static class Edge implements ComparableEdge {private int src, dest, weight;public Edge(int src, int dest, int weight) {this.src src;this.dest dest;this.weight weight;}Overridepublic int compareTo(Edge o) {return Integer.compare(this.weight, o.weight);}}static class DisjointSet {int[] parent, rank;public DisjointSet(int n) {parent new int[n];rank new int[n];for (int i 0; i n; i) {parent[i] i;rank[i] 0;}}public int find(int u) {if (parent[u] ! u) {parent[u] find(parent[u]);}return parent[u];}public void union(int u, int v) {int rootU find(u);int rootV find(v);if (rootU ! rootV) {if (rank[rootU] rank[rootV]) {parent[rootV] rootU;} else if (rank[rootU] rank[rootV]) {parent[rootU] rootV;} else {parent[rootV] rootU;rank[rootU];}}}}public int minCostConnectPoints(int[][] points) {int n points.length;ListEdge edges new ArrayList();// 创建所有边for (int i 0; i n; i) {for (int j i 1; j n; j) {int weight manhattanDistance(points[i], points[j]);edges.add(new Edge(i, j, weight));}}// 按边权重排序Collections.sort(edges);DisjointSet set new DisjointSet(n);int totalCost 0;for (Edge edge : edges) {if (set.find(edge.src) ! set.find(edge.dest)) {set.union(edge.src, edge.dest);totalCost edge.weight;}}return totalCost;}/*** 计算曼哈顿距离* * param p1 连接点1* param p2 连接点2* return*/private int manhattanDistance(int[] p1, int[] p2) {return Math.abs(p1[0] - p2[0]) Math.abs(p1[1] - p2[1]);}
} 4. 网络延迟时间
有 n 个网络节点标记为 1 到 n。
给你一个列表 times表示信号经过 有向 边的传递时间。 times[i] (ui, vi, wi)其中 ui 是源节点vi 是目标节点 wi 是一个信号从源节点传递到目标节点的时间。
现在从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号如果不能使所有节点收到信号返回 -1
示例 1
输入times [[2,1,1],[2,3,1],[3,4,1]], n 4, k 2
输出2示例 2
输入times [[1,2,1]], n 2, k 1
输出1示例 3
输入times [[1,2,1]], n 2, k 2
输出-1提示
1 k n 1001 times.length 6000times[i].length 31 ui, vi nui ! vi0 wi 100所有 (ui, vi) 对都 互不相同即不含重复边
解法一最短路径 - Dijkstra
class Solution {public int networkDelayTime(int[][] times, int n, int k) {// 创建一个邻接表来表示图// 每个节点映射到它所有邻接节点及其相应的传递时间MapInteger, Listint[] graph new HashMap();for (int[] time : times) {// 先加入key - uigraph.putIfAbsent(time[0], new ArrayList());// 后加入value - vi wigraph.get(time[0]).add(new int[] { time[1], time[2] });}// 小根堆优先队列 跟踪当前最短路径的节点及其到达时间PriorityQueueint[] minHead new PriorityQueue(Comparator.comparing(a - a[1]));minHead.offer(new int[] { k, 0 }); // {节点, 时间}// 跟踪到达每个节点的最短时间MapInteger, Integer minTime new HashMap();minTime.put(k, 0); // 节点时间// Dijkstra算法// 从节点k开始逐步扩展到邻接节点更新每个节点的最短传递时间while (!minHead.isEmpty()) {int[] current minHead.poll();int node current[0];int time current[1];// 遍历当前节点的所有邻接节点if (graph.containsKey(node)) {for (int[] neighbor : graph.get(node)) {int nextNode neighbor[0];int travelTime neighbor[1];// 计算到达邻接节点的时间int newTime time travelTime;// 如果通过当前节点到达某个邻接节点的时间比已知的时间更短则更新时间并将该邻接节点加入优先级队列if (newTime minTime.getOrDefault(nextNode, Integer.MAX_VALUE)) {minTime.put(nextNode, newTime);minHead.offer(new int[] { nextNode, newTime });}}}}// 找到所有节点的最大时间int maxTime 0;for (int i 1; i n; i) {// 如果存在未到达的节点则返回-1if (!minTime.containsKey(i)) {return -1;}maxTime Math.max(maxTime, minTime.get(i));}return maxTime;}
} 5. k站中转内最便宜的航班
有 n 个城市通过一些航班连接。给你一个数组 flights 其中 flights[i] [fromi, toi, pricei] 表示该航班都从城市 fromi 开始以价格 pricei 抵达 toi。
现在给定所有的城市和航班以及出发城市 src 和目的地 dst你的任务是找到出一条最多经过 k 站中转的路线使得从 src 到 dst 的 价格最便宜 并返回该价格。 如果不存在这样的路线则输出 -1。
示例 1
输入:
n 4, flights [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src 0, dst 3, k 1
输出: 700
解释: 城市航班图如上
从城市 0 到城市 3 经过最多 1 站的最佳路径用红色标记费用为 100 600 700。
请注意通过城市 [0, 1, 2, 3] 的路径更便宜但无效因为它经过了 2 站。示例 2
输入:
n 3, edges [[0,1,100],[1,2,100],[0,2,500]], src 0, dst 2, k 1
输出: 200
解释:
城市航班图如上
从城市 0 到城市 2 经过最多 1 站的最佳路径标记为红色费用为 100 100 200。示例 3
输入n 3, flights [[0,1,100],[1,2,100],[0,2,500]], src 0, dst 2, k 0
输出500
解释
城市航班图如上
从城市 0 到城市 2 不经过站点的最佳路径标记为红色费用为 500。提示
1 n 1000 flights.length (n * (n - 1) / 2)flights[i].length 30 fromi, toi nfromi ! toi1 pricei 10^4航班没有重复且不存在自环0 src, dst, k nsrc ! dst
解法一最短路径Dijkstra。执行耗时13ms
class Solution {public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {// 使用邻接表表示图ListListint[] graph new ArrayList();for (int i 0; i n; i) {graph.add(new ArrayList());}// 填充图for (int[] flight : flights) {graph.get(flight[0]).add(new int[] { flight[1], flight[2] });}// 小根堆元素为 {当前花费当前城市当前站数}PriorityQueueint[] minHeap new PriorityQueue(Comparator.comparing(a - a[0]));minHeap.offer(new int[] { 0, src, 0 });// 记录到达每个城市的最小费用并且要注意站数的限制int[][] minCost new int[n][k 2]; // k 2以考虑k站和出发城市// 初始化为最大值for (int i 0; i n; i) {Arrays.fill(minCost[i], Integer.MAX_VALUE);}minCost[src][0] 0; // 从src开始费用为0// Dijkstra核心逻辑while (!minHeap.isEmpty()) {int[] current minHeap.poll();int cost current[0]; // 当前花费int city current[1]; // 当前城市int stops current[2]; // 当前站数// 如果当前城市是目的地且经过站数不超过kif (city dst) {return cost;}// 如果经过的站数已经达到k1跳过if (stops k) {continue;}// 遍历当前城市的所有邻接城市for (int[] neighbor : graph.get(city)) {int nextCity neighbor[0]; // 目标城市int price neighbor[1]; // 价格int newCost cost price; // 新的总费用// 如果新费用低于当前记录更新并添加到优先队列if (newCost minCost[nextCity][stops 1]) {minCost[nextCity][stops 1] newCost;minHeap.offer(new int[] { newCost, nextCity, stops 1 });}}}// 如果没有找到有效路径返回-1return -1;}
}
解法二最短路径 - Bellman-Ford。执行耗时5ms public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {// 初始化源城市的最小费用为0其他城市为无穷大int[] prices new int[n];Arrays.fill(prices, Integer.MAX_VALUE);prices[src] 0;// 最多迭代k1次for (int i 0; i k; i) {int[] tempPrices Arrays.copyOf(prices,n);// 遍历所有的边for (int[] flight : flights) {int u flight[0], v flight[1], cost flight[2];if(prices[u] Integer.MAX_VALUE) {// 无法到达城市ucontinue;}// 更新到达每个城市的最小费用tempPrices[v] Math.min(tempPrices[v], prices[u] cost);}prices tempPrices;}return prices[dst] Integer.MAX_VALUE ? -1 : prices[dst];} 6. 课程表
你这个学期必须选修 numCourses 门课程记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出其中 prerequisites[i] [ai, bi] 表示如果要学习课程 ai 则 必须 先学习课程 bi 。
例如先修课程对 [0, 1] 表示想要学习课程 0 你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习如果可以返回 true 否则返回 false 。
示例 1
输入numCourses 2, prerequisites [[1,0]]
输出true
解释总共有 2 门课程。学习课程 1 之前你需要完成课程 0 。这是可能的。
示例 2
输入numCourses 2, prerequisites [[1,0],[0,1]]
输出false
解释总共有 2 门课程。学习课程 1 之前你需要先完成课程 0 并且学习课程 0 之前你还应先完成课程 1 。这是不可能的。提示
1 numCourses 20000 prerequisites.length 5000prerequisites[i].length 20 ai, bi numCoursesprerequisites[i] 中的所有课程对 互不相同
解法一拓扑排序
使用入度和队列来实现拓扑排序。每次从队列中取出一个课程并将其对应的后置课程的入度减一如果某个课程的入度减至0说明可以上这门课程。
class Solution {// 等同于在判断有向图是否存在环 - 拓扑排序public boolean canFinish(int numCourses, int[][] prerequisites) {int[] inDegree new int[numCourses];ListListInteger graph new ArrayList();for (int i 0; i numCourses; i) {graph.add(new ArrayList());}// 处理节点的先后关系for (int[] pre : prerequisites) {// 要想修读pre[0]先修pre[1] pre[1] - pre[0]graph.get(pre[1]).add(pre[0]);// 后置课程的入度加1inDegree[pre[0]];}QueueInteger queue new LinkedList();for (int i 0; i numCourses; i) {if (inDegree[i] 0) {queue.offer(i);}}int courseCompleted 0;// 节点出队while (!queue.isEmpty()) {int course queue.poll();courseCompleted;for (Integer neighbor : graph.get(course)) {// 节点出队后后置课程的入度减1inDegree[neighbor]--;if (inDegree[neighbor] 0) {queue.offer(neighbor);}}}return numCourses courseCompleted;}
}
解法二深度优先搜索DFS 递归标记 public boolean canFinish(int numCourses, int[][] prerequisites) {ListListInteger graph new ArrayList();for (int i 0; i numCourses; i) {graph.add(new ArrayList());}// 处理图中节点的先后关系for (int[] pre : prerequisites) {graph.get(pre[1]).add(pre[0]);}// 维护一个状态数组跟踪每个课程的访问状态 0-未访问 1-正在访问 2-已访问int[] visited new int[numCourses];for (int i 0; i numCourses; i) {// 判断是否存在环如果存在环则说明无法完成所有可能不存在拓扑排序if(hasCycle(graph, visited, i)) {return false;}}return true;}// 如果在DFS遍历的过程中再次访问到正在访问的节点则说明存在环无法完成所有的课程private boolean hasCycle(ListListInteger graph, int[] visited, int node) {if(visited[node] 1) return true; // 当前路径中存在环if(visited[node] 2) return false; // 已经访问过了无需再遍历visited[node] 1; // 正在访问for (Integer neighbor : graph.get(node)) {// 递归if(hasCycle(graph, visited, neighbor)) {return true;}}visited[node] 2; // 标记为已访问return false;} 7. 课程表Ⅱ
现在你总共有 numCourses 门课需要选记为 0 到 numCourses - 1。给你一个数组 prerequisites 其中 prerequisites[i] [ai, bi] 表示在选修课程 ai 前 必须 先选修 bi 。
例如想要学习课程 0 你需要先完成课程 1 我们用一个匹配来表示[0,1] 。
返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序你只要返回 任意一种 就可以了。如果不可能完成所有课程返回 一个空数组 。
示例 1
输入numCourses 2, prerequisites [[1,0]]
输出[0,1]
解释总共有 2 门课程。要学习课程 1你需要先完成课程 0。因此正确的课程顺序为 [0,1] 。示例 2
输入numCourses 4, prerequisites [[1,0],[2,0],[3,1],[3,2]]
输出[0,2,1,3]
解释总共有 4 门课程。要学习课程 3你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。
因此一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。
示例 3
输入numCourses 1, prerequisites []
输出[0]提示
1 numCourses 20000 prerequisites.length numCourses * (numCourses - 1)prerequisites[i].length 20 ai, bi numCoursesai ! bi所有[ai, bi] 互不相同
解法一拓扑排序入度队列。执行耗时7ms
class Solution {public int[] findOrder(int numCourses, int[][] prerequisites) {ListInteger order new ArrayList();int[] inDegree new int[numCourses];ListListInteger graph new ArrayList();for (int i 0; i numCourses; i) {graph.add(new ArrayList());}// 处理节点的先后关系for (int[] pre : prerequisites) {// 要想修读pre[0]先修pre[1] pre[1] - pre[0]graph.get(pre[1]).add(pre[0]);// 后置课程的入度加1inDegree[pre[0]];}QueueInteger queue new LinkedList();for (int i 0; i numCourses; i) {if (inDegree[i] 0) {queue.offer(i);}}// 节点出队while (!queue.isEmpty()) {int course queue.poll();order.add(course);for (Integer neighbor : graph.get(course)) {// 节点出队后后置课程的入度减1inDegree[neighbor]--;if (inDegree[neighbor] 0) {queue.offer(neighbor);}}}return order.size() numCourses ? order.stream().mapToInt(i - i).toArray() : new int[0];}
}
解法二深度优先搜索DFS。执行耗时5ms
class Solution {private ListListInteger graph;private int[] visited;private ListInteger order;public int[] findOrder(int numCourses, int[][] prerequisites) {// 初始化图和状态数组graph new ArrayList();for (int i 0; i numCourses; i) {graph.add(new ArrayList());}visited new int[numCourses];order new ArrayList();// 构建图for (int[] pre : prerequisites) {graph.get(pre[1]).add(pre[0]);}// DFS 遍历每门课程for (int i 0; i numCourses; i) {if (visited[i] 0) {if (!dfs(i)) {return new int[0]; // 返回空数组表示无法完成所有课程}}}// 结果反转Collections.reverse(order);return order.stream().mapToInt(i - i).toArray();}private boolean dfs(int course) {if (visited[course] 1) { // 发现环return false;}if (visited[course] 2) { // 已访问return true;}// 标记为正在访问visited[course] 1;for (int neighbor : graph.get(course)) {if (!dfs(neighbor)) {return false;}}// 标记为已访问并加入结果visited[course] 2;order.add(course);return true;}
}
