数据结构-图

embedded/2024/9/26 1:24:05/

1) 概念

图是由顶点（vertex）和边（edge）组成的数据结构，例如

该图有四个顶点：A、B、C、D 以及四条有向边，有向图中，边是单向的

有向 vs 无向

如果是无向图，那么边是双向的，下面是一个无向图的例子

度

度是指与该顶点相邻的边的数量

 

例如上图中

  • A、B、C、E、F 这几个顶点度数为 2

  • D 顶点度数为 4

有向图中，细分为入度和出度，参见下图

  • A (2 out / 0 in)

  • B、C、E (1 out / 1 in)

  • D (2 out / 2 in)

  • F (0 out / 2 in)

权

边可以有权重，代表从源顶点到目标顶点的距离、费用、时间或其他度量。

路径

路径被定义为从一个顶点到另一个顶点的一系列连续边，例如上图中【北京】到【上海】有多条路径

  • 北京 - 上海

  • 北京 - 武汉 - 上海

路径长度

  • 不考虑权重，长度就是边的数量

  • 考虑权重，一般就是权重累加

环

在有向图中，从一个顶点开始，可以通过若干条有向边返回到该顶点，那么就形成了一个环

图的连通性

如果两个顶点之间存在路径，则这两个顶点是连通的，所有顶点都连通，则该图被称之为连通图，若子图连通，则称为连通分量

2) 图的表示

比如说，下面的图

用邻接矩阵可以表示为：有边相连赋值1 没有边相连赋值0 二维数组 (浪费空间太多)

  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实现

以这幅图为例子

/*** 边*/
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;}}

import java.util.List;/*** 顶点*/
public class Vertex {String name;List<Edge> edges;public Vertex(String name){this.name = name;}public String getName(){return name;}public static void main(String[] args) {Vertex a = new Vertex("A");Vertex b = new Vertex("B");Vertex c = new Vertex("C");Vertex d = new Vertex("D");a.edges = List.of(new Edge(b),new Edge(c));b.edges = List.of(new Edge(d));c.edges = List.of(new Edge(d));d.edges = List.of();}
}

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,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));}}

深度优先搜索 Depth-first-search

但是在这段代码我们要加一个属性: 看看这个顶点有没有被访问过

/*** 顶点*/
public class Vertex {String name;List<Edge> edges;boolean visited;//是否被访问过public Vertex(String name){this.name = name;}public String getName(){return name;}}

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,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));//深度优先搜索--尽可能的向远走dfs(v1);}private static void dfs(Vertex v){v.visited = true;System.out.println(v.name);for (Edge edge : v.edges) {if (!edge.linked.visited) {//看看有没有被访问过dfs(edge.linked);}}}
/*
v1
v3
v4
v5
v6
v2*/
}


  private static void dfs2(Vertex v){//自定义栈实现LinkedList<Vertex> 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);}}/*
v1
v6
v5
v2
v4
v3*/}}
广度优先搜索  Breadth-first-search

import java.util.LinkedList;
import java.util.List;/*** 广度优先搜索 Breadth-first-search* */
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, 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));bfs(v1);}private static void bfs(Vertex v){LinkedList<Vertex> queue = new LinkedList<>();//队列queue.offer(v);v.visited = true;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);}}/* v1v3v2v6v4v5*/}}
}
拓扑排序

网页基础和Java基础的入度为0,排序删除后,再继续找入度为0的点

在顶点类要再加一个入度的属性:inDegree

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();List<Vertex> graph = List.of(v1, v2, v3, v4, v5, v6, v7);//graph代表整个图// 1.统计每个顶点的入度for(Vertex v:graph){for(Edge edge:v.edges) {edge.linked.inDegree++;}}for(Vertex vertex:graph){System.out.println(vertex.name+ " "+ vertex.inDegree);}/*网页基础 0Java基础 0JavaWeb 2Spring框架 2微服务框架 1数据库 0实战项目 1*/// 2.将入度为0的顶点加入队列LinkedList<Vertex> queue = new LinkedList<>();for(Vertex v:graph){if(v.inDegree==0){queue.offer(v);}}// 3.队列中不断移除顶点,每移除一个顶点,把它相邻顶点入度-1,若剪到为0则入队while(!queue.isEmpty()){Vertex poll = queue.poll();System.out.println(poll.name);/*网页基础Java基础数据库JavaWebSpring框架微服务框架实战项目*/for (Edge edge : poll.edges) {edge.linked.inDegree--;if(edge.linked.inDegree==0){queue.offer(edge.linked);}}}}
}

