图论中的算法

小鱼儿 2023-10-12 11:46 96阅读 0赞

图论的概念：图论是数学的一个分支，它是以图为研究对象，图论中的图是由若干个给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些实体之间的某种特定的关系，用点代表实体，用连接两点之间的线表示两个实体之间具有某种关系。

图的分类：

  • 无权无向图

5858f9f2bf584e8db18ef22dece7bae7.png

无向就是可以互相通向，没有进行方向的限制，就好比双向指向：

b46aa50657604f3bbf503abe02fbfb2e.png

  • 无权有向图

dcb5727103f8461b8036f5a17cc7ee60.png

无权就是好比每条路线占的权重一致，没有区别，故我们可以把无权图假设为每个权重都是1的有权图：

01e82284d4334cb6b2af212bf473e931.png

  • 有权无向图

ce19d33d5a5c446a88b2816cc98b0625.png

  • 有权有向图

3890cd3121b44bc2a266eb507548843b.png

BFS和DFS

我们首先来了解什么是BFS?什么又是DFS?9f90aae4a3ef47c39a94269441bb2b7c.gif

DFS俗称深度优先算法，有一种不撞南墙不回头的感觉，认准一条路，一致往下走，直到走不通位置，然后再重新返回再重复刚才的操作，直到找到目标节点为止。DFS关键点是递归以及回溯，一般用栈进行操作。在图中我们经常这样：

1eda4beca66541178d50c2675853876a.png

经典算法题之（知识补充）------ BFS和DFS的感性认识\_ProLayman的博客-CSDN博客

BFS俗称广度优先算法，相对于深度优先算法，如果把深度优先算法当成是一个莽夫的话，广度优先算法像是一个文人墨客，广度优先算法在面临一个路口时，把所有的路口记录下来，然后选择其中一个进入，然后再回退再进入另一个路口，直到找到目标节点为止。BFS关键点是状态的选取和标记，一般用队列去解决问题，在图中我们经常这样：

98039cff62114b499043b793d01125b8.png

图的存储结构

  • 邻接矩阵

概念：所谓邻接矩阵存储结构就是每个顶点用一个一维数组存储边的信息，这样所有点合起来就是用矩阵表示图中各顶点之间的邻接关系。所谓矩阵其实就是二维数组。对于有n个顶点的图 G=(V,E) 来说，我们可以用一个 n× n 的矩阵A来表示G中各顶点的相邻关系

54002ef78cd14eb99bbcac9c27b1f757.png

对应的邻接矩阵为：

4995fef987794857a0cb32713a421e05.png

与对应点直接相连为1，不直接相连为0

构建邻接矩阵：

  1. package graphtheory;
  3. import java.util.Arrays;
  5. /**
  6.  * 图的表示--使用邻接矩阵
  7.  */
  8. public class Graph01 {
  9.     private char[] V;//顶点上的值
  11.     private Vertex[] vertexs;//顶点数组
  13.     private int N;
  16.     //邻接矩阵
  17.     private int[][] adj;
  19.     //图的构造函数
  20.     public Graph01(char[] arr) {//{'A','E','F','G','H','P'}
  21.         //拿到数组的长度
  22.         int length = arr.length;
  23.         this.N = length;
  24.         V = new char[length];
  25.         //arr元素赋值 到V
  26.         this.V = Arrays.copyOf(arr, length);
  27.         //构建图中的结点
  28.         vertexs = new Vertex[length];
  29.         for (int i = 0; i < length; i++) {
  30.             vertexs[i] = new Vertex(i,this.V[i]);//
  32.         }
  33.         this.adj = new int[length][length];
  34.     }
  36.     //打印邻接矩阵
  37.     public void show() {
  38.         System.out.print("    ");
  39.         for (int i = 0; i < this.N; i++) {
  40.             System.out.format("%4c", this.V[i]);
  41.         }
  42.         System.out.println();
  43.         for (int i = 0; i < this.N; i++) {
  44.             System.out.format("%4c",this.V[i]);
  45.             for (int j = 0; j < this.N; j++) {
  46.                 System.out.format("%4s", this.adj[i][j] > 0?(this.adj[i][j]):"-");
  47.             }
  48.             System.out.println();
  49.         }
  50.     }
  52.     /**
  53.      * 创建顶点类
  54.      */
  55.     private class Vertex {
  56.         char v;//值
  57.         int index;//索引
  59.         public Vertex(int index, char c) {
  60.             this.index = index;
  61.             this.v = v;
  62.         }
  64.     }
  66.     public static void main(String[] args) {
  67.         char arr[] = {'A', 'E', 'F', 'G', 'H', 'P'};
  68.         //构建graph01
  69.         Graph01 graph01 = new Graph01(arr);
  70.         //进行连接
  71.         int[][] adjMatrix = graph01.adj;
  72.         adjMatrix[0][1]=1;
  73.         adjMatrix[0][2]=1;
  74.         adjMatrix[0][3]=1;
  76.         adjMatrix[1][0]=1;
  77.         adjMatrix[1][3]=1;
  78.         adjMatrix[1][4]=1;
  80.         adjMatrix[2][0]=1;
  82.         adjMatrix[3][0]=1;
  83.         adjMatrix[3][1]=1;
  84.         adjMatrix[3][4]=1;
  85.         adjMatrix[3][5]=1;
  87.         adjMatrix[4][1]=1;
  88.         adjMatrix[4][3]=1;
  89.         adjMatrix[4][5]=1;
  91.         adjMatrix[5][3]=1;
  92.         adjMatrix[5][4]=1;
  95.         graph01.show();
  96.     }
  97. }

