医院网站备案流程,模板板网站,net网站开发做手工简笔,贵阳做网站的公司目录 6) 拓扑排序KahnDFS 7) 最短路径DijkstraBellman-FordFloyd-Warshall 8) 最小生成树PrimKruskal 9) 不相交集合#xff08;并查集合#xff09;基础路径压缩Union By Size 图-相关题目 6) 拓扑排序 #mermaid-svg-MQhLsXiMwnlUL3q4 {font-family:trebuchet ms并查集合基础路径压缩Union By Size 图-相关题目 6) 拓扑排序 #mermaid-svg-MQhLsXiMwnlUL3q4 {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-MQhLsXiMwnlUL3q4 .error-icon{fill:#552222;}#mermaid-svg-MQhLsXiMwnlUL3q4 .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-MQhLsXiMwnlUL3q4 .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-MQhLsXiMwnlUL3q4 .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-MQhLsXiMwnlUL3q4 .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-MQhLsXiMwnlUL3q4 .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-MQhLsXiMwnlUL3q4 .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-MQhLsXiMwnlUL3q4 .marker{fill:#333333;stroke:#333333;}#mermaid-svg-MQhLsXiMwnlUL3q4 .marker.cross{stroke:#333333;}#mermaid-svg-MQhLsXiMwnlUL3q4 svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-MQhLsXiMwnlUL3q4 .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-MQhLsXiMwnlUL3q4 .cluster-label text{fill:#333;}#mermaid-svg-MQhLsXiMwnlUL3q4 .cluster-label span{color:#333;}#mermaid-svg-MQhLsXiMwnlUL3q4 .label text,#mermaid-svg-MQhLsXiMwnlUL3q4 span{fill:#333;color:#333;}#mermaid-svg-MQhLsXiMwnlUL3q4 .node rect,#mermaid-svg-MQhLsXiMwnlUL3q4 .node circle,#mermaid-svg-MQhLsXiMwnlUL3q4 .node ellipse,#mermaid-svg-MQhLsXiMwnlUL3q4 .node polygon,#mermaid-svg-MQhLsXiMwnlUL3q4 .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-MQhLsXiMwnlUL3q4 .node .label{text-align:center;}#mermaid-svg-MQhLsXiMwnlUL3q4 .node.clickable{cursor:pointer;}#mermaid-svg-MQhLsXiMwnlUL3q4 .arrowheadPath{fill:#333333;}#mermaid-svg-MQhLsXiMwnlUL3q4 .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-MQhLsXiMwnlUL3q4 .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-MQhLsXiMwnlUL3q4 .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-MQhLsXiMwnlUL3q4 .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-MQhLsXiMwnlUL3q4 .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-MQhLsXiMwnlUL3q4 .cluster text{fill:#333;}#mermaid-svg-MQhLsXiMwnlUL3q4 .cluster span{color:#333;}#mermaid-svg-MQhLsXiMwnlUL3q4 div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-MQhLsXiMwnlUL3q4 :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 网页基础 Java Web Java 基础 数据库 Spring框架 微服务框架 实战项目 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)); // 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);// 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的顶点加入队列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();
// 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();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);}
}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 操作系统银行家算法用于协调多个处理器和程序的信号量构造在分布式计算领域提出概念自稳定性 #mermaid-svg-jMU0CatDjcgUoad4 {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-jMU0CatDjcgUoad4 .error-icon{fill:#552222;}#mermaid-svg-jMU0CatDjcgUoad4 .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-jMU0CatDjcgUoad4 .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-jMU0CatDjcgUoad4 .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-jMU0CatDjcgUoad4 .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-jMU0CatDjcgUoad4 .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-jMU0CatDjcgUoad4 .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-jMU0CatDjcgUoad4 .marker{fill:#333333;stroke:#333333;}#mermaid-svg-jMU0CatDjcgUoad4 .marker.cross{stroke:#333333;}#mermaid-svg-jMU0CatDjcgUoad4 svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-jMU0CatDjcgUoad4 .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-jMU0CatDjcgUoad4 .cluster-label text{fill:#333;}#mermaid-svg-jMU0CatDjcgUoad4 .cluster-label span{color:#333;}#mermaid-svg-jMU0CatDjcgUoad4 .label text,#mermaid-svg-jMU0CatDjcgUoad4 span{fill:#333;color:#333;}#mermaid-svg-jMU0CatDjcgUoad4 .node rect,#mermaid-svg-jMU0CatDjcgUoad4 .node circle,#mermaid-svg-jMU0CatDjcgUoad4 .node ellipse,#mermaid-svg-jMU0CatDjcgUoad4 .node polygon,#mermaid-svg-jMU0CatDjcgUoad4 .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-jMU0CatDjcgUoad4 .node .label{text-align:center;}#mermaid-svg-jMU0CatDjcgUoad4 .node.clickable{cursor:pointer;}#mermaid-svg-jMU0CatDjcgUoad4 .arrowheadPath{fill:#333333;}#mermaid-svg-jMU0CatDjcgUoad4 .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-jMU0CatDjcgUoad4 .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-jMU0CatDjcgUoad4 .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-jMU0CatDjcgUoad4 .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-jMU0CatDjcgUoad4 .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-jMU0CatDjcgUoad4 .cluster text{fill:#333;}#mermaid-svg-jMU0CatDjcgUoad4 .cluster span{color:#333;}#mermaid-svg-jMU0CatDjcgUoad4 div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-jMU0CatDjcgUoad4 :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 7 9 14 9 2 15 11 6 1 2 3 4 5 6 算法描述
将所有顶点标记为未访问。创建一个未访问顶点的集合。为每个顶点分配一个临时距离值 对于我们的初始顶点将其设置为零对于所有其他顶点将其设置为无穷大。 每次选择最小临时距离的未访问顶点作为新的当前顶点对于当前顶点遍历其所有未访问的邻居并更新它们的临时距离为更小 例如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));ListVertex graph List.of(v1, v2, v3, v4, v5, v6);dijkstra(graph, v1);}private static void dijkstra(ListVertex graph, Vertex source) {ArrayListVertex 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, 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;}}}}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-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));ListVertex graph List.of(v1, v2, v3, v4, v5, v6);dijkstra(graph, v1);}private static void dijkstra(ListVertex graph, Vertex source) {PriorityQueueVertex 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, 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);}}}}}问题 #mermaid-svg-6bn0tobssaeuRzR9 {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-6bn0tobssaeuRzR9 .error-icon{fill:#552222;}#mermaid-svg-6bn0tobssaeuRzR9 .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-6bn0tobssaeuRzR9 .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-6bn0tobssaeuRzR9 .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-6bn0tobssaeuRzR9 .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-6bn0tobssaeuRzR9 .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-6bn0tobssaeuRzR9 .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-6bn0tobssaeuRzR9 .marker{fill:#333333;stroke:#333333;}#mermaid-svg-6bn0tobssaeuRzR9 .marker.cross{stroke:#333333;}#mermaid-svg-6bn0tobssaeuRzR9 svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-6bn0tobssaeuRzR9 .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-6bn0tobssaeuRzR9 .cluster-label text{fill:#333;}#mermaid-svg-6bn0tobssaeuRzR9 .cluster-label span{color:#333;}#mermaid-svg-6bn0tobssaeuRzR9 .label text,#mermaid-svg-6bn0tobssaeuRzR9 span{fill:#333;color:#333;}#mermaid-svg-6bn0tobssaeuRzR9 .node rect,#mermaid-svg-6bn0tobssaeuRzR9 .node circle,#mermaid-svg-6bn0tobssaeuRzR9 .node ellipse,#mermaid-svg-6bn0tobssaeuRzR9 .node polygon,#mermaid-svg-6bn0tobssaeuRzR9 .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-6bn0tobssaeuRzR9 .node .label{text-align:center;}#mermaid-svg-6bn0tobssaeuRzR9 .node.clickable{cursor:pointer;}#mermaid-svg-6bn0tobssaeuRzR9 .arrowheadPath{fill:#333333;}#mermaid-svg-6bn0tobssaeuRzR9 .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-6bn0tobssaeuRzR9 .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-6bn0tobssaeuRzR9 .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-6bn0tobssaeuRzR9 .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-6bn0tobssaeuRzR9 .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-6bn0tobssaeuRzR9 .cluster text{fill:#333;}#mermaid-svg-6bn0tobssaeuRzR9 .cluster span{color:#333;}#mermaid-svg-6bn0tobssaeuRzR9 div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-6bn0tobssaeuRzR9 :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 2 1 -2 1 v1 v2 v3 v4 按照 Dijkstra 算法得出
v1 - v2 最短距离2v1 - v3 最短距离1v1 - v4 最短距离2
事实应当是
v1 - v2 最短距离2v1 - v3 最短距离0v1 - 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));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();// 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));}}
}负环 #mermaid-svg-ibhu8X7I74Ao9UER {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-ibhu8X7I74Ao9UER .error-icon{fill:#552222;}#mermaid-svg-ibhu8X7I74Ao9UER .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-ibhu8X7I74Ao9UER .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-ibhu8X7I74Ao9UER .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-ibhu8X7I74Ao9UER .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-ibhu8X7I74Ao9UER .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-ibhu8X7I74Ao9UER .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-ibhu8X7I74Ao9UER .marker{fill:#333333;stroke:#333333;}#mermaid-svg-ibhu8X7I74Ao9UER .marker.cross{stroke:#333333;}#mermaid-svg-ibhu8X7I74Ao9UER svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-ibhu8X7I74Ao9UER .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-ibhu8X7I74Ao9UER .cluster-label text{fill:#333;}#mermaid-svg-ibhu8X7I74Ao9UER .cluster-label span{color:#333;}#mermaid-svg-ibhu8X7I74Ao9UER .label text,#mermaid-svg-ibhu8X7I74Ao9UER span{fill:#333;color:#333;}#mermaid-svg-ibhu8X7I74Ao9UER .node rect,#mermaid-svg-ibhu8X7I74Ao9UER .node circle,#mermaid-svg-ibhu8X7I74Ao9UER .node ellipse,#mermaid-svg-ibhu8X7I74Ao9UER .node polygon,#mermaid-svg-ibhu8X7I74Ao9UER .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-ibhu8X7I74Ao9UER .node .label{text-align:center;}#mermaid-svg-ibhu8X7I74Ao9UER .node.clickable{cursor:pointer;}#mermaid-svg-ibhu8X7I74Ao9UER .arrowheadPath{fill:#333333;}#mermaid-svg-ibhu8X7I74Ao9UER .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-ibhu8X7I74Ao9UER .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-ibhu8X7I74Ao9UER .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-ibhu8X7I74Ao9UER .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-ibhu8X7I74Ao9UER .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-ibhu8X7I74Ao9UER .cluster text{fill:#333;}#mermaid-svg-ibhu8X7I74Ao9UER .cluster span{color:#333;}#mermaid-svg-ibhu8X7I74Ao9UER div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-ibhu8X7I74Ao9UER :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 2 -4 1 1 v1 v2 v3 v4 如果在【顶点-1】轮处理完成后还能继续找到更短距离表示发现了负环
Floyd-Warshall #mermaid-svg-I5Wum918vI8hfQtY {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-I5Wum918vI8hfQtY .error-icon{fill:#552222;}#mermaid-svg-I5Wum918vI8hfQtY .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-I5Wum918vI8hfQtY .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-I5Wum918vI8hfQtY .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-I5Wum918vI8hfQtY .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-I5Wum918vI8hfQtY .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-I5Wum918vI8hfQtY .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-I5Wum918vI8hfQtY .marker{fill:#333333;stroke:#333333;}#mermaid-svg-I5Wum918vI8hfQtY .marker.cross{stroke:#333333;}#mermaid-svg-I5Wum918vI8hfQtY svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-I5Wum918vI8hfQtY .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-I5Wum918vI8hfQtY .cluster-label text{fill:#333;}#mermaid-svg-I5Wum918vI8hfQtY .cluster-label span{color:#333;}#mermaid-svg-I5Wum918vI8hfQtY .label text,#mermaid-svg-I5Wum918vI8hfQtY span{fill:#333;color:#333;}#mermaid-svg-I5Wum918vI8hfQtY .node rect,#mermaid-svg-I5Wum918vI8hfQtY .node circle,#mermaid-svg-I5Wum918vI8hfQtY .node ellipse,#mermaid-svg-I5Wum918vI8hfQtY .node polygon,#mermaid-svg-I5Wum918vI8hfQtY .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-I5Wum918vI8hfQtY .node .label{text-align:center;}#mermaid-svg-I5Wum918vI8hfQtY .node.clickable{cursor:pointer;}#mermaid-svg-I5Wum918vI8hfQtY .arrowheadPath{fill:#333333;}#mermaid-svg-I5Wum918vI8hfQtY .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-I5Wum918vI8hfQtY .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-I5Wum918vI8hfQtY .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-I5Wum918vI8hfQtY .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-I5Wum918vI8hfQtY .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-I5Wum918vI8hfQtY .cluster text{fill:#333;}#mermaid-svg-I5Wum918vI8hfQtY .cluster span{color:#333;}#mermaid-svg-I5Wum918vI8hfQtY div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-I5Wum918vI8hfQtY :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} -2 4 3 2 -1 v1 v3 v2 v4 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);/*直接连通v1 v2 v3 v4v1 0 ∞ -2 ∞v2 4 0 3 ∞v3 ∞ ∞ 0 2v4 ∞ -1 ∞ 0k0 借助v1到达其它顶点v1 v2 v3 v4v1 0 ∞ -2 ∞v2 4 0 2 ∞v3 ∞ ∞ 0 2v4 ∞ -1 ∞ 0k1 借助v2到达其它顶点v1 v2 v3 v4v1 0 ∞ -2 ∞v2 4 0 2 ∞v3 ∞ ∞ 0 2v4 3 -1 1 0k2 借助v3到达其它顶点v1 v2 v3 v4v1 0 ∞ -2 0v2 4 0 2 4v3 ∞ ∞ 0 2v4 3 -1 1 0k3 借助v4到达其它顶点v1 v2 v3 v4v1 0 -1 -2 0v2 4 0 2 4v3 5 1 0 2v4 3 -1 1 0*/floydWarshall(graph);}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); // v1 (v3)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); // v3if (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, ListVertex graph, int i, int j) {LinkedListString 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 数组的对角线处ij 处发现了负数表示出现了负环
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));ListVertex graph List.of(v1, v2, v3, v4, v5, v6, v7);prim(graph, v1);}static void prim(ListVertex graph, Vertex source) {ArrayListVertex 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(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;}
}Kruskal
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);}static void kruskal(int size, PriorityQueueEdge queue) {ListEdge 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;}Overridepublic String toString() {return Arrays.toString(s);}}路径压缩
public int find(int x) { // x 2if (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 2if (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];}Overridepublic 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、BFS1584连接所有点的最小费用最小生成树743网络延迟时间单源最短路径787K 站中转内最便宜的航班单源最短路径207课程表拓扑排序210课程表 II拓扑排序