但是拓扑排序有个前提就是图中不能有环

一旦出现环就无法进行排序了

如果再按照之前的算法进行排序的话,微服务框架一直大于等于0

那如果需要我们写一段代码来检测出是否有环怎么做呢?

   // 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);}}}System.out.println(result.size() == graph.size());
拓扑排序DFS

在这个方法实现上，我们又要多加一个属性

/*** 顶点*/
public class Vertex {String name;List<Edge> edges;boolean visited;//是否被访问过int inDegree;//入度int status;// 状态 0-未访问 1-访问中  2-访问过,用于拓扑排序public Vertex(String name){this.name = name;}public String getName(){return name;}}
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();List<Vertex> graph = List.of(v1, v2, v3, v4, v5, v6, v7);//graph代表整个图LinkedList<String> stack = new LinkedList<>();for (Vertex v : graph) {dfs(v,stack);}System.out.println(stack);}private static void dfs(Vertex v, LinkedList<String> stack) {if(v.status==2){return;}if(v.status==1){throw new RuntimeException("发现了环");}v.status = 1;//status = 1是用在环的检测上for (Edge edge : v.edges) {dfs(edge.linked,stack);}v.status=2;stack.push(v.name);}
}

最短路径

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分布式计算有影响力论文奖。为了纪念他，该年度奖项在接下来的一年更名为迪克斯特拉奖。

迪克斯特拉在计算机科学领域的贡献

  1. 最短路径算法，也称为迪克斯特拉算法，现代计算机科学本科课程中广泛教授

  2. Shunting yard算法

  3. THE OS 操作系统

  4. 银行家算法

  5. 用于协调多个处理器和程序的信号量构造

  6. 在分布式计算领域提出概念：自稳定性

 

算法描述：

  1. 将所有顶点标记为未访问。创建一个未访问顶点的集合。

  2. 为每个顶点分配一个临时距离值

    • 对于我们的初始顶点，将其设置为零

    • 对于所有其他顶点，将其设置为无穷大。

  3. 每次选择最小临时距离的未访问顶点，作为新的当前顶点

  4. 对于当前顶点，遍历其所有未访问的邻居，并更新它们的临时距离为更小

    • 例如，1->6 的距离是 14，而1->3->6 的距离是11。这时将距离更新为 11

    • 否则，将保留上次距离值

  5. 当前顶点的邻居处理完成后，把它从未访问集合中删除

这里还要再加一个属性dist代表距离,然后初始的时候除了起始节点,其他都是默认无穷大

/*** 顶点*/
public class Vertex {String name;List<Edge> edges;boolean visited;//是否被访问过int inDegree;//入度int status;// 状态 0-未访问 1-访问中  2-访问过,用于拓扑排序int dist = INF; // 距离static final Integer INF = Integer.MAX_VALUE;public Vertex(String name){this.name = name;}public String getName(){return name;}}

实现代码:

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));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);//1.创建一个未访问节点source.dist = 0;//2.分配临时距离while(!list.isEmpty()){//3.选取当前顶点 (集合中dist最小的点)Vertex curr = chooseMinDistVertex(list);//4 更新当前顶点邻居距离updataNeighboursDist(curr,list);//5.移除当前顶点list.remove(curr);}for (Vertex v : graph) {System.out.println(v.name + " "+ v.dist);}/*v1 0v2 7v3 9v4 20v5 20v6 11*/}private static void updataNeighboursDist(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;}
}

但是如果我要路径呢?

新添加一个属性prev

