数据结构与算法--图论

目录

一 熟悉
图的表示
图的应用
 二 DFS和BFS
三 拓扑排序
 四 Dijkstra算法
 五 BellmanFord算法
一、基本原理
二、算法步调
三、算法特点
 六 Floyd-Warshall算法
一、算法概述
二、算法步调
三、算法实现
 七 最小生成树算法
一、Prim算法
二、 kruskal算法
一、算法思想
二、具体步调
三、核心问题
四、算法特点
五、应用场景

---

一 熟悉

在Java中，"图"（Graph）是一种非常紧张的数据结构，用于表示一组对象（称为顶点或节点）之间的连接关系。图可以是无向的（边没有方向）或有向的（边有方向）。图在办理许多算法问题中非常有用，如路径查找、网络流、最短路径、图遍历（如深度优先搜索DFS和广度优先搜索BFS）等。
图的表示

在Java中，图可以通过多种方式表示，此中两种常见的方法是：

• 邻接矩阵：利用二维数组来表示图。数组中的每个元素表示顶点对之间的连接状态（在有向图中，还大概表示边的权重或是否存在边）。如果顶点i和顶点j之间有一条边，则对应的数组元素非零（或者存储边的权重）。
  
• 邻接表：对于图中的每个顶点，都有一个列表来存储与该顶点相邻的全部顶点。这种方法比邻接矩阵更节省空间，特殊是当图很稀疏（即边的数目远小于顶点对数目的图）时。
  

图的应用

图的应用非常广泛，包罗但不限于：

• 社交网络分析：将用户作为顶点，用户之间的关系（如朋侪关系）作为边。
  
• 最短路径问题：如Dijkstra算法或A*算法，用于找到从一个顶点到另一个顶点的最短路径。
  
• 网络流问题：如最大流问题，用于确定通过图的流量网络的最大大概流量。
  
• 图的遍历：如深度优先搜索（DFS）和广度优先搜索（BFS），用于访问或搜索图的顶点。
  
• 舆图导航：将地点作为顶点，路径作为边，办理路径查找和规划问题。
  

通过学习和把握图的相干算法，你可以办理许多实际中遇到的复杂问题。

 二 DFS和BFS

1. public static void dfs(Vertex v) {
2.     dfs1(v);
3. }
5. public static void dfs1(Vertex v) {
6.     v.visited=true;
7.     System.out.println(v.name);
8.     for (Edge edge:v.edges) {
9.        Vertex v1=edge.linked;
10.        if (!v1.visited) {
11.           dfs1(v1);
12.        }
13.     }
14. }
16. public static void dfs2(Vertex v) {
17.     LinkedList<Vertex> stack=new LinkedList<Vertex>();
18.     stack.push(v);
19.     while(!stack.isEmpty()) {
20.        Vertex v1=stack.pop();
21.        v1.visited=true;
22.        System.out.println(v1.name);
23.        for(Edge edge:v1.edges) {
24.           Vertex vv=edge.linked;
25.           if (!vv.visited) {
26.              stack.push(vv);
27.           }
28.           }
29.        }
30.     }
35. public static void bfs(Vertex v) {
36.     LinkedList<Vertex> queue=new LinkedList<Vertex>();
37.     queue.offer(v);
38.     v.visited=true;
39.     while (!queue.isEmpty()) {
40.        Vertex vv=queue.poll();
41.        System.out.println(vv.name);
42.        for(Edge edge:vv.edges) {
43.           if (!edge.linked.visited) {
44.              edge.linked.visited=true;
45.              queue.offer(edge.linked);
46.           }
47.        }
48.     }
49.    
50.    
51.     }

复制代码

1. /**
2. * 边
3. */
4. public class Edge {
6.     Vertex linked;// 边指向的点
7.     int weight;
9.     public Edge(Vertex linked) {
10.         this(linked, 1);
11.     }
13.     public Edge(Vertex linked, int weight) {
14.         this.linked = linked;
15.         this.weight = weight;
16.     }
18. }

复制代码

1. /**
2. * 顶点
3. */
4. public class Vertex {
6.     String name;// 顶点的名称
7.     List<Edge> edges;// 与其相连的边
8.    
9.     boolean visited;
10.    
11.     public Vertex(String name) {
12.        this.name = name;
13.     }
14.    
15.     public String getName() {
16.        return name;
17.     }
18.    
19. }