573219004cb046b888b45a30ae514d87.png

  • 邻接表

邻接表的概念：邻接表的思想是，对于图中的每一个顶点，用一个数组来记录这个点和哪些点相连。由于相邻的点会动态的添加，所以对于每个点，我们需要用List来记录。

54002ef78cd14eb99bbcac9c27b1f757.png

对应的邻接表为：

f663248f2c3d4b9b9950e42c38fe2a49.png

  1. package graphtheory;
  3. import java.util.ArrayList;
  4. import java.util.Arrays;
  5. import java.util.List;
  7. /**
  8.  * 图的表示--使用邻接矩阵
  9.  */
  10. public class Graph02 {
  11.     private char[] V;//顶点上的值
  13.     private Vertex[] vertexs;//顶点数组
  14.     private int N;
  17.     //邻接矩阵
  18.     private List<Integer>[] adj;
  20.     //图的构造函数
  21.     public Graph02(char[] arr) {//{'A','E','F','G','H','P'}
  22.         //拿到数组的长度
  23.         int length = arr.length;
  24.         this.N = length;
  25.         V = new char[length];
  26.         //arr元素赋值 到V
  27.         this.V = Arrays.copyOf(arr, length);
  28.         //构建图中的结点
  29.         vertexs = new Vertex[length];
  30.         for (int i = 0; i < length; i++) {
  31.             vertexs[i] = new Vertex(i, this.V[i]);
  33.         }
  34.         this.adj = new List[length];
  35.         for (int i = 0; i < this.N; i++) {
  36.             this.adj[i]=new ArrayList<>();
  37.         }
  38.     }
  40.     //打印邻接矩阵
  41.     public void show() {
  42.         System.out.println("    ");
  43.         for (int i = 0; i < this.N; i++) {
  44.             System.out.format("%-4c", this.V[i]);
  45.             //拿到邻接表相邻结点的集合
  46.             List<Integer> linkedList = this.adj[i];
  47.             for (int j = 0; j < linkedList.size(); j++) {
  48.                 System.out.print(this.V[linkedList.get(j)] + "---->");
  49.             }
  50.             System.out.println();
  51.             System.out.format("%-4d",vertexs[i].index);
  52.             for (int j = 0; j < linkedList.size(); j++) {
  53.                 System.out.print(vertexs[linkedList.get(j)].index + "---->");
  54.             }
  55.             System.out.println();
  57.             }
  58.         }
  62.     /**
  63.      * 创建顶点类
  64.      */
  65.     private class Vertex {
  66.         char v;//值
  68.         int index;//索引
  70.         int weight;//权值
  72.         public Vertex(int index, char c) {
  73.             this.index = index;
  74.             this.v = v;
  75.             this.weight = weight;
  76.         }
  78.         public Vertex(int index) {
  80.         }
  81.     }
  83.     public static void main(String[] args) {
  84.         char arr[] = {'A', 'E', 'F', 'G', 'H', 'P'};
  85.         //构建graph01
  86.         Graph02 graph02 = new Graph02(arr);
  87.         //邻接表
  88.         List<Integer>[] adj = graph02.adj;
  89.         adj[0].add(1);
  90.         adj[0].add(2);
  91.         adj[0].add(3);
  93.         adj[1].add(0);
  94.         adj[1].add(3);
  95.         adj[1].add(4);
  97.         adj[2].add(0);
  99.         adj[3].add(0);
  100.         adj[3].add(1);
  101.         adj[3].add(4);
  102.         adj[3].add(5);
  104.         adj[4].add(1);
  105.         adj[4].add(3);
  106.         adj[4].add(5);
  108.         adj[5].add(3);
  109.         adj[5].add(4);
  112.         graph02.show();
  113.     }
  114. }

a36124a7368a4aa48836bae7bb156872.png