/*** 顶点*/
public class Vertex {String name;List<Edge> edges;boolean visited;//是否被访问过int inDegree;//入度int status;// 状态 0-未访问 1-访问中  2-访问过,用于拓扑排序int dist = INF; // 距离static final Integer INF = Integer.MAX_VALUE;Vertex prev = null;public Vertex(String name){this.name = name;}public String getName(){return name;}}

实现部分

private static void dijkstra(List<Vertex> graph, Vertex source) {ArrayList<Vertex> list = new ArrayList<>(graph);//1.创建一个未访问节点source.dist = 0;//2.分配临时距离while(!list.isEmpty()){//3.选取当前顶点 (集合中dist最小的点)Vertex curr = chooseMinDistVertex(list);//4 更新当前顶点邻居距离updataNeighboursDist(curr);//5.移除当前顶点list.remove(curr);curr.visited = true;}for (Vertex v : graph) {System.out.println(v.name + " "+ v.dist+" "+(v.prev!=null?v.prev.name:"null"));}/*v1 0 nullv2 7 v1v3 9 v1v4 20 v3v5 20 v6v6 11 v3*/}private static void updataNeighboursDist(Vertex curr) {for (Edge edge : curr.edges) {Vertex n = edge.linked;if(!n.visited){ //这里修改了一下不用每次都用contans判断在性能上有一点提升int dist = curr.dist+edge.weight;if(dist<n.dist){n.dist = dist;n.prev = curr;}}}}

改进 - 优先级队列(最小堆)

  1. 创建一个优先级队列，放入所有顶点（队列大小会达到边的数量）

  2. 为每个顶点分配一个临时距离值

    • 对于我们的初始顶点，将其设置为零

    • 对于所有其他顶点，将其设置为无穷大。

  3. 每次选择最小临时距离的未访问顶点，作为新的当前顶点

  4. 对于当前顶点，遍历其所有未访问的邻居，并更新它们的临时距离为更小，若距离更新需加入队列(因为Java中的优先级队列不会自动调整位置 虽然顶点可能重复了但是位置更为重要)

    • 例如，1->6 的距离是 14，而1->3->6 的距离是11。这时将距离更新为 11

    • 否则，将保留上次距离值

  5. 当前顶点的邻居处理完成后，把它从队列中删除

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));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;//2.分配临时距离for (Vertex vertex : graph) {queue.offer(vertex);}while(!queue.isEmpty()){//3.选取当前顶点 (集合中dist最小的点)Vertex curr =queue.peek();//4 更新当前顶点邻居距离if(!curr.visited){//因为小顶堆中dist更改了但是位置不变我们自己又添加了一个顶点这样就会导致两次访问updataNeighboursDist(curr,queue);curr.visited=true;}//5.移除当前顶点queue.poll();curr.visited = true;}/*v1 0 nullv2 7 v1v3 9 v1v4 20 v3v5 20 v6v6 11 v3*/for (Vertex v : graph) {System.out.println(v.name + " "+ v.dist+" "+(v.prev!=null?v.prev.name:"null"));}}private static void updataNeighboursDist(Vertex curr, PriorityQueue<Vertex> queue) {for (Edge edge : curr.edges) {Vertex n = edge.linked;if(!n.visited){ //这里修改了一下不用每次都用contans判断在性能上有一点提升int dist = curr.dist+edge.weight;if(dist<n.dist){n.dist = dist;n.prev = curr;queue.offer(n);//更改后要再加入}}}}}

Dijkstra算法的问题:

出现负权重的边==>导致结果出错

按照 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"));}}
}

问题:但是这个算法不能处理负环

负环

三个权重加起来是负数 2+1-4=-1 没有解 无限循环

 

如果在【顶点-1】轮处理完成后，还能继续找到更短距离，表示发现了负环
 

 直接throw 一个报错
 

 

Floyd-Warshall 多源最短路径算法
 

可以处理负边 但是遇到负环还是不行
 

 

 对name重写hashcode和equals方法
 

/*** 顶点*/
public class Vertex {String name;List<Edge> edges;boolean visited;//是否被访问过int inDegree;//入度int status;// 状态 0-未访问 1-访问中  2-访问过,用于拓扑排序int dist = INF; // 距离static final Integer INF = Integer.MAX_VALUE;Vertex prev = null;public Vertex(String name){this.name = name;}public String getName(){return name;}@Overridepublic String toString() {return name+'(' + dist + ')';}@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 Objects.hash(name);}
}

 

Java HashMap getOrDefault() 方法
 

getOrDefault() 方法获取指定 key 对应对 value，如果找不到 key ，则返回设置的默认值。
 

getOrDefault() 方法的语法为：
 

hashmap.getOrDefault(Object key, V defaultValue)
 

注：hashmap 是 HashMap 类的一个对象。
 

参数说明：
 

  • key - 键
  • defaultValue - 当指定的key并不存在映射关系中，则返回的该默认值
 

返回值
 