复制代码

三 拓扑排序

• 首先求出图中全部节点的度（即与该节点相连的边的数目）。
  
• 将全部度小于等于1的节点入队。
  
• 当队列不空时，弹出队首元素，并将其相邻节点的度减1。如果相邻节点的度变为1，则将该相邻节点入队。
  

如果拓扑排序中出现环，则是无法将环中元素输出的
下图中，Spring输出后，微服务框架对应的入度从2减1 还有1 则不会加入队列中 循环结束了
判定是否有环的方法:
判定已经访问的节点数是否等于图中的总节点数。如果相等，阐明无环；否则，有环。

1. public class TopologicalSort {
2.     public static void main(String[] args) {
3.        Vertex v1 = new Vertex("网页基础");
4.        Vertex v2 = new Vertex("Java基础");
5.        Vertex v3 = new Vertex("JavaWeb");
6.        Vertex v4 = new Vertex("Spring框架");
7.        Vertex v5 = new Vertex("微服务框架");
8.        Vertex v6 = new Vertex("数据库");
9.        Vertex v7 = new Vertex("实战项目");
11.        v1.edges = List.of(new Edge(v3));
12.        v2.edges = List.of(new Edge(v3));
13.        v3.edges = List.of(new Edge(v4));
14.        v4.edges = List.of(new Edge(v5));
15.        v5.edges = List.of(new Edge(v7));
16.        v6.edges = List.of(new Edge(v4));
17.        v7.edges = List.of();
19.        List<Vertex> graph = List.of(v1, v2, v3, v4, v5, v6, v7);
21.        // 1.统计每个顶点的入度
22.        for (Vertex vertex : graph) {
23.           for (Edge edge : vertex.edges) {
24.              edge.linked.inDegree++;
25.           }
26.        }
27.        // 2. 找到入度为0的顶点，输出，并将其邻接点的入度减1
28.        LinkedList<Vertex> queue = new LinkedList<>();
29.        for (Vertex vertex : graph) {
30.           if (vertex.inDegree == 0) {
31.              queue.offer(vertex);
32.           }
33.        }
34.        // 3.队列中不断移除顶点，移除顶点的邻接点的入度--，并将入度为0的顶点加入队列
35.        while (!queue.isEmpty()) {
36.           Vertex pop = queue.poll();
37.           System.out.println(pop.name);
38.           for (Edge edge : pop.edges) {
39.              edge.linked.inDegree--;
40.              if (edge.linked.inDegree == 0) {
41.                 queue.offer(edge.linked);
42.              }
43.           }
44.        }
45.     }
46. }

复制代码

DFS深度遍历实现拓扑排序
给顶点加上三个状态 0未访问 1已访问 2正访问

• 
  
  
  
  • 利用DFS遍历图，并为每个节点设置三种状态：白色（未访问）、灰色（正在访问）、黑色（已访问完毕）。
    
  • 如果在遍历过程中发现某个节点有一条边指向灰色节点（即该节点的某个子女节点），并且这个灰色节点不是上一步访问的节点，则阐明存在环。
    
  
  

1. LinkedList<String> stack = new LinkedList<>();
2.     for (Vertex vertex : graph) {
3.        dfs(vertex, stack);
4.     }
5.     while (!stack.isEmpty()) {
6.        System.out.println(stack.poll());
7.     }
8. }
10. public static void dfs(Vertex v, LinkedList<String> stack){
11.     if (v.status==1){
12.        // 已经被访问过了
13.        return;
14.     }
15.     if (v.status==2){
16.        throw new IllegalStateException("有环");
17.     }
18.     v.status=2; // 在访问
19.     for (Edge edge : v.edges) {
20.        dfs(edge.linked, stack);
21.     }
22.     v.status=1;
23.     stack.push(v.name);
24.    
25. }

复制代码

 
 四 Dijkstra算法

迪克斯特拉 单源最短路径算法
思绪：

• 利用邻接表来构建图模型，每个点对应其全部邻接点，定义一个边的类，包含to(尽头)，和weight(权重)
  
• 定义一个dis[]，表示到每个点的距离，初始时到每个点的距离为Integer.MaxValue();
  
• dis[start]=0,到起点的距离为0
  