使用邻接表求出A—P的所有路径：

  1. package graphtheory;
  4. import java.util.*;
  6. // 图的表示-- 使用邻接表
  7. public class Graph03 {
  8.     private char[] V;
  9.     // 顶点数组
  10.     private Vertex[] vertexs;
  11.     private int N;
  12.     // 邻接表
  13.     private List<Integer>[] adj;
  15.     public Graph03(char[] arr) { // {'A','E','F','G','H','P'}
  16.         int length = arr.length;
  17.         this.N = length;
  18.         this.V = Arrays.copyOf(arr, length);
  19.         // 构建图中的结点
  20.         vertexs = new Vertex[length];
  21.         for (int i = 0; i < length; i++) {
  22.             vertexs[i] = new Vertex(0, this.V[i]);
  23.         }
  24.         this.adj = new List[length];
  25.         for (int i = 0; i < this.N; i++) {
  26.             this.adj[i] = new ArrayList<>();
  27.         }
  28.     }
  30.     // 打印邻接矩阵
  31.     public void show() {
  32.         for (int i = 0; i < this.N; i++) {
  33.             System.out.format("%-4c", this.V[i]);
  34.             List<Integer> linkedList = this.adj[i];
  35.             for (int j = 0; j < linkedList.size(); j++) {
  36.                 System.out.print(this.V[linkedList.get(j)] + "---->");
  37.             }
  38.             System.out.println();
  39.             System.out.format("%-4c", this.V[i]);
  40.             for (int j = 0; j < linkedList.size(); j++) {
  41.                 System.out.print(linkedList.get(j) + "---->");
  42.             }
  43.             System.out.println();
  44.         }
  45.     }
  48.     public void bfs(int startIndex){
  49.         boolean visited[] = new boolean[this.N];
  50.         List<List<Integer>> result = new ArrayList<>();
  51.         // 使用队列
  52.         Queue<AbstractMap.SimpleEntry<Integer,Integer>> queue = new LinkedList<>();
  53.         // 将开始顶点入队
  54.         queue.add(new AbstractMap.SimpleEntry<>(startIndex,0));
  55.         // 设置startIndex已经被访问
  56.         visited[startIndex]=true;
  57.         while(!queue.isEmpty()){
  58.             AbstractMap.SimpleEntry<Integer,Integer> pair =  queue.poll();
  59.             int key = pair.getKey(); //顶点的索引
  61.             int val = pair.getValue();// 层
  63.             if(result.size() == val){
  64.                 ArrayList list = new ArrayList();
  65.                 result.add(list);
  66.             }
  67.             List<Integer> levelList = result.get(val);
  68.             levelList.add(key);
  69.            // 找和key顶点直接相连的的索引
  70.            List<Integer> list =  this.adj[key];
  71.            for(int i=0;i<list.size();i++){
  72.                if(!visited[list.get(i)]){
  73.                    queue.add(new AbstractMap.SimpleEntry(list.get(i),val+1));
  74.                    visited[list.get(i)]=true;
  75.                }
  76.            }
  77.         }
  78.        for(int i=0;i<result.size();i++){
  79.            System.out.println("level:"+(i+1));
  80.            for(int j=0;j<result.get(i).size();j++){
  81.                System.out.format("%-4d",result.get(i).get(j));
  82.            }
  83.            System.out.println();
  84.        }
  85.     }
  89.     public void dfs(int startIndex,int endIndex){
  90.         //创建一个数组，用来记录是否已经被访问
  91.         boolean visited[] = new boolean[this.N];
  92.         // 标记开始结点已经被访问过
  93.         LinkedList<Character> path = new LinkedList<>();
  94.         dfs(startIndex,endIndex,visited,path);
  95.     }
  97.     // 递归向下去找
  98.     private void dfs(int startIndex,int endIndex,boolean[] visited, LinkedList<Character> path){
  99.         // 递归终止的条件
  100.         if(startIndex == endIndex){
  101.             path.offerLast(this.V[startIndex]);
  102.             System.out.println(path);
  103.             // 从路径的尾部删掉最后的顶点
  104.             path.pollLast();
  105.             return;
  106.         }
  107.         // 将当前顶点加到路径中去
  108.         path.offer(this.V[startIndex]);
  109.         // 标识startIndex已经被访问了
  110.         visited[startIndex]=true;
  111.         //  递归操作
  112.         // 1、先找和startIndex直接连接的顶点有哪些
  113.         List<Integer> list = this.adj[startIndex];
  114.         // 2、处理每一个直接连接的顶点
  115.         for(int i=0;i<list.size();i++){
  116.             if(!visited[list.get(i)]){
  117.                 dfs(list.get(i),endIndex,visited,path);
  118.             }
  119.         }
  120.         visited[startIndex]=false; // 回溯
  121.         path.pollLast();
  122.     }
  125.     private class Vertex {
  126.         char v;
  127.         int index;
  129.         //权值
  130.         int weight;
  132.         public Vertex(int index, char v, int weight) {
  133.             this.index = index;
  134.             this.v = v;
  135.             this.weight = weight;
  136.         }
  138.         public Vertex(int index, char v) {
  139.             this(index, v, 1);
  140.         }
  141.     }
  143.     public static void main(String[] args) {
  144.         char arr[] = {'A', 'E', 'F', 'G', 'H', 'P' };
  145.         Graph03 graph03 = new Graph03(arr);
  146.         // 邻接表
  147.         List<Integer>[] adj = graph03.adj;
  148.         adj[0].add(1);
  149.         adj[0].add(2);
  150.         adj[0].add(3);
  151.         adj[1].add(0);
  152.         adj[1].add(3);
  153.         adj[1].add(4);
  154.         adj[2].add(0);
  155.         adj[3].add(0);
  156.         adj[3].add(1);
  157.         adj[3].add(4);
  158.         adj[3].add(5);
  159.         adj[4].add(1);
  160.         adj[4].add(3);
  161.         adj[4].add(5);
  162.         adj[5].add(3);
  163.         adj[5].add(4);
  165.         graph03.bfs(5);
  166.     }
  168. }