返回 key 相映射的的 value，如果给定的 key 在映射关系中找不到，则返回指定的默认值。
 


import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;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);/*k=0直接连通v1  v2  v3  v4v1  0   ∞   -2  ∞v2  4   0   3   ∞v3  ∞   ∞   0   2v4  ∞   -1  ∞   0k=1 借助v1到达其它顶点v1  v2  v3  v4v1  0   ∞   -2  ∞v2  4   0   2   ∞v3  ∞   ∞   0   2v4  ∞   -1  ∞   0k=2 借助v2到达其它顶点v1  v2  v3  v4v1  0   ∞   -2  ∞v2  4   0   2   ∞v3  ∞   ∞   0   2v4  3   -1  1   0k=3 借助v3到达其它顶点v1  v2  v3  v4v1  0   ∞   -2  0v2  4   0   2   4v3  ∞   ∞   0   2v4  3   -1  1   0k=4 借助v4到达其它顶点v1  v2  v3  v4v1  0   -1   -2  0v2  4   0   2   4v3  5   1   0   2v4  3   -1  1   0*/floydWarshall(graph);}private 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);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);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;//连通就改变prev}}}
//        print(prev);
//        print(dist);//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);for (int i = 0; i < size; i++) {for (int j = 0; j < size; j++) {path(prev,graph,i,j);}}}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(",", "[", "]")));}}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);}}

 

负环
 

如果在 3 层循环结束后，在 dist 数组的对角线处（i==j 处）发现了负数，表示出现了负环
 

对角线有0出现负环
 

练习
 

Leetcode1334
 

1334. 阈值距离内邻居最少的城市 - 力扣（LeetCode）
 

思路：Floyd算法
 本题需要记录每个节点到其它节点的最短路径，所以通过Floyd算法，使用dp数组更新所有节点到其余节点的最短路径，最后dp数组保留的就是所有节点到其余节点的最短路径，使用num数组记录，每个节点到其它节点的最短路长度小于distanceThreshold的个数，找出最少的个数的起点i就是答案。
  
 