• 每次从未访问的节点中选取一个距离起点最近的节点（通过优先队列实现）。然后遍历这个节点的邻接点，更新起点到新的节点的距离，如果新的距离<原来的距离，把新的节点加入到优先队列中
  
• 利用visited数组标记哪个节点已经访问过，如果该节点已经访问过，则不再访问
  

时间复杂度: O((n+m)⋅log⁡n)，此中 n 是节点数，m是边数。

• 
  
  
  
  • 邻接表创建的复杂度是 O(m)。
    
  • 优先队列每次操作的复杂度是 log⁡n，最多会处理 m+n次操作。
    
  
  

空间复杂度: O(n+m)用于存储图的邻接表和辅助数组。

1. package TuLun;
3. import java.io.BufferedReader;
4. import java.io.IOException;
5. import java.io.InputStreamReader;
6. import java.io.StreamTokenizer;
7. import java.util.*;
9. public class P4779 {
10.     public static void main(String[] args) throws IOException {
11.         StreamTokenizer st=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
12.         st.nextToken();
13.         int n =(int)st.nval;
14.         st.nextToken();
15.         int m = (int)st.nval;
16.         st.nextToken();
17.         int s = (int)st.nval;
18.         List<edge>[]graphs=new List[n+1];
19.         for (int i = 0; i < graphs.length; i++) {
20.             graphs[i]=new ArrayList<>();
21.         }
22.         for (int i = 1; i <= m; i++) {
23.             st.nextToken();
24.             int u = (int)st.nval;
25.             st.nextToken();
26.             int v = (int)st.nval;
27.             st.nextToken();
28.             long w = (int)st.nval;
29.             graphs[u].add(new edge(v,w));
30.         }
31.         long[]dis=new long[n+1];
32.         for (int i = 1; i <= n; i++) {
33.             dis[i]=Integer.MAX_VALUE;
34.         }
35.         dis[s]=0;
36.        PriorityQueue<long[]>queue=new PriorityQueue<>(Comparator.comparingLong(longs -> longs[1]));
37.        // 到哪个节点，距离
38.        queue.add(new long[]{s,0});
39.        boolean[]visited=new boolean[n+1];
40.        while (!queue.isEmpty()){
41.            long[] arr = queue.poll();
42.            int node = (int)arr[0];
43.            long curDis = arr[1];
45.            if (visited[node])continue;
46.            visited[node]=true;
48.            // 遍历该节点的邻接点 然后更新start到其邻接点的距离
49.            for (edge edge : graphs[node]) {
50.                int nextNode = edge.to;
51.                long nextDis = edge.weight;
52.                if (dis[nextNode]>curDis+nextDis){
53.                    dis[nextNode]=curDis+nextDis;
54.                    queue.offer(new long[]{nextNode,dis[nextNode]});
55.                }
56.            }
57.        }
58.         for (int i = 1; i <=n ; i++) {
59.             System.out.print(dis[i]+" ");
60.         }
61.     }
63.     public static class edge{
64.         int to;
65.         long weight;
67.         public edge(int to, long weight) {
68.             this.to = to;
69.             this.weight = weight;
70.         }
71.     }
73. }

复制代码

 五 BellmanFord算法

BellmanFord可以处理负边，Dijkstra不可以
BellmanFord，即贝尔曼-福特算法（Bellman–Ford algorithm），是一种用于盘算带权有向图中单源最短路径（SSSP：Single-Source Shortest Path）的算法。以下是对BellmanFord算法的具体表明：
一、基本原理

贝尔曼-福特算法通过多次迭代（松弛操作）来逐步迫近从原点到图中全部其他节点的最短路径。算法的核心在于对每一条边举行多次查抄，看是否存在通过这条边可以收缩从源点到某个节点的路径的环境。
二、算法步调

• 初始化：将全部节点到源点的距离初始化为无穷大（除了原点到自身的距离为0）。
  
• 松弛操作：对图中的每一条边举行多次（通常是V-1次，V是节点数）松弛操作。在每次松弛操作中，对于每一条边(u, v)，如果通过u到达v的路径比当前已知的从源点到v的路径更短，则更新v的距离。
  
• 查抄负权环：在完成V-1次松弛操作后，再举行一次额外的松弛操作。如果在这次操作中还能更新某个节点的距离，则阐明图中存在负权环，因为负权环答应无限次地减少路径的总权重。
  