迪杰斯特拉算法

概念：即先求出长度最短的一条最短路径，再参照它求出长度次短的一条最短路径，依次类推，直到从源点v 到其它各顶点的最短路径全部求出为止。

54002ef78cd14eb99bbcac9c27b1f757.png

假设我们求A点到各点的最短距离

fefc5a9639d04cdaa30435cd93635bd8.png 迪杰斯特拉算法过程（原理）

  1. package graphtheory;
  4. import java.util.*;
  6. // 图的单源最最短路径-迪杰斯特拉算法（从一个顶点到图中各个顶点的最短距离）
  7. public class Graph04 {
  8.     private char[] V;
  9.     // 顶点数组
  10.     private Vertex[] vertexs;
  11.     private int N;
  12.     // 邻接表
  13.     private List<AbstractMap.SimpleEntry<Integer, Integer>>[] adj; // key:顶点索引，val:权值
  15.     public Graph04(char[] arr) { // {'A','E','F','G','H','P'}
  16.         int length = arr.length;
  17.         this.N = length;
  18.         this.V = Arrays.copyOf(arr, length);
  19.         // 构建图中的结点
  20.         vertexs = new Vertex[length];
  21.         for (int i = 0; i < length; i++) {
  22.             vertexs[i] = new Vertex(i, this.V[i]);
  23.         }
  24.         this.adj = new List[length];
  25.         for (int i = 0; i < this.N; i++) {
  26.             this.adj[i] = new ArrayList<>();
  27.         }
  28.     }
  31.     public int[] dijkstra(int sourceIndex) {
  32.         // 1、创建距离表
  33.         int[] dist = new int[this.N];
  34.         Arrays.fill(dist, Integer.MAX_VALUE);
  35.         // 2、创建一个标识顶点是否被访问的数组
  36.         boolean[] visited = new boolean[this.N];
  37.         // 3、初始化距离表
  38.         // 3-1
  39.         dist[sourceIndex] = 0; // 自身到自身的距离
  40.         visited[sourceIndex] = true;
  41.         // 3-2、找和sourceIndex直接相连的顶点
  42.         List<AbstractMap.SimpleEntry<Integer, Integer>> list = this.adj[sourceIndex];
  43.         for (int i = 0; i < list.size(); i++) {
  44.             AbstractMap.SimpleEntry<Integer, Integer> vertex = list.get(i);
  45.             int key = vertex.getKey();//顶点索引
  46.             int val = vertex.getValue();//权值
  47.             // 3-3  更新距离表
  48.             dist[key] = val;
  49.         }
  51.         for (int k = 1; k < this.N; k++) {
  52.             //4、在上述的最短路径dist[]中，从未被访问的顶点中选一条最短的路径长度
  53.             int minDist = Integer.MAX_VALUE;
  54.             int minDistIndex = -1;
  55.             for (int i = 0; i < this.N; i++) {
  56.                 if (!visited[i] && dist[i] != Integer.MAX_VALUE && dist[i] < minDist) {
  57.                     minDist = dist[i];
  58.                     minDistIndex = i;
  59.                 }
  60.             }
  62.             // 最最短的路径长度所在的顶点与其它顶点都没有相连
  63.             if (minDistIndex == -1) {
  64.                 break;
  65.             }
  67.             //5、更新距离表()
  68.             // 5-1 将最最短的路径长度所在的顶点设置成已访问
  69.             visited[minDistIndex] = true;
  70.             // 5-2 找到和最短路径长度所在顶点直接相连的顶点
  71.             List<AbstractMap.SimpleEntry<Integer, Integer>> list2 = this.adj[minDistIndex];
  72.             // 5-3 minDist+权值与距离表中的数据进行比较
  73.             for (int i = 0; i < list2.size(); i++) {
  74.                 AbstractMap.SimpleEntry<Integer, Integer> vertex = list2.get(i);
  75.                 int key = vertex.getKey();//顶点索引
  76.                 int val = vertex.getValue();//权值
  77.                 int newVal = minDist + val;
  78.                 if (!visited[key] && newVal < dist[key]) {
  79.                     dist[key] = newVal;
  80.                 }
  81.             }
  82.         }
  83.         return dist;
  84.     }
  87.     private class Vertex {
  88.         char v;
  89.         int index;
  91.         public Vertex(int index, char v) {
  92.             this.index = index;
  93.             this.v = v;
  94.         }
  95.     }
  97.     public static void main(String[] args) {
  98.         char arr[] = {'A', 'E', 'F', 'G', 'H', 'P'};
  99.         Graph04 graph04 = new Graph04(arr);
  100.         // 邻接表
  101.         List<AbstractMap.SimpleEntry<Integer, Integer>>[] adj = graph04.adj;
  103.         adj[0].add(new AbstractMap.SimpleEntry<>(1, 5));
  104.         adj[0].add(new AbstractMap.SimpleEntry<>(2, 4));
  105.         adj[0].add(new AbstractMap.SimpleEntry<>(5, 2));
  107.         adj[1].add(new AbstractMap.SimpleEntry<>(0, 5));
  108.         adj[1].add(new AbstractMap.SimpleEntry<>(5, 1));
  109.         adj[1].add(new AbstractMap.SimpleEntry<>(4, 3));
  111.         adj[2].add(new AbstractMap.SimpleEntry<>(0, 4));
  112.         adj[3].add(new AbstractMap.SimpleEntry<>(4, 3));
  113.         adj[3].add(new AbstractMap.SimpleEntry<>(5, 4));
  114.         adj[4].add(new AbstractMap.SimpleEntry<>(1, 3));
  115.         adj[4].add(new AbstractMap.SimpleEntry<>(5, 2));
  116.         adj[4].add(new AbstractMap.SimpleEntry<>(3, 3));
  117.         adj[5].add(new AbstractMap.SimpleEntry<>(0, 2));
  118.         adj[5].add(new AbstractMap.SimpleEntry<>(1, 1));
  119.         adj[5].add(new AbstractMap.SimpleEntry<>(4, 2));
  120.         adj[5].add(new AbstractMap.SimpleEntry<>(3, 4));
  122.         int[] dist = graph04.dijkstra(0);
  123.         System.out.println(Arrays.toString(dist));
  124.     }
  126. }