class Solution {public int findTheCity(int n, int[][] edges, int distanceThreshold) {int[][] g = new int[n][n];// 初始化邻接矩阵for(int i = 0;i<n;i++){for(int j = 0;j<n;j++){g[i][j] = i==j?0:0x3f3f3f;}}//存图for(int[] e:edges){int a = e[0],b=e[1],c=e[2];g[a][b]=g[b][a] = Math.min(g[a][b],c);//说不定有负边的情况只是这里没有}//最短路floyd(g);//统计答案int ans = -1,cnt = n+10;for(int i = 0;i<n;i++){int cur = 0;for(int j = 0;j<n;j++){if(i!=j&&g[i][j] <= distanceThreshold)cur++;}if(cur<=cnt){cnt = cur;ans = i;}}return ans;}void floyd(int[][] g){int n = g.length;// floyd 基本流程为三层循环:[枚举中转点-枚举起点-枚举终点]for(int p = 0;p<n;p++){for(int i = 0;i<n;i++){for(int j=0;j<n;j++){g[i][j] = Math.min(g[i][j],g[i][p]+g[p][j]);}}}}
}
 

 

Leetcode1976 
 

1976. 到达目的地的方案数 - 力扣（LeetCode）
 

class Solution {int N = 210, MOD = (int)1e9+7;long INF = (long)1e12;int[][] g = new int[N][N];int[] in = new int[N];long[] dist = new long[N];boolean[] vis = new boolean[N];int n;public int countPaths(int _n, int[][] rs) {n = _n;for (int[] info : rs) {int a = info[0], b = info[1], c = info[2];g[a][b] = g[b][a] = c;}// 朴素 Dijkstra 求解从 0 点到其他点的最短路dijkstra();// 利用最短路重新建图，并统计入度for (int[] info : rs) {int a = info[0], b = info[1], c = info[2];g[a][b] = g[b][a] = 0;if (dist[a] + c == dist[b]) {g[a][b] = c; in[b]++;} else if (dist[b] + c == dist[a]) {g[b][a] = c; in[a]++;}}// 跑拓扑排序统计方案数Deque<Integer> d = new ArrayDeque<>();for (int i = 0; i < n; i++) {if (in[i] == 0) d.addLast(i);}int[] f = new int[n];f[0] = 1;while (!d.isEmpty()) {int x = d.pollFirst();for (int i = 0; i < n; i++) {if (g[x][i] == 0) continue;f[i] += f[x];f[i] %= MOD;if (--in[i] == 0) d.addLast(i);}}return f[n - 1];}void dijkstra() {Arrays.fill(dist, INF);dist[0] = 0;for (int i = 0; i < n; i++) {int t = -1;for (int j = 0; j < n; j++) {if (!vis[j] && (t == -1 || dist[j] < dist[t])) t = j;}vis[t] = true;for (int j = 0; j < n; j++) {if (g[t][j] == 0) continue;dist[j] = Math.min(dist[j], dist[t] + g[t][j]);}}}
}

 

 

 

 

 

 

 












http://www.ppmy.cn/embedded/18751.html












相关文章










文献速递：深度学习胶质瘤诊断---空间细胞结构预测胶质母细胞瘤的预后









文献速递：深度学习胶质瘤诊断---空间细胞结构预测胶质母细胞瘤的预后




Title  
题目 Spatial cellular architecture predicts prognosis in glioblastoma 
空间细胞结构预测胶质母细胞瘤的预后 01文献速递介绍 胶质母细胞瘤的治疗耐药性的关键驱动因素是肿瘤内的异质性和细胞状态的可塑性。在这里&#xff0c;我们调查了空间细胞组织与胶质母细胞瘤…




阅读更多...

















数据结构（九）---并查集









数据结构（九）---并查集




目录 
1.集合 
2.集合的相关操作 
(1)查(Find)&#xff1a; 
•Find操作的优化 
(2)并(Union)&#xff1a; 
•Union操作的优化 1.集合 
数据元素之间的逻辑关系可以为集合&#xff0c;树形关系&#xff0c;线性关系&#xff0c;图关系。对于集合而言&#xff0c;一个集合可以划…




阅读更多...

















mysql的多表查询和子查询









mysql的多表查询和子查询




多表查询&#xff1a;查询数据时&#xff0c;需要使用多张表来查询 
多表查询分类&#xff1a; 1.内连接查询 2.外连接查询 3.子查询 笛卡尔积&#xff1a;  
create table class
(id int primary key auto_increment,name varchar(10)
);
create table student
(id int primar…




阅读更多...

















回归与聚类——性能评估（二）









回归与聚类——性能评估（二）




1分析 
回归当中的数据大小不一致&#xff0c;是否会导致结果影响较大。所以需要做标准化处理。 
数据分割与标准化处理回归预测线性回归的算法效果评估 
2回归性能评估 
均方误差(Mean Squared Error)MSE)评价机制&#xff1a;  注&#xff1a;y^i为预测值&#xff0c;y-为真实…




阅读更多...

















Visual studio2022+QT的创建









Visual studio2022+QT的创建




Visual studio2022QT的创建 
1.首先安装Visual studio 
2.可以直接在visual studio中安装qt插件&#xff0c;如下所示&#xff1a; 
扩展->管理扩展->搜索qt Vistal Studio Tools 
3.接下来的就是重点&#xff0c;安装完了这个插件之后&#xff0c;也是需要安装qt的程序的…




阅读更多...

















网络运维类面试非技术问题









网络运维类面试非技术问题




1、之前工作中网络架构 答&#xff1a;在上一家公司&#xff0c;我们的网络架构  &#xff08;或者我在做上一个项目时的网络架构&#xff09;        1&#xff09;在上家公司&#xff0c;采用了分层的网络架构模型&#xff0c;包括接入层、汇聚层、核心层和出口层        2&a…




阅读更多...

















前端HTML面试题：meta 元素都有什么









前端HTML面试题：meta 元素都有什么




在HTML中&#xff0c;<meta> 元素是一个非常重要且常用的元素&#xff0c;它用于表示关于HTML文档的元数据&#xff08;metadata&#xff09;&#xff0c;这些元数据不会直接显示在页面上&#xff0c;但可以被浏览器以及其他网页服务利用。在前端开发的面试中&#xff0c…




阅读更多...

















IOptionService









IOptionService




目录 
1、 IOptionService  
1.1、 * 保存一组配置  
2、 IUserService  
2.1、 * 保存用户数据  
2.2、 * 通过uid查找对象  
2.3、 * 用戶登录




阅读更多...















 
 
 
 










最新文章







 





















Copyright @ 2022~2023