目录
- 6) 拓扑排序
- Kahn
- DFS
- 7) 最短路径
- Dijkstra
- Bellman-Ford
- Floyd-Warshall
- 8) 最小生成树
- Prim
- Kruskal
- 9) 不相交集合（并查集合）
- 基础
- 路径压缩
- Union By Size
- 图-相关题目
6) 拓扑排序
Kahn
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)); // +1
v2.edges = List.of(new Edge(v3)); // +1
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();
List<Vertex> graph = List.of(v1, v2, v3, v4, v5, v6, v7);
// 1. 统计每个顶点的入度
for (Vertex v : graph) {
for (Edge edge : v.edges) {
edge.linked.inDegree++;
}
}
/*for (Vertex vertex : graph) {
System.out.println(vertex.name + " " + vertex.inDegree);
}*/
// 2. 将入度为0的顶点加入队列
LinkedList<Vertex> queue = new LinkedList<>();
for (Vertex v : graph) {
if (v.inDegree == 0) {
queue.offer(v);
}
}
// 3. 队列中不断移除顶点，每移除一个顶点，把它相邻顶点入度减1，若减到0则入队
List<String> result = new ArrayList<>();
while (!queue.isEmpty()) {
Vertex poll = queue.poll();
// System.out.println(poll.name);
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);
}
}
}
}
DFS
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();
List<Vertex> graph = List.of(v1, v2, v3, v4, v5, v6, v7);
LinkedList<String> result = new LinkedList<>();
for (Vertex v : graph) {
if(v.status==0) {
dfs(v, result);
}
}
System.out.println(result);
}
private static void dfs(Vertex v, LinkedList<String> 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);
}
}
7) 最短路径
Dijkstra
Edsger Wybe Dijkstra
艾兹格·维布·迪克斯特拉（Edsger Wybe Dijkstra，/ˈdaɪkstrə/ DYKE-strə；荷兰语：[ˈɛtsxər ˈʋibə ˈdɛikstra] 1930年5月11日-2002年8月6日）是一位荷兰计算机科学家、程序员、软件工程师、系统科学家和科学散文家。他因对开发结构化编程语言做出的基础贡献而获得了1972年的图灵奖，并担任德克萨斯大学奥斯汀分校的斯伦贝谢百年计算机科学主席，任职时间从1984年到2000年。在他于2002年去世前不久，他因其在程序计算的自稳定性方面的工作而获得了ACM PODC分布式计算有影响力论文奖。为了纪念他，该年度奖项在接下来的一年更名为迪克斯特拉奖。
迪克斯特拉在计算机科学领域的贡献
- 最短路径算法，也称为迪克斯特拉算法，现代计算机科学本科课程中广泛教授
- Shunting yard算法
- THE OS 操作系统
- 银行家算法
- 用于协调多个处理器和程序的信号量构造
- 在分布式计算领域提出概念：自稳定性
算法描述：
- 将所有顶点标记为未访问。创建一个未访问顶点的集合。
- 为每个顶点分配一个临时距离值
- 对于我们的初始顶点，将其设置为零
- 对于所有其他顶点，将其设置为无穷大。
- 每次选择最小临时距离的未访问顶点，作为新的当前顶点
- 对于当前顶点，遍历其所有未访问的邻居，并更新它们的临时距离为更小
- 例如，1->6 的距离是 14，而1->3->6 的距离是11。这时将距离更新为 11
- 否则，将保留上次距离值
- 当前顶点的邻居处理完成后，把它从未访问集合中删除
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));
List<Vertex> graph = List.of(v1, v2, v3, v4, v5, v6);
dijkstra(graph, v1);
}
private static void dijkstra(List<Vertex> graph, Vertex source) {
ArrayList<Vertex> list = new ArrayList<>(graph);
source.dist = 0;
while (!list.isEmpty()) {
// 3. 选取当前顶点
Vertex curr = chooseMinDistVertex(list);
// 4. 更新当前顶点邻居距离
updateNeighboursDist(curr, list);
// 5. 移除当前顶点
list.remove(curr);
}
for (Vertex v : graph) {
System.out.println(v.name + " " + v.dist);
}
}
private static void updateNeighboursDist(Vertex curr, ArrayList<Vertex> 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;
}
}
}
}
private static Vertex chooseMinDistVertex(ArrayList<Vertex> 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->6 的距离是 14，而1->3->6 的距离是11。这时将距离更新为 11
- 否则，将保留上次距离值
- 当前顶点的邻居处理完成后，把它从队列中删除
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));
List<Vertex> graph = List.of(v1, v2, v3, v4, v5, v6);
dijkstra(graph, v1);
}
private static void dijkstra(List<Vertex> graph, Vertex source) {
PriorityQueue<Vertex> queue = new PriorityQueue<>(Comparator.comparingInt(v -> v.dist));
source.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) {
updateNeighboursDist(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 updateNeighboursDist(Vertex curr, PriorityQueue<Vertex> 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);
}
}
}
}
}
问题
按照 Dijkstra 算法，得出
- v1 -> v2 最短距离2
- v1 -> v3 最短距离1
- v1 -> v4 最短距离2
事实应当是
- v1 -> v2 最短距离2
- v1 -> v3 最短距离0
- v1 -> v4 最短距离1
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));
List<Vertex> 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();
List<Vertex> 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();
List<Vertex> graph = List.of(v1, v2, v3, v4);
bellmanFord(graph, v1);
}
private static void bellmanFord(List<Vertex> graph, Vertex source) {
source.dist = 0;
int size = graph.size();
// 1. 进行 顶点个数 - 1 轮处理
for (int i = 0; i < size - 1; i++) {
// 2. 遍历所有的边
for (Vertex s : graph) {
for (Edge edge : s.edges) {
// 3. 处理每一条边
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 + " " + (v.prev != null ? v.prev.name : "null"));
}
}
}
负环
如果在【顶点-1】轮处理完成后，还能继续找到更短距离，表示发现了负环
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));
List<Vertex> graph = List.of(v1, v2, v3, v4);
/*
直接连通
v1 v2 v3 v4
v1 0 ∞ -2 ∞
v2 4 0 3 ∞
v3 ∞ ∞ 0 2
v4 ∞ -1 ∞ 0
k=0 借助v1到达其它顶点
v1 v2 v3 v4
v1 0 ∞ -2 ∞
v2 4 0 2 ∞
v3 ∞ ∞ 0 2
v4 ∞ -1 ∞ 0
k=1 借助v2到达其它顶点
v1 v2 v3 v4
v1 0 ∞ -2 ∞
v2 4 0 2 ∞
v3 ∞ ∞ 0 2
v4 3 -1 1 0
k=2 借助v3到达其它顶点
v1 v2 v3 v4
v1 0 ∞ -2 0
v2 4 0 2 4
v3 ∞ ∞ 0 2
v4 3 -1 1 0
k=3 借助v4到达其它顶点
v1 v2 v3 v4
v1 0 -1 -2 0
v2 4 0 2 4
v3 5 1 0 2
v4 3 -1 1 0
*/
floydWarshall(graph);
}
static void floydWarshall(List<Vertex> 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); // v1 (v3)
Map<Vertex, 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); // v3
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(prev);
// 2）看能否借路到达其它顶点
/*
v2->v1 v1->v?
dist[1][0] + dist[0][0]
dist[1][0] + dist[0][1]
dist[1][0] + dist[0][2]
dist[1][0] + dist[0][3]
*/
for (int k = 0; k < size; k++) {
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
// dist[i][k] + dist[k][j] // i行的顶点，借助k顶点，到达j列顶点
// dist[i][j] // i行顶点，直接到达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];
}
}
}
// print(dist);
}
print(prev);
}
static void path(Vertex[][] prev, List<Vertex> graph, int i, int j) {
LinkedList<String> stack = new LinkedList<>();
System.out.print("[" + 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);
}
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(",", "[", "]")));
}
}
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(",", "[", "]")));
}
}
}
负环
如果在 3 层循环结束后，在 dist 数组的对角线处（i==j 处）发现了负数，表示出现了负环
8) 最小生成树
Prim
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));
List<Vertex> graph = List.of(v1, v2, v3, v4, v5, v6, v7);
prim(graph, v1);
}
static void prim(List<Vertex> graph, Vertex source) {
ArrayList<Vertex> list = new ArrayList<>(graph);
source.dist = 0;
while (!list.isEmpty()) {
Vertex min = chooseMinDistVertex(list);
updateNeighboursDist(min);
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(ArrayList<Vertex> 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;
}
}
Kruskal
public class Kruskal {
static class Edge implements Comparable<Edge> {
List<Vertex> vertices;
int start;
int end;
int weight;
public Edge(List<Vertex> 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;
}
@Override
public int compareTo(Edge o) {
return Integer.compare(this.weight, o.weight);
}
@Override
public 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");
List<Vertex> vertices = List.of(v1, v2, v3, v4, v5, v6, v7);
PriorityQueue<Edge> 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);
}
static void kruskal(int size, PriorityQueue<Edge> queue) {
List<Edge> result = new ArrayList<>();
DisjointSet set = new DisjointSet(size);
while (result.size() < size - 1) {
Edge poll = queue.poll();
int s = set.find(poll.start);
int e = set.find(poll.end);
if (s != e) {
result.add(poll);
set.union(s, e);
}
}
for (Edge edge : result) {
System.out.println(edge);
}
}
}
9) 不相交集合（并查集合）
基础
public class DisjointSet {
int[] s;
// 索引对应顶点
// 元素是用来表示与之有关系的顶点
/*
索引 0 1 2 3 4 5 6
元素 [0, 1, 2, 3, 4, 5, 6] 表示一开始顶点直接没有联系（只与自己有联系）
*/
public DisjointSet(int size) {
s = new int[size];
for (int i = 0; i < size; i++) {
s[i] = i;
}
}
// find 是找到老大
public int find(int x) {
if (x == s[x]) {
return x;
}
return find(s[x]);
}
// union 是让两个集合“相交”，即选出新老大，x、y 是原老大索引
public void union(int x, int y) {
s[y] = x;
}
@Override
public String toString() {
return Arrays.toString(s);
}
}
路径压缩
public int find(int x) { // x = 2
if (x == s[x]) {
return x;
}
return s[x] = find(s[x]); // 0 s[2]=0
}
Union By Size
public class DisjointSetUnionBySize {
int[] s;
int[] size;
public DisjointSetUnionBySize(int size) {
s = new int[size];
this.size = new int[size];
for (int i = 0; i < size; i++) {
s[i] = i;
this.size[i] = 1;
}
}
// find 是找到老大 - 优化：路径压缩
public int find(int x) { // x = 2
if (x == s[x]) {
return x;
}
return s[x] = find(s[x]); // 0 s[2]=0
}
// union 是让两个集合“相交”，即选出新老大，x、y 是原老大索引
public void union(int x, int y) {
// s[y] = x;
if (size[x] < size[y]) {
int t = x;
x = y;
y = t;
}
s[y] = x;
size[x] = size[x] + size[y];
}
@Override
public String toString() {
return "内容："+Arrays.toString(s) + "\n大小：" + Arrays.toString(size);
}
public static void main(String[] args) {
DisjointSetUnionBySize set = new DisjointSetUnionBySize(5);
set.union(1, 2);
set.union(3, 4);
set.union(1, 3);
System.out.println(set);
}
}
图-相关题目
| 题目编号 | 题目标题 | 算法思想 |
|---|---|---|
| 547 | 省份数量 | DFS、BFS、并查集 |
| 797 | 所有可能路径 | DFS、BFS |
| 1584 | 连接所有点的最小费用 | 最小生成树 |
| 743 | 网络延迟时间 | 单源最短路径 |
| 787 | K 站中转内最便宜的航班 | 单源最短路径 |
| 207 | 课程表 | 拓扑排序 |
| 210 | 课程表 II | 拓扑排序 |