怎么样才能求出我们距离最短的路径呢？

我们这里需要一个前置顶点表进行记录：

7201ab7e59f54d8fbb9a9ba6f777d453.png

分图：

92069148ab954ab09c485a94374f131e.png

5de6ee6d68e746f3b1612e53dc6b3346.png

  1. package graphtheory;
  4. import java.util.*;
  6. // 图的单源最最短路径-迪杰斯特拉算法（从一个顶点到图中各个顶点的最短距离）
  7. public class Graph04 {
  8.     private char[] V;
  9.     // 顶点数组
  10.     private Vertex[] vertexs;
  11.     private int N;
  12.     // 邻接表
  13.     private List<AbstractMap.SimpleEntry<Integer, Integer>>[] adj; // key:顶点索引，val:权值
  15.     // 1、创建距离表
  16.     private int[] dist;
  17.     private int[] pre;
  18.     public Graph04(char[] arr) { // {'A','E','F','G','H','P'}
  19.         int length = arr.length;
  20.         this.N = length;
  21.         this.V = Arrays.copyOf(arr, length);
  23.         this.dist = new int[this.N];
  24.         Arrays.fill(dist, Integer.MAX_VALUE);
  25.         // 创建最短路径的前驱顶点表(为了表示最短路径)
  26.         this.pre=new int[this.N];
  27.         Arrays.fill(this.pre,-1);
  28.         // 构建图中的结点
  29.         vertexs = new Vertex[length];
  30.         for (int i = 0; i < length; i++) {
  31.             vertexs[i] = new Vertex(0, this.V[i]);
  32.         }
  33.         this.adj = new List[length];
  34.         for (int i = 0; i < this.N; i++) {
  35.             this.adj[i] = new ArrayList<>();
  36.         }
  37.     }
  40.     public void dijkstra(int sourceIndex) {
  43.         // 2、创建一个标识顶点是否被访问的数组
  44.         boolean[] visited = new boolean[this.N];
  45.         // 3、初始化距离表
  46.         // 3-1
  47.         dist[sourceIndex] = 0; // 自身到自身的距离
  48.         visited[sourceIndex] = true;
  49.         // 3-2、找和sourceIndex直接相连的顶点
  50.         List<AbstractMap.SimpleEntry<Integer, Integer>> list = this.adj[sourceIndex];
  51.         for (int i = 0; i < list.size(); i++) {
  52.             AbstractMap.SimpleEntry<Integer, Integer> vertex = list.get(i);
  53.             int key = vertex.getKey();//顶点索引
  54.             int val = vertex.getValue();//权值
  55.             // 3-3  更新距离表
  56.             this.dist[key] = val;
  57.             // 更新前驱顶点表
  58.             this.pre[key]=sourceIndex;
  59.         }
  61.         for (int k = 1; k < this.N; k++) {
  62.             //4、在上述的最短路径dist[]中，从未被访问的顶点中选一条最短的路径长度
  63.             int minDist = Integer.MAX_VALUE;
  64.             int minDistIndex = -1;
  65.             for (int i = 0; i < this.N; i++) {
  66.                 if (!visited[i] && dist[i] != Integer.MAX_VALUE && dist[i] < minDist) {
  67.                     minDist = dist[i];
  68.                     minDistIndex = i;
  69.                 }
  70.             }
  72.             // 最最短的路径长度所在的顶点与其它顶点都没有相连
  73.             if (minDistIndex == -1) {
  74.                 break;
  75.             }
  77.             //5、更新距离表()
  78.             // 5-1 将最最短的路径长度所在的顶点设置成已访问
  79.             visited[minDistIndex] = true;
  80.             // 5-2 找到和最短路径长度所在顶点直接相连的顶点
  81.             List<AbstractMap.SimpleEntry<Integer, Integer>> list2 = this.adj[minDistIndex];
  82.             // 5-3 minDist+权值与距离表中的数据进行比较
  83.             for (int i = 0; i < list2.size(); i++) {
  84.                 AbstractMap.SimpleEntry<Integer, Integer> vertex = list2.get(i);
  85.                 int key = vertex.getKey();//顶点索引
  86.                 int val = vertex.getValue();//权值
  87.                 int newVal = minDist + val;
  88.                 if (!visited[key] && newVal < dist[key]) {
  89.                     this.dist[key] = newVal;
  90.                     // 更新前驱顶点表
  91.                     this.pre[key] = minDistIndex;
  92.                 }
  93.             }
  94.         }
  95.     }
  97.     public void showDist(){
  98.         System.out.println(Arrays.toString(this.dist));
  99.     }
  101.     public void getMinDist(int sourceIndex ,int targetIndex){
  102.         Stack<Integer> stack = new Stack<>();
  103.         stack.push(targetIndex);
  104.         int preIndex = this.pre[targetIndex];
  105.         while(preIndex !=-1 && preIndex!=sourceIndex){
  106.             stack.push(preIndex);
  107.             preIndex = this.pre[preIndex];
  108.         }
  109.         // 将 sourceIndex放入栈
  110.         if(preIndex !=-1){
  111.             stack.push(sourceIndex);
  112.         }
  114.         // 出栈
  115.         StringBuilder res = new StringBuilder();
  116.         while(!stack.isEmpty()){
  117.             res.append(this.V[stack.pop()]+"-->");
  118.         }
  119.         System.out.println(res);
  120.     }
  123.     private class Vertex {
  124.         char v;
  125.         int index;
  127.         public Vertex(int index, char v) {
  128.             this.index = index;
  129.             this.v = v;
  130.         }
  131.     }
  133.     public static void main(String[] args) {
  134.         char arr[] = {'A', 'E', 'F', 'G', 'H', 'P'};
  135.         Graph04 graph04 = new Graph04(arr);
  136.         // 邻接表
  137.         List<AbstractMap.SimpleEntry<Integer, Integer>>[] adj = graph04.adj;
  139.         adj[0].add(new AbstractMap.SimpleEntry<>(1, 5));
  140.         adj[0].add(new AbstractMap.SimpleEntry<>(2, 4));
  141.         adj[0].add(new AbstractMap.SimpleEntry<>(5, 2));
  143.         adj[1].add(new AbstractMap.SimpleEntry<>(0, 5));
  144.         adj[1].add(new AbstractMap.SimpleEntry<>(5, 1));
  145.         adj[1].add(new AbstractMap.SimpleEntry<>(4, 3));
  147.         adj[2].add(new AbstractMap.SimpleEntry<>(0, 4));
  148.         adj[3].add(new AbstractMap.SimpleEntry<>(4, 3));
  149.         adj[3].add(new AbstractMap.SimpleEntry<>(5, 4));
  150.         adj[4].add(new AbstractMap.SimpleEntry<>(1, 3));
  151.         adj[4].add(new AbstractMap.SimpleEntry<>(5, 2));
  152.         adj[4].add(new AbstractMap.SimpleEntry<>(3, 3));
  153.         adj[5].add(new AbstractMap.SimpleEntry<>(0, 2));
  154.         adj[5].add(new AbstractMap.SimpleEntry<>(1, 1));
  155.         adj[5].add(new AbstractMap.SimpleEntry<>(4, 2));
  156.         adj[5].add(new AbstractMap.SimpleEntry<>(3, 4));
  158.         int sourceIndex = 5;
  159.         graph04.dijkstra(sourceIndex);
  160.         graph04.showDist();
  162.         int targetIndex = 3;
  163.         // 求从源到目标顶点的最短路径
  164.         graph04.getMinDist(sourceIndex,targetIndex);
  165.     }
  167. }