三、算法特点

• 支持负权边：与Dijkstra算法差别，Bellman-Ford算法能够处理图中存在负权边的环境，这是其最显著的长处之一。
  
• 检测负权回路：在完玉成部边的松弛操作后，算法还能通过额外的步调检测图中是否存在负权回路（即负权环），这是其他某些算法所不具备的功能。
  
• 实现简朴：算法的实现相对直观，轻易理解和编程实现。
  
• 时间复杂度较高：Bellman-Ford算法的时间复杂度为O(VE)，此中V是顶点数，E是边数。在边数较多的图中，算法的实行服从较低。
  
• 无法处理负权环：虽然算法能检测负权环，但在图中存在负权环时，算法无法给出正确的最短路径解，因为负权环会导致路径长度无限减小。
  

1. public static void  BellmanFord(List<Vertex> graph) {
2.     // 1.进行顶点个数-1轮处理
3.     for (int i = 0; i < graph.size()-1; i++) {
4.         // 2.遍历所有边
5.         for (Vertex s : graph) {
6.             for (Edge edge : s.edges) {
7.                 // 3. 如果存在更短路径，更新路径
8.                 Vertex linked = edge.linked;
9.                 if (s.distance!=Integer.MAX_VALUE && s.distance+edge.weight< linked.distance){
10.                    linked.distance = s.distance+edge.weight;
11.                    linked.prev = s;
12.                 }
13.             }
14.         }
15.     }

复制代码

1. package TuLun;
3. import java.io.BufferedReader;
4. import java.io.IOException;
5. import java.io.InputStreamReader;
6. import java.io.StreamTokenizer;
7. import java.util.ArrayList;
8. import java.util.Arrays;
9. import java.util.List;
11. public class P3385 {
12.     public static void main(String[] args) throws IOException {
13.         StreamTokenizer st=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
14.         st.nextToken();
15.         int t = (int) st.nval;
16.         for (int i = 0; i < t; i++) {
17.             st.nextToken();
18.             int n= (int) st.nval;
19.             st.nextToken();
20.             int m= (int) st.nval;
21.             List<Edge>[]graphs=new List[n+1];
22.             for (int j = 1; j <=n ; j++) {
23.                 graphs[j]=new ArrayList<>();
24.             }
25.             for (int j = 0; j < m; j++) {
26.                 st.nextToken();
27.                 int u= (int) st.nval;
28.                 st.nextToken();
29.                 int v= (int) st.nval;
30.                 st.nextToken();
31.                 int w= (int) st.nval;
32.                 if (w>=0){
33.                     graphs[u].add(new Edge(v,w));
34.                     graphs[v].add(new Edge(u,w));
35.                 }else{
36.                     graphs[u].add(new Edge(v,w));
37.                 }
38.             }
39.             long[]dis=new long[n+1];
40.             Arrays.fill(dis,Integer.MAX_VALUE);
41.             dis[1]=0;
42.             for (int j = 0; j < n-1; j++) {
43.                 for (int k = 1; k <=n; k++) {
44.                     for (Edge edge : graphs[k]) {
45.                         int nextNode = edge.to;
46.                         long nextDis=edge.weight;
47.                         if (dis[k]!=Integer.MAX_VALUE  && dis[nextNode]>dis[k]+nextDis){
48.                             dis[nextNode]=dis[k]+nextDis;
49.                         }
50.                     }
51.                 }
52.             }
53.             boolean flag=false;
54.             for (int k = 1; k <=n; k++) {
55.                 for (Edge edge : graphs[k]) {
56.                     int nextNode = edge.to;
57.                     long nextDis=edge.weight;
58.                     if (dis[k]!=Integer.MAX_VALUE && dis[nextNode]>dis[k]+nextDis){
59.                         flag=true;
60.                         break;
61.                     }
62.                 }
63.                 if (flag)break;
64.             }
65.             if (flag){
66.                 System.out.println("YES");
67.             }else{
68.                 System.out.println("NO");
69.             }
70.         }
72.     }
73.     public static class Edge{
74.         int to;
75.         long weight;
77.         public Edge(int to, long weight) {
78.             this.to = to;
79.             this.weight = weight;
80.         }
81.     }
82. }

复制代码

 六 Floyd-Warshall算法

FloydWarshall，即Floyd-Warshall算法，是一种用于求解图中求解任意两点间的最短路径的动态规划算法。以下是对Floyd-Warshall算法的具体表明：
一、算法概述

Floyd-Warshall算法可以在有向图或无向图中探求全部顶点对之间的最短路径。它不仅能够处理正权边，还能处理负权边，但图中不能包含负权循环。该算法的时间复杂度为O(V2)。
二、算法步调

• 初始化：创建一个n×n的距离矩阵D，此中D[j]表示从顶点i到顶点j的最短路径的长度。如果(i,j)之间没有直接的边，则D[j]设置为无穷大（或某个充足大的数来表示不可达）。对于全部的顶点i，D=0，表示从自身到自身的距离为0。
  
• 动态规划过程：对于每一个中间顶点k，更新距离矩阵D。具体来说，对于每一对顶点(i, j)，如果D[j] > D[k] + D[k][j]，则更新D[j]为D[k] + D[k][j]。这相当于查抄是否可以通过k作为中间顶点来获得从i到j的更短路径。
  
• 迭代：重复上述动态规划过程，直到全部大概的中间顶点都被考虑过。
  
• 效果：最终，距离矩阵D中的每个元素D[j]将包含从顶点i到顶点j的最短路径的长度。
  

三、算法实现

Floyd-Warshall算法的实现通常利用嵌套的三层循环来遍历全部节点对和中间节点。
查验是否有环的方法：

• 在dist中判定对角线上是否存在负数
  
• 对角线是本身到本身最小应该为0
  
• 绕了一圈回到本身<0
  

1. public class FloydWarshall {
2.     public static void main(String[] args) {
3.         Vertex v1 = new Vertex("v1");
4.         Vertex v2 = new Vertex("v2");
5.         Vertex v3 = new Vertex("v3");
6.         Vertex v4 = new Vertex("v4");
8.         v1.edges = List.of(new Edge(v3,-2));
9.         v2.edges = List.of(new Edge(v1,4),new Edge(v3,3));
10.         v3.edges = List.of(new Edge(v4,2));
11.         v4.edges = List.of(new Edge(v2,-1));
13.         List<Vertex> graph = List.of(v1,v2,v3,v4);
14.         floydWarshall(graph);
16.     }
18.     /**
19.      *      v1 v2 v3 v4
20.      *   v1
21.      *   v2
22.      *   v3
23.      *   v4
24.      * @param graph
25.      */
26.     public static void floydWarshall(List<Vertex> graph){
27.         long[][] dist = new long[graph.size()][graph.size()];
28.         Vertex[][] prev = new Vertex[graph.size()][graph.size()];  // 路径
29.         // 1.初始化距离
30.         for (int i = 0; i < graph.size(); i++) {
31.             // i起点 j终点
32.             Map<Vertex, Integer> map = graph.get(i).edges.stream().collect(Collectors.toMap(k -> k.linked, v -> v.weight));
33.             for (int j = 0; j < graph.size(); j++) {
34.                 if (i == j){
35.                     // 自己到自己距离为0
36.                     dist[i][j] = 0;
37.                 }else{
38.                     // 判断起点是否和终点连接 不连接则距离无穷大
39.                     Integer orDefault = map.getOrDefault(graph.get(j), Integer.MAX_VALUE);
40.                     dist[i][j] = orDefault;
41.                     // i到j j的上一个应该为i
42.                     prev[i][j] = graph.get(i);
43.                 }
44.             }
45.         }
46.         // 2.借助中间点k从起点i到达结束点j 或者也可以从起点i出发借助中间点k到结束点j i,j,k都是一轮循环
47.         // 2.1有几个点则进行几轮借助 每个点都去借助一轮别的点
48.         for (int k = 0; k < graph.size(); k++) {
49.             // 2.2 i 起点
50.             for (int i = 0; i < graph.size(); i++) { // 多源的 所以起点也要换 每个顶点当一次起点
51.                 // 2.3 j终点
52.                 for (int j = 0; j < graph.size(); j++) {
53.                     if (dist[i][k]!=Integer.MAX_VALUE && dist[k][j]!=Integer.MAX_VALUE
54.                             && dist[i][k]+dist[k][j]<dist[i][j]){
55.                         dist[i][j] =dist[i][k]+dist[k][j];
56.                         prev[i][j]=graph.get(k);
57.                     }
58.                 }
59.             }
60.         }
62.         // 3.打印结果
63. //        for (int i = 0; i < graph.size(); i++) {
64. //            for (int j = 0; j < graph.size(); j++) {
65. //                System.out.print(dist[i][j]+" ");
66. //            }
67. //            System.out.println();
68. //        }
69.         for (int i = 0; i < graph.size(); i++) {
70.             for (int j = 0; j < graph.size(); j++) {
71.                 path(prev,graph,i,j);
72.             }
74.         }
76.     }
78.     private static void path(Vertex[][] prev, List<Vertex> graph,int i,int j) {
79.         LinkedList<String> stack = new LinkedList<>();
80.         System.out.print("["+graph.get(i).name+","+graph.get(j).name+"]  " );
81.         stack.push(graph.get(j).name);
82.         while(i!=j){
83.             Vertex vertex = prev[i][j];
84.             stack.push(vertex.name);
85.             j = graph.indexOf(vertex);
86.         }
87.         System.out.println(String.join("->", stack));
92.     }
95. }

复制代码

 七 最小生成树算法

一、Prim算法

Prim算法是一种用于求解最小生成树（Minimum Spanning Tree, MST）的经典算法。最小生成树是指在一个加权无向图中，找到一棵包含全部顶点且边权值之和最小的树。Prim算法的基本思想是从图的某一顶点开始，逐步扩展生成树，每次选择一条连接生成树顶点聚集和未连接顶点聚集中权值最小的边，直到生成树包含全部顶点。

1. public static void main(String[] args) {
2.     Vertex v1 = new Vertex("v1");
3.     Vertex v2 = new Vertex("v2");
4.     Vertex v3 = new Vertex("v3");
5.     Vertex v4 = new Vertex("v4");
6.     Vertex v5 = new Vertex("v5");
7.     Vertex v6 = new Vertex("v6");
9.     v1.edges = List.of(new Edge(v3,9),new Edge(v2,7),new Edge(v6,14));
10.     v2.edges = List.of(new Edge(v4,15));
11.     v3.edges = List.of(new Edge(v4,11),new Edge(v6,2));
12.     v4.edges = List.of(new Edge(v5,6));
13.     v5.edges = List.of();
14.     v6.edges = List.of(new Edge(v5,9));
17.     List<Vertex> graph = List.of(v1, v2, v3, v4, v5, v6);
18.     // 1.创建一个优先级队列，按照距离进行排序，默认为小顶堆
19.     PriorityQueue<Vertex> queue = new PriorityQueue<>(Comparator.comparingInt(v->v.distance));
20.     // 2.为每个顶点初始化距离
21.     v1.distance = 0;
22.     for (Vertex vertex : graph) {
23.         if (vertex != v1) {
24.             vertex.distance = Integer.MAX_VALUE;
25.         }
26.     }
27.     for (Vertex vertex : graph) {
28.         queue.offer(vertex);
29.     }
31.     // 3.每次选择距离最小的顶点，作为新的当前顶点
32.     while (!queue.isEmpty()) {
33.         // 3.1 取出距离最小的顶点
34.         Vertex current = queue.peek();
35.         // 3.2 更新距离
36.         if (!current.visited){
37.             updateDistance(current, queue);
38.             current.visited = true;
39.         }
40.         // 3.3 从队列中删除该节点
41.         queue.poll();
42.     }
44.     // 4.打印路径
45.     for (Vertex vertex : graph) {
46.         System.out.println(vertex.name +" "+ vertex.distance+" "+ (vertex.prev == null ? "null" : vertex.prev.name));
47.     }
49. }
50. public static void updateDistance(Vertex current, PriorityQueue<Vertex> queue) {
51.     // 3.3 遍历当前顶点的邻居
52.     for (Edge edge : current.edges) {
53.         Vertex n = edge.linked;
54.         if (!n.visited){
55.             int dist=edge.weight;
56.             // 3.4 如果距离小于邻居的距离，则更新邻居的距离
57.             if (dist < n.distance) {
58.                 n.distance = dist;
59.                 // 更新该节点的距离
60.                 queue.offer(n);
61.                 n.prev = current;
62.             }
63.         }
66.     }
67. }

复制代码

二、 kruskal算法

Kruskal算法，即克鲁斯卡尔算法，是一种用于在加权连通图中探求最小生成树的算法。以下是对Kruskal算法的具体表明：
一、算法思想

Kruskal算法的基本思想是按照权值从小到大的次序选择n-1条边，并保证这n-1条边不构成回路，从而构成一棵极小连通子图，该连通子图中n-1条边上权值之和达到最小，则称其为连通网的最小生成树。
二、具体步调

• 从加权图中找出全部的边，初始时全部边都不属于最小生成树。
  
• 将全部的边按照权值从小到大举行排序。
  
• 从排序后的边中依次取出边，并判定该边及其连接的两个顶点加入最小生成树是否会形成环路。
  

• 
  
  
  
  • 若形成环路，则跳过此边，继续取下一条边举行判定。
    
  • 若不形成环路，则将该边及其连接的两个顶点加入最小生成树。
    
  
  

• 重复上述步调，直至全部顶点均连接在一起，并且没有形成环路时，最小生成树就找到了。
  

三、核心问题

• 如何对图的全部边按照权值大小举行排序？
  

• 
  
  
  
  • 应对策略：接纳排序算法（如快速排序、归并排序等）对图的全部边按照权值大小举行排序。
    
  
  

• 如何判定边及其顶点加入最小生成树是否会形成回路？
  

• 
  
  
  
  • 应对策略：可以利用并查集（Union Find）数据结构来判定。在将边加入最小生成树之前，先判定该边的两个顶点是否已经在同一个聚集中（即是否已经连通）。若已经连通，则加入该边会形成回路；若未连通，则可以将该边加入最小生成树，并将两个顶点所在的聚集归并。
    
  
  

四、算法特点

• Kruskal算法是将边作为操作对象，当加权图的边越多，要处理的边也越多，则算法的时间复杂度就越高；而顶点的数目对算法的时间复杂度无影响。因此，Kruskal算法适合处理稀疏图（边较少的图）。
  
• Kruskal算法的时间复杂度重要取决于排序操作，一样平常为O(mlogm)，此中m为边的数目。
  

五、应用场景

Kruskal算法广泛应用于网络设计、交通规划、电路布线等领域中，用于求解最小生成树问题。比方，在构建通信网络时，需要选择权值（如距离、成本等）最小的边来连接各个节点，以保证网络的连通性和最小成本。
综上所述，Kruskal算法是一种高效、实用的求解最小生成树的算法，特殊实用于处理稀疏图的环境。

1. static void kruskal(int size, PriorityQueue<Edge> queue){
2.     List<Edge> edges = new ArrayList<>();
3.     DisjoinSet set=new DisjoinSet(size);
4.     while (!queue.isEmpty()){
5.         Edge poll = queue.poll();
6.         int i = set.find(poll.start);// 找到起点的老大
7.         int j = set.find(poll.end);// 找到终点的老大
8.         if (i!=j){
9.             // 老大索引不一致 不是一个老大
10.             edges.add(poll);
11.             set.union(i,j);// 相交 给原本的两个老大整个共同的新老大
12.         }
13.     }
14. }

复制代码

1. package com.shutu.Graph;
3. public class DisjoinSet {
5.     int[] s;
7.     // 初始化，n个元素的并查集，初始每个元素都是一个集合，自身为老大
8.     // 索引代表顶点
9.     // 值代表有关系的顶点
10.     public DisjoinSet(int n) {
11.         s = new int[n];
12.         for (int i = 0; i < n; i++) {
13.             s[i] = i;
14.         }
15.     }
17.     // 找到老大是谁
18.     public int find(int x) {
19.         if (s[x] == x) {
20.             return x;
21.         }
22.         return find(s[x]);
23.         // 路径压缩 return s[x]=find(s[x]);
24.         
25.     }
27.     // 是让两个集合“相交”，即选出新老大，x、y是原老大索引
28.     public void union(int x, int y) {
29.         s[y]=x;
30.     }
35. }

复制代码

初始图

连接一些权重比较小的边 给每个点找到本身的老大 两个顶点老大雷同则阐明已相连

路径压缩 再找到他们的老大后，直接将其值改为老大值

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。