目录
一 认识
在Java中，"图"（Graph）是一种非常重要的数据结构，用于表示一组对象（称为顶点或节点）之间的连接关系。图可以是无向的（边没有方向）或有向的（边有方向）。图在解决许多算法问题中非常有用，如路径查找、网络流、最短路径、图遍历（如深度优先搜索DFS和广度优先搜索BFS）等。
图的表示
在Java中，图可以通过多种方式表示，其中两种常见的方法是：
- 邻接矩阵：使用二维数组来表示图。数组中的每个元素表示顶点对之间的连接状态（在有向图中，还可能表示边的权重或是否存在边）。如果顶点i和顶点j之间有一条边，则对应的数组元素非零（或者存储边的权重）。
- 邻接表：对于图中的每个顶点，都有一个列表来存储与该顶点相邻的所有顶点。这种方法比邻接矩阵更节省空间，特别是当图很稀疏（即边的数量远小于顶点对数量的图）时。
图的应用
图的应用非常广泛，包括但不限于：
- 社交网络分析：将用户作为顶点，用户之间的关系（如朋友关系）作为边。
- 最短路径问题：如Dijkstra算法或A*算法，用于找到从一个顶点到另一个顶点的最短路径。
- 网络流问题：如最大流问题，用于确定通过图的流量网络的最大可能流量。
- 图的遍历：如深度优先搜索（DFS）和广度优先搜索（BFS），用于访问或搜索图的顶点。
- 地图导航：将地点作为顶点，路径作为边，解决路径查找和规划问题。
通过学习和掌握图的相关算法，你可以解决许多实际中遇到的复杂问题。
二 DFS和BFS
public static void dfs(Vertex v) {
dfs1(v);
}
public static void dfs1(Vertex v) {
v.visited=true;
System.out.println(v.name);
for (Edge edge:v.edges) {
Vertex v1=edge.linked;
if (!v1.visited) {
dfs1(v1);
}
}
}
public static void dfs2(Vertex v) {
LinkedList<Vertex> stack=new LinkedList<Vertex>();
stack.push(v);
while(!stack.isEmpty()) {
Vertex v1=stack.pop();
v1.visited=true;
System.out.println(v1.name);
for(Edge edge:v1.edges) {
Vertex vv=edge.linked;
if (!vv.visited) {
stack.push(vv);
}
}
}
}
public static void bfs(Vertex v) {
LinkedList<Vertex> queue=new LinkedList<Vertex>();
queue.offer(v);
v.visited=true;
while (!queue.isEmpty()) {
Vertex vv=queue.poll();
System.out.println(vv.name);
for(Edge edge:vv.edges) {
if (!edge.linked.visited) {
edge.linked.visited=true;
queue.offer(edge.linked);
}
}
}
}/**
* 边
*/
public class Edge {
Vertex linked;// 边指向的点
int weight;
public Edge(Vertex linked) {
this(linked, 1);
}
public Edge(Vertex linked, int weight) {
this.linked = linked;
this.weight = weight;
}
}/**
* 顶点
*/
public class Vertex {
String name;// 顶点的名称
List<Edge> edges;// 与其相连的边
boolean visited;
public Vertex(String name) {
this.name = name;
}
public String getName() {
return name;
}
}三 拓扑排序
- 首先求出图中所有节点的度（即与该节点相连的边的数量）。
- 将所有度小于等于1的节点入队。
- 当队列不空时，弹出队首元素，并将其相邻节点的度减1。如果相邻节点的度变为1，则将该相邻节点入队。
如果拓扑排序中出现环，则是无法将环中元素输出的
下图中，Spring输出后，微服务框架对应的入度从2减1 还有1 则不会加入队列中 循环结束了
判断是否有环的方法:
判断已经访问的节点数是否等于图中的总节点数。如果相等，说明无环；否则，有环。
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));
v2.edges = List.of(new Edge(v3));
v3.edges = List.of(new Edge(v4));
v4.edges = List.of(new Edge(v5));
v5.edges = List.of(new Edge(v7));
v6.edges = List.of(new Edge(v4));
v7.edges = List.of();
List<Vertex> graph = List.of(v1, v2, v3, v4, v5, v6, v7);
// 1.统计每个顶点的入度
for (Vertex vertex : graph) {
for (Edge edge : vertex.edges) {
edge.linked.inDegree++;
}
}
// 2. 找到入度为0的顶点，输出，并将其邻接点的入度减1
LinkedList<Vertex> queue = new LinkedList<>();
for (Vertex vertex : graph) {
if (vertex.inDegree == 0) {
queue.offer(vertex);
}
}
// 3.队列中不断移除顶点，移除顶点的邻接点的入度--，并将入度为0的顶点加入队列
while (!queue.isEmpty()) {
Vertex pop = queue.poll();
System.out.println(pop.name);
for (Edge edge : pop.edges) {
edge.linked.inDegree--;
if (edge.linked.inDegree == 0) {
queue.offer(edge.linked);
}
}
}
}
}DFS深度遍历实现拓扑排序
给顶点加上三个状态 0未访问 1已访问 2正访问
-
- 使用DFS遍历图，并为每个节点设置三种状态：白色（未访问）、灰色（正在访问）、黑色（已访问完毕）。
- 如果在遍历过程中发现某个节点有一条边指向灰色节点（即该节点的某个后代节点），并且这个灰色节点不是上一步访问的节点，则说明存在环。
LinkedList<String> stack = new LinkedList<>();
for (Vertex vertex : graph) {
dfs(vertex, stack);
}
while (!stack.isEmpty()) {
System.out.println(stack.poll());
}
}
public static void dfs(Vertex v, LinkedList<String> stack){
if (v.status==1){
// 已经被访问过了
return;
}
if (v.status==2){
throw new IllegalStateException("有环");
}
v.status=2; // 在访问
for (Edge edge : v.edges) {
dfs(edge.linked, stack);
}
v.status=1;
stack.push(v.name);
}
四 Dijkstra算法
迪克斯特拉 单源最短路径算法
思路：
- 使用邻接表来构建图模型，每个点对应其所有邻接点，定义一个边的类，包含to(终点)，和weight(权重)
- 定义一个dis[]，表示到每个点的距离，初始时到每个点的距离为Integer.MaxValue();
- dis[start]=0,到起点的距离为0
- 每次从未访问的节点中选取一个距离起点最近的节点（通过优先队列实现）。然后遍历这个节点的邻接点，更新起点到新的节点的距离，如果新的距离<原来的距离，把新的节点加入到优先队列中
- 使用visited数组标记哪个节点已经访问过，如果该节点已经访问过，则不再访问
时间复杂度: O((n+m)⋅logn)，其中 n 是节点数，m是边数。
-
- 邻接表创建的复杂度是 O(m)。
- 优先队列每次操作的复杂度是 logn，最多会处理 m+n次操作。
空间复杂度: O(n+m)用于存储图的邻接表和辅助数组。
package TuLun;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.*;
public class P4779 {
public static void main(String[] args) throws IOException {
StreamTokenizer st=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
st.nextToken();
int n =(int)st.nval;
st.nextToken();
int m = (int)st.nval;
st.nextToken();
int s = (int)st.nval;
List<edge>[]graphs=new List[n+1];
for (int i = 0; i < graphs.length; i++) {
graphs[i]=new ArrayList<>();
}
for (int i = 1; i <= m; i++) {
st.nextToken();
int u = (int)st.nval;
st.nextToken();
int v = (int)st.nval;
st.nextToken();
long w = (int)st.nval;
graphs[u].add(new edge(v,w));
}
long[]dis=new long[n+1];
for (int i = 1; i <= n; i++) {
dis[i]=Integer.MAX_VALUE;
}
dis[s]=0;
PriorityQueue<long[]>queue=new PriorityQueue<>(Comparator.comparingLong(longs -> longs[1]));
// 到哪个节点，距离
queue.add(new long[]{s,0});
boolean[]visited=new boolean[n+1];
while (!queue.isEmpty()){
long[] arr = queue.poll();
int node = (int)arr[0];
long curDis = arr[1];
if (visited[node])continue;
visited[node]=true;
// 遍历该节点的邻接点 然后更新start到其邻接点的距离
for (edge edge : graphs[node]) {
int nextNode = edge.to;
long nextDis = edge.weight;
if (dis[nextNode]>curDis+nextDis){
dis[nextNode]=curDis+nextDis;
queue.offer(new long[]{nextNode,dis[nextNode]});
}
}
}
for (int i = 1; i <=n ; i++) {
System.out.print(dis[i]+" ");
}
}
public static class edge{
int to;
long weight;
public edge(int to, long weight) {
this.to = to;
this.weight = weight;
}
}
}
五 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是边数。在边数较多的图中，算法的执行效率较低。
- 无法处理负权环：虽然算法能检测负权环，但在图中存在负权环时，算法无法给出正确的最短路径解，因为负权环会导致路径长度无限减小。
public static void BellmanFord(List<Vertex> graph) {
// 1.进行顶点个数-1轮处理
for (int i = 0; i < graph.size()-1; i++) {
// 2.遍历所有边
for (Vertex s : graph) {
for (Edge edge : s.edges) {
// 3. 如果存在更短路径，更新路径
Vertex linked = edge.linked;
if (s.distance!=Integer.MAX_VALUE && s.distance+edge.weight< linked.distance){
linked.distance = s.distance+edge.weight;
linked.prev = s;
}
}
}
}
package TuLun;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class P3385 {
public static void main(String[] args) throws IOException {
StreamTokenizer st=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
st.nextToken();
int t = (int) st.nval;
for (int i = 0; i < t; i++) {
st.nextToken();
int n= (int) st.nval;
st.nextToken();
int m= (int) st.nval;
List<Edge>[]graphs=new List[n+1];
for (int j = 1; j <=n ; j++) {
graphs[j]=new ArrayList<>();
}
for (int j = 0; j < m; j++) {
st.nextToken();
int u= (int) st.nval;
st.nextToken();
int v= (int) st.nval;
st.nextToken();
int w= (int) st.nval;
if (w>=0){
graphs[u].add(new Edge(v,w));
graphs[v].add(new Edge(u,w));
}else{
graphs[u].add(new Edge(v,w));
}
}
long[]dis=new long[n+1];
Arrays.fill(dis,Integer.MAX_VALUE);
dis[1]=0;
for (int j = 0; j < n-1; j++) {
for (int k = 1; k <=n; k++) {
for (Edge edge : graphs[k]) {
int nextNode = edge.to;
long nextDis=edge.weight;
if (dis[k]!=Integer.MAX_VALUE && dis[nextNode]>dis[k]+nextDis){
dis[nextNode]=dis[k]+nextDis;
}
}
}
}
boolean flag=false;
for (int k = 1; k <=n; k++) {
for (Edge edge : graphs[k]) {
int nextNode = edge.to;
long nextDis=edge.weight;
if (dis[k]!=Integer.MAX_VALUE && dis[nextNode]>dis[k]+nextDis){
flag=true;
break;
}
}
if (flag)break;
}
if (flag){
System.out.println("YES");
}else{
System.out.println("NO");
}
}
}
public static class Edge{
int to;
long weight;
public Edge(int to, long weight) {
this.to = to;
this.weight = weight;
}
}
}六 Floyd-Warshall算法
FloydWarshall，即Floyd-Warshall算法，是一种用于求解图中求解任意两点间的最短路径的动态规划算法。以下是对Floyd-Warshall算法的详细解释：
一、算法概述
Floyd-Warshall算法可以在有向图或无向图中寻找所有顶点对之间的最短路径。它不仅能够处理正权边，还能处理负权边，但图中不能包含负权循环。该算法的时间复杂度为O(V2)。
二、算法步骤
- 初始化：创建一个n×n的距离矩阵D，其中D[i][j]表示从顶点i到顶点j的最短路径的长度。如果(i,j)之间没有直接的边，则D[i][j]设置为无穷大（或某个足够大的数来表示不可达）。对于所有的顶点i，D[i][i]=0，表示从自身到自身的距离为0。
- 动态规划过程：对于每一个中间顶点k，更新距离矩阵D。具体来说，对于每一对顶点(i, j)，如果D[i][j] > D[i][k] + D[k][j]，则更新D[i][j]为D[i][k] + D[k][j]。这相当于检查是否可以通过k作为中间顶点来获得从i到j的更短路径。
- 迭代：重复上述动态规划过程，直到所有可能的中间顶点都被考虑过。
- 结果：最终，距离矩阵D中的每个元素D[i][j]将包含从顶点i到顶点j的最短路径的长度。
三、算法实现
Floyd-Warshall算法的实现通常使用嵌套的三层循环来遍历所有节点对和中间节点。
检验是否有环的方法：
- 在dist中判断对角线上是否存在负数
- 对角线是自己到自己最小应该为0
- 绕了一圈回到自己<0
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);
floydWarshall(graph);
}
/**
* v1 v2 v3 v4
* v1
* v2
* v3
* v4
* @param graph
*/
public static void floydWarshall(List<Vertex> graph){
long[][] dist = new long[graph.size()][graph.size()];
Vertex[][] prev = new Vertex[graph.size()][graph.size()]; // 路径
// 1.初始化距离
for (int i = 0; i < graph.size(); i++) {
// i起点 j终点
Map<Vertex, Integer> map = graph.get(i).edges.stream().collect(Collectors.toMap(k -> k.linked, v -> v.weight));
for (int j = 0; j < graph.size(); j++) {
if (i == j){
// 自己到自己距离为0
dist[i][j] = 0;
}else{
// 判断起点是否和终点连接 不连接则距离无穷大
Integer orDefault = map.getOrDefault(graph.get(j), Integer.MAX_VALUE);
dist[i][j] = orDefault;
// i到j j的上一个应该为i
prev[i][j] = graph.get(i);
}
}
}
// 2.借助中间点k从起点i到达结束点j 或者也可以从起点i出发借助中间点k到结束点j i,j,k都是一轮循环
// 2.1有几个点则进行几轮借助 每个点都去借助一轮别的点
for (int k = 0; k < graph.size(); k++) {
// 2.2 i 起点
for (int i = 0; i < graph.size(); i++) { // 多源的 所以起点也要换 每个顶点当一次起点
// 2.3 j终点
for (int j = 0; j < graph.size(); 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]=graph.get(k);
}
}
}
}
// 3.打印结果
// for (int i = 0; i < graph.size(); i++) {
// for (int j = 0; j < graph.size(); j++) {
// System.out.print(dist[i][j]+" ");
// }
// System.out.println();
// }
for (int i = 0; i < graph.size(); i++) {
for (int j = 0; j < graph.size(); j++) {
path(prev,graph,i,j);
}
}
}
private 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 vertex = prev[i][j];
stack.push(vertex.name);
j = graph.indexOf(vertex);
}
System.out.println(String.join("->", stack));
}
}七 最小生成树算法
一、Prim算法
Prim算法是一种用于求解最小生成树（Minimum Spanning Tree, MST）的经典算法。最小生成树是指在一个加权无向图中，找到一棵包含所有顶点且边权值之和最小的树。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");
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);
// 1.创建一个优先级队列，按照距离进行排序，默认为小顶堆
PriorityQueue<Vertex> queue = new PriorityQueue<>(Comparator.comparingInt(v->v.distance));
// 2.为每个顶点初始化距离
v1.distance = 0;
for (Vertex vertex : graph) {
if (vertex != v1) {
vertex.distance = Integer.MAX_VALUE;
}
}
for (Vertex vertex : graph) {
queue.offer(vertex);
}
// 3.每次选择距离最小的顶点，作为新的当前顶点
while (!queue.isEmpty()) {
// 3.1 取出距离最小的顶点
Vertex current = queue.peek();
// 3.2 更新距离
if (!current.visited){
updateDistance(current, queue);
current.visited = true;
}
// 3.3 从队列中删除该节点
queue.poll();
}
// 4.打印路径
for (Vertex vertex : graph) {
System.out.println(vertex.name +" "+ vertex.distance+" "+ (vertex.prev == null ? "null" : vertex.prev.name));
}
}
public static void updateDistance(Vertex current, PriorityQueue<Vertex> queue) {
// 3.3 遍历当前顶点的邻居
for (Edge edge : current.edges) {
Vertex n = edge.linked;
if (!n.visited){
int dist=edge.weight;
// 3.4 如果距离小于邻居的距离，则更新邻居的距离
if (dist < n.distance) {
n.distance = dist;
// 更新该节点的距离
queue.offer(n);
n.prev = current;
}
}
}
}二、 kruskal算法
Kruskal算法，即克鲁斯卡尔算法，是一种用于在加权连通图中寻找最小生成树的算法。以下是对Kruskal算法的详细解释：
一、算法思想
Kruskal算法的基本思想是按照权值从小到大的顺序选择n-1条边，并保证这n-1条边不构成回路，从而构成一棵极小连通子图，该连通子图中n-1条边上权值之和达到最小，则称其为连通网的最小生成树。
二、具体步骤
- 从加权图中找出所有的边，初始时所有边都不属于最小生成树。
- 将所有的边按照权值从小到大进行排序。
- 从排序后的边中依次取出边，并判断该边及其连接的两个顶点加入最小生成树是否会形成环路。
-
- 若形成环路，则跳过此边，继续取下一条边进行判断。
- 若不形成环路，则将该边及其连接的两个顶点加入最小生成树。
- 重复上述步骤，直至所有顶点均连接在一起，并且没有形成环路时，最小生成树就找到了。
三、核心问题
- 如何对图的所有边按照权值大小进行排序？
-
- 应对策略：采用排序算法（如快速排序、归并排序等）对图的所有边按照权值大小进行排序。
- 如何判断边及其顶点加入最小生成树是否会形成回路？
-
- 应对策略：可以使用并查集（Union Find）数据结构来判断。在将边加入最小生成树之前，先判断该边的两个顶点是否已经在同一个集合中（即是否已经连通）。若已经连通，则加入该边会形成回路；若未连通，则可以将该边加入最小生成树，并将两个顶点所在的集合合并。
四、算法特点
- Kruskal算法是将边作为操作对象，当加权图的边越多，要处理的边也越多，则算法的时间复杂度就越高；而顶点的数量对算法的时间复杂度无影响。因此，Kruskal算法适合处理稀疏图（边较少的图）。
- Kruskal算法的时间复杂度主要取决于排序操作，一般为O(mlogm)，其中m为边的数量。
五、应用场景
Kruskal算法广泛应用于网络设计、交通规划、电路布线等领域中，用于求解最小生成树问题。例如，在构建通信网络时，需要选择权值（如距离、成本等）最小的边来连接各个节点，以保证网络的连通性和最小成本。
综上所述，Kruskal算法是一种高效、实用的求解最小生成树的算法，特别适用于处理稀疏图的情况。
static void kruskal(int size, PriorityQueue<Edge> queue){
List<Edge> edges = new ArrayList<>();
DisjoinSet set=new DisjoinSet(size);
while (!queue.isEmpty()){
Edge poll = queue.poll();
int i = set.find(poll.start);// 找到起点的老大
int j = set.find(poll.end);// 找到终点的老大
if (i!=j){
// 老大索引不一致 不是一个老大
edges.add(poll);
set.union(i,j);// 相交 给原本的两个老大整个共同的新老大
}
}
}package com.shutu.Graph;
public class DisjoinSet {
int[] s;
// 初始化，n个元素的并查集，初始每个元素都是一个集合，自身为老大
// 索引代表顶点
// 值代表有关系的顶点
public DisjoinSet(int n) {
s = new int[n];
for (int i = 0; i < n; i++) {
s[i] = i;
}
}
// 找到老大是谁
public int find(int x) {
if (s[x] == x) {
return x;
}
return find(s[x]);
// 路径压缩 return s[x]=find(s[x]);
}
// 是让两个集合“相交”，即选出新老大，x、y是原老大索引
public void union(int x, int y) {
s[y]=x;
}
}
初始图
连接一些权重比较小的边 给每个点找到自己的老大 两个顶点老大相同则说明已相连
路径压缩 再找到他们的老大后，直接将其值改为老大值