弗洛伊德算法

具体思想：邻接矩阵dist储存路径，同时最终状态代表点点的最短路径。如果没有直接相连的两点那么默认为一个很大的值，而自身到自身的长度为0.

f89134e41bde4aadae0c6da3d948a1f2.png

A和B不认识，所以A找不到B,但是这时候A的朋友D来了，说他可以介绍B给A认识，所以A就通过D找到了B

782f6bf43dc442c0b62c1b0ba0baa6ed.png

弗洛伊德算法就是用了这样的思想

daac81fad51f4db18a7e0b066f57d92d.png30a436ca3a814e4db3bfc1f94f7d09bc.png

  • 把第1个到第n个点依次加入图中。每个点加入进行试探是否有路径长度被更改。
  • 而上述试探具体方法为遍历图中每一个点(i,j双重循环)，判断每一个点对距离，是否因为加入的点而发生最小距离变化。如果发生改变，那么两点(i,j)距离就更改。
  • 转移方程：:dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j])

792e1ff85d17446bab075834714ed296.png

b7716d962e6a4f56bbfadc1b1d1024b1.png

baa8aa4054a54d8d8fed38b8a8f4efb4.png

  1. package graphtheory;
  4. import java.util.*;
  6. // 图的多源最最短路径-弗洛伊德算法Floyd（从任意顶点到图中各个顶点的最短距离）
  7. public class Graph05 {
  8.     private char[] V;
  9.     // 顶点数组
  10.     private Vertex[] vertexs;
  11.     private int N;
  12.     // 邻接表
  13.     private List<AbstractMap.SimpleEntry<Integer, Integer>>[] adj; // key:顶点索引，val:权值
  15.     private int[][] dists;
  17.     public Graph05(char[] arr) { // {'A','E','F','G','H','P'}
  18.         int length = arr.length;
  19.         this.N = length;
  20.         this.V = Arrays.copyOf(arr, length);
  21.         // 构建图中的结点
  22.         vertexs = new Vertex[length];
  23.         for (int i = 0; i < length; i++) {
  24.             vertexs[i] = new Vertex(0, this.V[i]);
  25.         }
  26.         this.adj = new List[length];
  27.         for (int i = 0; i < this.N; i++) {
  28.             this.adj[i] = new ArrayList<>();
  29.         }
  30.         this.dists = new int[this.N][this.N];
  31.         for (int i = 0; i < this.N; i++) {
  32.             for (int j = 0; j < this.N; j++) {
  33.                 if (i == j) {
  34.                     this.dists[i][j] = 0;
  35.                 } else {
  36.                     this.dists[i][j] = Integer.MAX_VALUE;
  37.                 }
  38.             }
  39.         }
  40.     }
  43.     private class Vertex {
  44.         char v;
  45.         int index;
  47.         public Vertex(int index, char v) {
  48.             this.index = index;
  49.             this.v = v;
  50.         }
  51.     }
  53.     public void floyd() {
  54.         // 对dists进一步初始化
  55.         for (int i = 0; i < this.N; i++) {
  56.             List<AbstractMap.SimpleEntry<Integer, Integer>> list = this.adj[i];
  57.             for (int j = 0; j < list.size(); j++) {
  58.                 AbstractMap.SimpleEntry<Integer, Integer> pair = list.get(j);
  59.                 int key = pair.getKey();
  60.                 int val = pair.getValue();
  61.                 this.dists[i][key] = val;
  62.             }
  63.         }
  65.         // 将每个顶点加到二维数组中（是给每个二维数组中的每个元素都加） 相当于矩阵，给每个元素进行相同的操作
  66.         for (int i = 0; i < this.N; i++) { // 表示的添加顶点的索引
  67.             for (int m = 0; m < this.N; m++) {
  68.                 //同行不用进行操作
  69.                 if (m == i) {
  70.                     continue;
  71.                 }
  72.                 for (int n = 0; n < this.N; n++) {
  73.                 //距离无穷大也不用进行操作
  74.                     if (this.dists[m][i] != Integer.MAX_VALUE && this.dists[i][n] != Integer.MAX_VALUE) {
  75.                         this.dists[m][n] = Math.min(this.dists[m][n], this.dists[m][i] + this.dists[i][n]);
  76.                     }
  77.                 }
  78.             }
  79.         }
  80.         show();
  81.     }
  83.     private void show() {
  84.         System.out.format("%-4s", " ");
  85.         for (int i = 0; i < this.N; i++) {
  86.             System.out.format("%-4s", this.V[i]);
  87.         }
  88.         System.out.println();
  89.         for (int i = 0; i < this.N; i++) {
  90.             System.out.format("%-4s", this.V[i]);
  91.             for (int j = 0; j < this.N; j++) {
  92.                 System.out.format("%-4s", this.dists[i][j] == Integer.MAX_VALUE ? "-" : this.dists[i][j] + "");
  93.             }
  94.             System.out.println();
  95.         }
  96.     }
  98.     public static void main(String[] args) {
  99.         char arr[] = {'A', 'E', 'F', 'G', 'H', 'P'};
  100.         Graph05 graph05 = new Graph05(arr);
  101.         // 邻接表
  102.         List<AbstractMap.SimpleEntry<Integer, Integer>>[] adj = graph05.adj;
  104.         adj[0].add(new AbstractMap.SimpleEntry<>(1, 5));
  105.         adj[0].add(new AbstractMap.SimpleEntry<>(2, 4));
  106.         adj[0].add(new AbstractMap.SimpleEntry<>(5, 2));
  108.         adj[1].add(new AbstractMap.SimpleEntry<>(0, 5));
  109.         adj[1].add(new AbstractMap.SimpleEntry<>(5, 1));
  110.         adj[1].add(new AbstractMap.SimpleEntry<>(4, 3));
  112.         adj[2].add(new AbstractMap.SimpleEntry<>(0, 4));
  113.         adj[3].add(new AbstractMap.SimpleEntry<>(4, 3));
  114.         adj[3].add(new AbstractMap.SimpleEntry<>(5, 4));
  115.         adj[4].add(new AbstractMap.SimpleEntry<>(1, 3));
  116.         adj[4].add(new AbstractMap.SimpleEntry<>(5, 2));
  117.         adj[4].add(new AbstractMap.SimpleEntry<>(3, 3));
  118.         adj[5].add(new AbstractMap.SimpleEntry<>(0, 2));
  119.         adj[5].add(new AbstractMap.SimpleEntry<>(1, 1));
  120.         adj[5].add(new AbstractMap.SimpleEntry<>(4, 2));
  121.         adj[5].add(new AbstractMap.SimpleEntry<>(3, 4));
  123.         graph05.floyd();
  124.         int sourceIndex = 1;
  125.         int targetIndex = 3;
  127.     }
  129. }

发表评论

表情：
评论列表 （有 0 条评论，96人围观）

还没有评论，来说两句吧...

相关阅读

    相关 图论中的算法

    图论的概念：图论是数学的一个分支，它是以图为研究对象，图论中的图是由若干个给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些实体之间的某种特定的关系，用点代表实体，用

    小鱼儿小鱼儿/ 0 赞/ 97 阅读

    相关 图论

    一、图的常用概念 　　1、顶点（vertex） 　　2、边（edge） 　　3、路径 　　4、无向图：顶点之间的连接没有方向 　　![1007094-201909

    柔光的暖阳◎柔光的暖阳◎/ 0 赞/ 124 阅读

    相关 图论

    http://[blog.csdn.net/pipisorry/article/details/52518118][blog.csdn.net_pipisorry_articl

    清疚清疚/ 0 赞/ 330 阅读

    相关 图论算法

    Problem1一笔画问题 题目描述     给出一个图，求其欧拉回路（若没有回路，则求其欧拉路径），若不存在则输出‘No solution’ 输入     输入的第一

    妖狐艹你老母妖狐艹你老母/ 0 赞/ 335 阅读

    相关 图论 Floyd算法

    Floyd算法　　 　　时间复杂度O (n^3) 　　空间复杂度O (n^2) 用处 　　可以求任意两个点之间的最短路径长度。 　　得出的邻接矩阵存储 i 到 j 的

    青旅半醒青旅半醒/ 0 赞/ 338 阅读