一 无向图

无向图：边仅仅连接两个顶点，没有其他含义

1.1 无向图定义

  1. 相邻顶点
    1. 当两个顶点通过一条边相连时，我们称这两个顶点是相邻的，并且称这条边依附于这两个顶点。
  2. 度
    1. 某个顶点的度就是依附于该顶点的边的个数
  3. 子图
    1. ·是一幅图的所有边的子集(包含这些边依附的顶点)组成的图；
  4. 路径
    1. 是由边顺序连接的一系列的顶点组成
  5. 环
    1. 是一条至少含有一条边且终点和起点相同的路径
    2. image.png
  6. 连通
    1. 如果图中任意一个顶点都存在一条路径到达另外一个顶点，那么这幅图就称之为连通图
  7. 连通子图
    1. 一个非连通图由若干连通的部分组成，每一个连通的部分都可以称为该图的连通子图
    2. image.png

      1.2 实现原理

      要表示一幅图，只需要表示清楚以下两部分内容即可：
      1. 图中所有的顶点；
      2. 所有连接顶点的边；
      常见的图的存储结构有两种：邻接矩阵和邻接表

      1.2.1 邻接矩阵

  8. 使用一个V*V的二维数组int[V][V] adj,把索引的值看做是顶点；
    2. 如果顶点v和顶点w相连，我们只需要将adj[v][w]和adj[w][v]的值设置为1,否则设置为0即可。
    image.png
    很明显，邻接矩阵这种存储方式的空间复杂度是V^2的，如果我们处理的问题规模比较大的话，内存空间极有可能不够用。

    1.2.2 邻接表

    1.使用一个大小为V的数组 Queue[V] adj，把索引看做是顶点；
    2.每个索引处adj[v]存储了一个队列，该队列中存储的是所有与该顶点相邻的其他顶点
    image.png
    很明显，邻接表的空间并不是是线性级别的，所以后面我们一直采用邻接表这种存储形式来表示图。

    1.3 无向图代码

    ```java package com.ycc.data.structure.graph;

import com.ycc.data.structure.line.MyArrayQueue;

/**

  • 无向图 *
  • @author liaozx

  • @date 2020/9/19 */ public class Graph { //顶点数目 private final int V; //边的数目 private int E; //邻接表 private MyArrayQueue[] adj;

    public Graph(int V) {

    1.  //初始化顶点数量
    2.  this.V = V;
    3.  //初始化边的数量
    4.  this.E = 0;
    5.  //初始化邻接表
    6.  this.adj = new MyArrayQueue[V];
    7.  for (int i = 0; i < adj.length; i++) {
    8.      adj[i] = new MyArrayQueue<>();
    9.  }

    }

    //获取顶点数目 public int V() {

    1.  return V;

    }

    //获取边的数目 public int E() {

    1.  return E;

    }

    //向图中添加一条边 顶点v-顶点w public void addEdge(int v, int w) {

    1.  //在无向图中，边是没有方向的，所以该边既可以说是从v到w的边，又可以说是从w到v的边，因此，需要让w出现在v的邻接表中，并且还要让v出现在w的邻接表中
    2.  adj[v].enQueue(w);
    3.  adj[w].enQueue(v);
    4.  //边的数量+1
    5.  E++;

    }

    //获取和顶点v相邻的所有顶点 public MyArrayQueue adj(int v) {

    1.  //返回v所对应的邻接表即可
    2.  return adj[v];

    }

}

  1. <a name="i4up4"></a>
  2. ## 1.4 深度搜索
  3. 所谓的深度优先搜索，指的是在搜索时，如果遇到一个结点既有子结点，又有兄弟结点，那么先找子结点，然后找兄弟结点。例如 0-->6-->4-->5-->3
  4. <a name="CIBtz"></a>
  5. ### 1.4.1 实现原理
  6. ![image.png](https://cdn.nlark.com/yuque/0/2020/png/1502688/1600512182590-607781bc-09b0-451b-ba3a-e0f7774583ad.png?x-oss-process=image%2Fwatermark%2Ctype_d3F5LW1pY3JvaGVp%2Csize_10%2Ctext_5Lq66Ze05Zub5pyI5aSp%2Ccolor_FFFFFF%2Cshadow_50%2Ct_80%2Cg_se%2Cx_10%2Cy_10#align=left&display=inline&height=577&margin=%5Bobject%20Object%5D&name=image.png&originHeight=1154&originWidth=1354&size=394183&status=done&style=none&width=677)<br />很明显，在由于边是没有方向的，所以，如果4和5顶点相连，那么4会出现在5的相邻链表中，5也会出现在4的相邻链表中，那么为了不对顶点进行重复搜索，应该要有相应的标记来表示当前顶点有没有搜索过，可以使用一个布尔类型的数组 boolean[V] marked,索引代表顶点，值代表当前顶点是否已经搜索，如果已经搜索，标记为true，如果没有搜索，标记为false；
  7. <a name="F2OBi"></a>
  8. ### 1.4.2 代码实现
  9. ```java
  10. package com.ycc.data.structure.graph;
  12. import cn.itcast.algorithm.graph.Graph;
  14. /**
  15.  * 深度优先
  16.  * @author liaozx
  17.  * @date 2020/10/19
  18.  */
  19. public class DepthFirstSearch {
  20.     //索引代表顶点，值表示当前顶点是否已经被搜索
  21.     private boolean[] marked;
  22.     //记录有多少个顶点与s顶点相通
  23.     private int count;
  25.     //构造深度优先搜索对象，使用深度优先搜索找出G图中s顶点的所有相邻顶点
  26.     public DepthFirstSearch(cn.itcast.algorithm.graph.Graph G, int s) {
  27.         //初始化marked数组
  28.         this.marked = new boolean[G.V()];
  29.         //初始化跟顶点s相通的顶点的数量
  30.         this.count = 0;
  31.         dfs(G, s);
  32.     }
  34.     //使用深度优先搜索找出G图中v顶点的所有相通顶点
  35.     private void dfs(Graph G, int v) {
  36.         //把v顶点标识为已搜索
  37.         marked[v] = true;
  38.         for (Integer w : G.adj(v)) {
  39.             //判断当前w顶点有没有被搜索过，如果没有被搜索过，则递归调用dfs方法进行深度搜索
  40.             if (!marked[w]) {
  41.                 dfs(G, w);
  42.             }
  43.         }
  44.         //相通顶点数量+1
  45.         count++;
  46.     }
  48.     //判断w顶点与s顶点是否相通
  49.     public boolean marked(int w) {
  50.         return marked[w];
  51.     }
  53.     //获取与顶点s相通的所有顶点的总数
  54.     public int count() {
  55.         return count;
  56.     }
  58. }

1.4.3 测试代码

  1. package com.ycc.data.structure.graph.test;
  3. import cn.itcast.algorithm.graph.DepthFirstSearch;
  4. import cn.itcast.algorithm.graph.Graph;
  6. public class DepthFirstSearchTest {
  8.     public static void main(String[] args) {
  10.         //准备Graph对象
  11.         Graph G = new Graph(13);
  12.         G.addEdge(0,5);
  13.         G.addEdge(0,1);
  14.         G.addEdge(0,2);
  15.         G.addEdge(0,6);
  17.         G.addEdge(5,3);
  18.         G.addEdge(5,4);
  20.         G.addEdge(3,4);
  21.         G.addEdge(4,6);
  23.         G.addEdge(7,8);
  25.         G.addEdge(9,11);
  26.         G.addEdge(9,10);
  27.         G.addEdge(9,12);
  29.         G.addEdge(11,12);
  31.         //准备深度优先搜索对象
  32.         DepthFirstSearch search = new DepthFirstSearch(G, 0);
  34.         //测试与某个顶点相通的顶点数量
  35.         int count = search.count();
  36.         System.out.println("与起点0相通的顶点的数量为:"+count);
  39.         //测试某个顶点与起点是否相同
  40.         boolean marked1 = search.marked(5);
  41.         System.out.println("顶点5和顶点0是否相通："+marked1);
  44.         boolean marked2 = search.marked(7);
  45.         System.out.println("顶点7和顶点0是否相通："+marked2);
  47.     }
  48. }

1.5 广度搜索

所谓的深度优先搜索，指的是在搜索时，如果遇到一个结点既有子结点，又有兄弟结点，那么先找兄弟结点，然后找子结点。

1.5.1 实现原理

image.png

1.5.2 代码实现

  1. package com.ycc.data.structure.graph;
  3. import com.ycc.data.structure.line.MyArrayQueue;
  5. /**
  6.  * 广度优先
  7.  *
  8.  * @author liaozx
  9.  * @date 2020/10/19
  10.  */
  11. public class BreadthFirstSearch {
  12.     //索引代表顶点，值表示当前顶点是否已经被搜索
  13.     private final boolean[] marked;
  14.     //记录有多少个顶点与s顶点相通
  15.     private int count;
  16.     //用来存储待搜索邻接表的点
  17.     private final MyArrayQueue<Integer> waitSearch;
  19.     //构造广度优先搜索对象，使用广度优先搜索找出G图中s顶点的所有相邻顶点
  20.     public BreadthFirstSearch(Graph G, int s) {
  21.         this.marked = new boolean[G.V()];
  22.         this.count = 0;
  23.         this.waitSearch = new MyArrayQueue<Integer>();
  24.         bfs(G, s);
  25.     }
  27.     //使用广度优先搜索找出G图中v顶点的所有相邻顶点
  28.     private void bfs(Graph G, int v) {
  29.         //把当前顶点v标识为已搜索
  30.         marked[v] = true;
  31.         //让顶点v进入队列，待搜索
  32.         waitSearch.enQueue(v);
  33.         //通过循环，如果队列不为空，则从队列中弹出一个待搜索的顶点进行搜索
  34.         while (!waitSearch.isEmpty()) {
  35.             //弹出一个待搜索的顶点
  36.             Integer wait = waitSearch.deQueue();
  37.             MyArrayQueue queue = G.adj(wait);
  38.             //遍历wait顶点的邻接表
  39.             for (int i = 0; i < queue.length(); i++) {
  40.                 Integer integer = (Integer) queue.get(i);
  41.                 if (!marked[integer]) {
  42.                     //如果没有被搜索则递归调用搜索
  43.                     bfs(G, integer);
  44.                 }
  45.             }
  46.         }
  47.         //让相通的顶点+1；
  48.         count++;
  50.     }
  52.     //判断w顶点与s顶点是否相通
  53.     public boolean marked(int w) {
  54.         return marked[w];
  55.     }
  57.     //获取与顶点s相通的所有顶点的总数
  58.     public int count() {
  59.         return count;
  60.     }
  61. }

1.5.3 测试代码

  1. package com.ycc.data.structure.graph.test;
  4. import com.ycc.data.structure.graph.BreadthFirstSearch;
  5. import com.ycc.data.structure.graph.Graph;
  7. public class BreadthFirstSearchTest {
  9.     public static void main(String[] args) {
  11.         //准备Graph对象
  12.         Graph G = new Graph(13);
  14.         G.addEdge(0, 5);
  15.         G.addEdge(0, 1);
  16.         G.addEdge(0, 2);
  17.         G.addEdge(0, 6);
  19.         G.addEdge(5, 3);
  20.         G.addEdge(5, 4);
  22.         G.addEdge(3, 4);
  24.         G.addEdge(4, 6);
  26.         G.addEdge(7, 8);
  28.         G.addEdge(9, 11);
  29.         G.addEdge(9, 10);
  30.         G.addEdge(9, 12);
  32.         G.addEdge(11, 12);
  33.         //准备深度优先搜索对象
  34.         BreadthFirstSearch search = new BreadthFirstSearch(G, 0);
  36.         //测试与某个顶点相通的顶点数量
  37.         int count = search.count();
  38.         System.out.println("与起点0相通的顶点的数量为:" + count);
  40.         //测试某个顶点与起点是否相同
  41.         boolean marked1 = search.marked(5);
  42.         System.out.println("顶点5和顶点0是否相通：" + marked1);
  44.         boolean marked2 = search.marked(7);
  45.         System.out.println("顶点7和顶点0是否相通：" + marked2);
  47.     }
  48. }

1.6 案例交通

某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。目前的道路状况，9号城市和10号城市是否相通？9号城市和8号城市是否相通？
在我们的测试数据文件夹中有一个trffic_project.txt文件，它就是诚征道路统计表，下面是对数据的解释：
image.png
总共有20个城市，目前已经修改好了7条道路，问9号城市和10号城市是否相通？9号城市和8号城市是否相通？

  1. package com.ycc.data.structure.graph.test;
  4. import com.ycc.data.structure.graph.DepthFirstSearch;
  5. import com.ycc.data.structure.graph.Graph;
  7. /**
  8.  * @author liaozx
  9.  * @date 2020/10/17
  10.  */
  11. public class TrafficProjectTest {
  13.     public static void main(String[] args) throws Exception {
  16.         //构建一个Graph对象
  17.         Graph graph = new Graph(20);
  18.         //0 1
  19.         //6 9
  20.         //3 8
  21.         //5 11
  22.         //2 12
  23.         //6 10
  24.         //4 8
  25.         graph.addEdge(0, 1);
  26.         graph.addEdge(6, 9);
  27.         graph.addEdge(3, 8);
  28.         graph.addEdge(5, 11);
  29.         graph.addEdge(2, 12);
  30.         graph.addEdge(6, 10);
  31.         graph.addEdge(4, 8);
  32.         //构建一个深度优先搜索对象，起点设置为顶点9
  33.         DepthFirstSearch search = new DepthFirstSearch(graph, 9);
  34.         //调用marked方法，判断8顶点和10顶点是否与起点9相通
  35.         System.out.println("顶点8和顶点9是否相通：" + search.marked(8));
  36.         System.out.println("顶点10和顶点9是否相通：" + search.marked(10));
  38.     }
  39. }

1.7 路径查找

1.7.1 路径查找原理

我们实现路径查找，最基本的操作还是得遍历并搜索图，所以，我们的实现暂且基于深度优先搜索来完成。其搜索的过程是比较简单的。我们添加了edgeTo[]整型数组，这个整型数组会记录从每个顶点回到起点s的路径。如果我们把顶点设定为0，那么它的搜索可以表示为下图：
image.png
image.png
image.png

1.7.2 代码实现

  1. package com.ycc.data.structure.graph;
  3. import com.ycc.data.structure.line.MyArrayQueue;
  4. import com.ycc.data.structure.line.MyArrayStack;
  6. public class DepthFirstPaths {
  7.     //索引代表顶点，值表示当前顶点是否已经被搜索
  8.     private boolean[] marked;
  9.     //起点
  10.     private int s;
  11.     //索引代表顶点，值代表从起点s到当前顶点路径上的最后一个顶点
  12.     private int[] edgeTo;
  14.     //构造深度优先搜索对象，使用深度优先搜索找出G图中起点为s的所有路径
  15.     public DepthFirstPaths(Graph G, int s) {
  16.         //初始化marked数组
  17.         this.marked = new boolean[G.V()];
  18.         //初始化起点
  19.         this.s = s;
  20.         //初始化edgeTo数组
  21.         this.edgeTo = new int[G.V()];
  23.         dfs(G, s);
  24.     }
  26.     //使用深度优先搜索找出G图中v顶点的所有相邻顶点
  27.     private void dfs(Graph G, int v) {
  28.         //把v表示为已搜索
  29.         marked[v] = true;
  30.         //遍历顶点v的邻接表，拿到每一个相邻的顶点，继续递归搜索
  31.         MyArrayQueue<Integer> queue = G.adj(v);
  32.         for (int i = 0; i < queue.length(); i++) {
  33.             //如果顶点w没有被搜索，则继续递归搜索
  34.             Integer w = queue.get(i);
  35.             if (!marked[w]) {
  36.                 edgeTo[w] = v;//到达顶点w的路径上的最后一个顶点是v
  37.                 dfs(G, w);
  38.             }
  39.         }
  40.     }
  42.     //判断w顶点与s顶点是否存在路径
  43.     public boolean hasPathTo(int v) {
  44.         return marked[v];
  45.     }
  47.     //找出从起点s到顶点v的路径(就是该路径经过的顶点)
  48.     public MyArrayStack<Integer> pathTo(int v) {
  49.         if (!hasPathTo(v)) {
  50.             return null;
  51.         }
  52.         //创建栈对象，保存路径中的所有顶点
  53.         MyArrayStack<Integer> path = new MyArrayStack<>();
  54.         //通过循环，从顶点v开始，一直往前找，到找到起点为止
  55.         for (int x = v; x != s; x = edgeTo[x]) {
  56.             path.push(x);
  57.         }
  58.         //把起点s放到栈中
  59.         path.push(s);
  60.         return path;
  61.     }
  64. }

1.8.3 测试代码

  1. package com.ycc.data.structure.graph.test;
  4. import com.ycc.data.structure.graph.DepthFirstPaths;
  5. import com.ycc.data.structure.graph.Graph;
  6. import com.ycc.data.structure.line.MyArrayStack;
  8. public class DepthFirstPathsTest {
  10.     public static void main(String[] args) throws Exception {
  12.         //根据第一行数据构建一副图Graph
  13.         Graph graph = new Graph(6);
  14.         //0 2
  15.         //0 1
  16.         //2 1
  17.         //2 3
  18.         //2 4
  19.         //3 5
  20.         //3 4
  21.         //0 5
  22.         graph.addEdge(0, 2);
  23.         graph.addEdge(0, 1);
  24.         graph.addEdge(2, 1);
  25.         graph.addEdge(2, 3);
  26.         graph.addEdge(2, 4);
  27.         graph.addEdge(3, 5);
  28.         graph.addEdge(3, 4);
  29.         graph.addEdge(0, 5);
  31.         //构建路径查找对象，并设置起点为0
  32.         DepthFirstPaths paths = new DepthFirstPaths(graph, 0);
  34.         //调用 pathTo(4)，找到从起点0到终点4的路径，返回Stack
  35.         MyArrayStack<Integer> stack = paths.pathTo(4);
  36.         StringBuilder sb = new StringBuilder();
  37.         //遍历栈对象
  38.         for (int i = 0; i < stack.length(); i++) {
  39.             sb.append(stack.get(i) + "-");
  40.         }
  41.         sb.deleteCharAt(sb.length() - 1);
  42.         System.out.println(sb);
  43.     }
  44. }

1.8 加权无向图

加权无向图是一种为每条边关联一个权重值或是成本的图模型。这种图能够自然地表示许多应用。在一副航空图中，边表示航线，权值则可以表示距离或是费用。在一副电路图中，边表示导线，权值则可能表示导线的长度即成本，或是信号通过这条先所需的时间。此时我们很容易就能想到，最小成本的问题，例如，从西安飞纽约，怎样飞才能使时间成本最低或者是金钱成本最低？
在下图中，从顶点0到顶点4有三条路径，分别为0-2-3-4,0-2-4,0-5-3-4,那我们如果要通过那条路径到达4顶点最好呢？此时就要考虑，那条路径的成本最低。
image.png

1.8.1 加权无向图边

  1. package com.ycc.data.structure.graph;
  3. /**
  4.  * 带权重的边
  5.  *
  6.  * @author liaozx
  7.  * @date 2020/10/17
  8.  */
  9. public class Edge implements Comparable<Edge> {
  10.     private final int v;//顶点一
  11.     private final int w;//顶点二
  12.     private final double weight;//当前边的权重
  14.     //通过顶点v和w，以及权重weight值构造一个边对象
  15.     public Edge(int v, int w, double weight) {
  16.         this.v = v;
  17.         this.w = w;
  18.         this.weight = weight;
  19.     }
  21.     //获取边的权重值
  22.     public double weight() {
  23.         return weight;
  24.     }
  26.     //获取边上的一个点
  27.     public int either() {
  28.         return v;
  29.     }
  31.     //获取边上除了顶点vertex外的另外一个顶点
  32.     public int other(int vertex) {
  33.         if (vertex == v) {
  34.             return w;
  35.         } else {
  36.             return v;
  37.         }
  38.     }
  40.     @Override
  41.     public int compareTo(Edge that) {
  42.         //使用一个遍历记录比较的结果
  43.         int cmp;
  45.         if (this.weight() > that.weight()) {
  46.             //如果当前边的权重值大，则让cmp=1；
  47.             cmp = 1;
  48.         } else if (this.weight() < that.weight()) {
  49.             //如果当前边的权重值小，则让cmp=-1；
  50.             cmp = -1;
  51.         } else {
  52.             //如果当前边的权重值和that边的权重值一样大，则让cmp=0
  53.             cmp = 0;
  54.         }
  55.         return cmp;
  56.     }
  57. }

1.8.2 加权无向图

  1. package com.ycc.data.structure.graph;
  4. import com.ycc.data.structure.line.MyArrayQueue;
  5. /**
  6.  * 加权无向图
  7.  *
  8.  * @author liaozx
  9.  * @date 2020/10/17
  10.  */
  11. public class EdgeWeightedGraph {
  12.     //顶点总数
  13.     private final int V;
  14.     //边的总数
  15.     private int E;
  16.     //邻接表
  17.     private MyArrayQueue<Edge>[] adj;
  19.     //创建一个含有V个顶点的空加权无向图
  20.     public EdgeWeightedGraph(int V) {
  21.         //初始化顶点数量
  22.         this.V = V;
  23.         //初始化边的数量
  24.         this.E = 0;
  25.         //初始化邻接表
  26.         this.adj = new MyArrayQueue[V];
  27.         for (int i = 0; i < adj.length; i++) {
  28.             adj[i] = new MyArrayQueue<Edge>();
  29.         }
  31.     }
  33.     //获取图中顶点的数量
  34.     public int V() {
  35.         return V;
  36.     }
  38.     //获取图中边的数量
  39.     public int E() {
  40.         return E;
  41.     }
  44.     //向加权无向图中添加一条边e
  45.     public void addEdge(Edge e) {
  46.         //需要让边e同时出现在e这个边的两个顶点的邻接表中
  47.         int v = e.either();
  48.         int w = e.other(v);
  50.         adj[v].enQueue(e);
  51.         adj[w].enQueue(e);
  53.         //边的数量+1
  54.         E++;
  55.     }
  57.     //获取和顶点v关联的所有边
  58.     public MyArrayQueue<Edge> adj(int v) {
  59.         return adj[v];
  60.     }
  62.     //获取加权无向图的所有边
  63.     public MyArrayQueue<Edge> edges() {
  65.         //创建一个队列对象，存储所有的边
  66.         MyArrayQueue<Edge> allEdges = new MyArrayQueue<>();
  68.         //遍历图中的每一个顶点，找到该顶点的邻接表，邻接表中存储了该顶点关联的每一条边
  70.         //因为这是无向图，所以同一条边同时出现在了它关联的两个顶点的邻接表中，需要让一条边只记录一次；
  71.         for (int v = 0; v < V; v++) {
  72.             //遍历v顶点的邻接表，找到每一条和v关联的边
  73.             MyArrayQueue<Edge> arrayQueue = adj(v);
  74.             for (int i = 0; i < arrayQueue.length(); i++) {
  75.                 Edge edge = arrayQueue.get(i);
  76.                 if (edge.other(v) < v) {
  77.                     allEdges.enQueue(edge);
  78.                 }
  79.             }
  80.         }
  81.         return allEdges;
  82.     }
  83. }

二 有向图

有向图是一副具有方向性的图，是由一组顶点和一组有方向的边组成的，每条方向的边都连着一对有序的顶点。

2.1 有向图定义

  1. 出度
    1. 由某个顶点指出的边的个数称为该顶点的出度。
  2. 入度
    1. 指向某个顶点的边的个数称为该顶点的入度。
  3. 有向路径
    1. 由一系列顶点组成，对于其中的每个顶点都存在一条有向边，从它指向序列中的下一个顶点。
  4. 有向环

一条至少含有一条边，且起点和终点相同的有向路径。

2.2 实现原理

类似于无向图，只有细微的差别。

2.3 有向图代码

  1. package com.ycc.data.structure.graph;
  4. import com.ycc.data.structure.line.MyArrayQueue;
  6. /**
  7.  * 有向图
  8.  *
  9.  * @author liaozx
  10.  * @date 2020/10/16
  11.  */
  12. public class Digraph {
  13.     //顶点数目
  14.     private final int V;
  15.     //边的数目
  16.     private int E;
  17.     //邻接表
  18.     private MyArrayQueue<Integer>[] adj;
  20.     public Digraph(int V) {
  21.         //初始化顶点数量
  22.         this.V = V;
  23.         //初始化边的数量
  24.         this.E = 0;
  25.         //初始化邻接表
  26.         this.adj = new MyArrayQueue[V];
  27.         for (int i = 0; i < adj.length; i++) {
  28.             adj[i] = new MyArrayQueue<Integer>();
  29.         }
  31.     }
  34.     //获取顶点数目
  35.     public int V() {
  36.         return V;
  37.     }
  39.     //获取边的数目
  40.     public int E() {
  41.         return E;
  42.     }
  44.     //向有向图中添加一条边 v->w
  45.     public void addEdge(int v, int w) {
  46.         //只需要让顶点w出现在顶点v的邻接表中，因为边是有方向的，最终，顶点v的邻接表中存储的相邻顶点的含义是：  v->其他顶点
  47.         adj[v].enQueue(w);
  48.         E++;
  49.     }
  51.     //获取由v指出的边所连接的所有顶点
  52.     public MyArrayQueue<Integer> adj(int v) {
  53.         return adj[v];
  54.     }
  56.     //该图的反向图
  57.     private Digraph reverse() {
  58.         //创建有向图对象
  59.         Digraph r = new Digraph(V);
  61.         for (int v = 0; v < V; v++) {
  62.             //获取由该顶点v指出的所有边
  63.             for (Integer w : adj[v]) {//原图中表示的是由顶点v->w的边
  64.                 r.addEdge(w, v);//w->v
  65.             }
  66.         }
  67.         return r;
  68.     }
  69. }

2.4 拓扑排序

2.4.1 定义

有向图将所有的顶点排序，使得所有的有向边均从排在前面的元素指向排在后面的元素，此时就可以明确的表示出每个顶点的优先级。
举例理解：
在现实生活中，我们经常会同一时间接到很多任务去完成，但是这些任务的完成是有先后次序的。以我们学习java学科为例，我们需要学习很多知识，但是这些知识在学习的过程中是需要按照先后次序来完成的。从java基础，到jsp/servlet，到ssm，到springboot等是个循序渐进且有依赖的过程。在学习jsp前要首先掌握java基础和html基础，学习ssm框架前要掌握jsp/servlet之类才行。
image.png
为了简化问题，我们使用整数为顶点编号的标准模型来表示这个案例：
image.png
此时如果某个同学要学习这些课程，就需要指定出一个学习的方案，我们只需要对图中的顶点进行排序，让它转换为一个线性序列，就可以解决问题，这时就需要用到一种叫拓扑排序的算法。
变成如下图所示：
image.png

2.4.2 环的问题

如果学习x课程前必须先学习y课程，学习y课程前必须先学习z课程，学习z课程前必须先学习x课程，那么一定是有问题了，我们就没有办法学习了，因为这三个条件没有办法同时满足。其实这三门课程x、y、z的条件组成了一个环。
image.png
因此，如果我们要使用拓扑排序解决优先级问题，首先得保证图中没有环的存在。

2.4.3 检测环原理

在API中添加了onStack[] 布尔数组，索引为图的顶点，当我们深度搜索时：
1. 在如果当前顶点正在搜索，则把对应的onStack数组中的值改为true，标识进栈；
2. 如果当前顶点搜索完毕，则把对应的onStack数组中的值改为false，标识出栈；
3. 如果即将要搜索某个顶点，但该顶点已经在栈中，则图中有环；

图解：
image.png
image.png
image.png

2.4.4 代码实现

  1. package com.ycc.data.structure.graph;
  4. import com.ycc.data.structure.line.MyArrayQueue;
  6. /**
  7.  * 检测有向环
  8.  *
  9.  * @author liaozx
  10.  * @date 2020/10/16
  11.  */
  13. public class DirectedCycle {
  14.     //索引代表顶点，值表示当前顶点是否已经被搜索
  15.     private boolean[] marked;
  16.     //记录图中是否有环
  17.     private boolean hasCycle;
  18.     //索引代表顶点，使用栈的思想，记录当前顶点有没有已经处于正在搜索的有向路径上
  19.     private boolean[] onStack;
  21.     //创建一个检测环对象，检测图G中是否有环
  22.     public DirectedCycle(Digraph G) {
  23.         //初始化marked数组
  24.         this.marked = new boolean[G.V()];
  25.         //初始化hasCycle
  26.         this.hasCycle = false;
  27.         //初始化onStack数组
  28.         this.onStack = new boolean[G.V()];
  30.         //找到图中每一个顶点，让每一个顶点作为入口，调用一次dfs进行搜索
  31.         for (int v = 0; v < G.V(); v++) {
  32.             //判断如果当前顶点还没有搜索过，则调用dfs进行搜索
  33.             if (!marked[v]) {
  34.                 dfs(G, v);
  35.             }
  37.         }
  39.     }
  41.     //基于深度优先搜索，检测图G中是否有环
  42.     private void dfs(Digraph G, int v) {
  43.         //把顶点v表示为已搜索
  44.         marked[v] = true;
  45.         //把当前顶点进栈
  46.         onStack[v] = true;
  48.         MyArrayQueue<Integer> queue = G.adj(v);
  50.         //进行深度搜索
  51.         for (int i = 0; i < queue.length(); i++) {
  52.             Integer w = queue.get(i);
  53.             //判断如果当前顶点w没有被搜索过，则继续递归调用dfs方法完成深度优先搜索
  54.             if (!marked[w]) {
  55.                 dfs(G, w);
  56.             }
  58.             //判断当前顶点w是否已经在栈中，如果已经在栈中，证明当前顶点之前处于正在搜索的状态，那么现在又要搜索一次，证明检测到环了
  59.             if (onStack[w]) {
  60.                 hasCycle = true;
  61.                 return;
  62.             }
  63.         }
  64.         //把当前顶点出栈
  65.         onStack[v] = false;
  66.     }
  68.     //判断当前有向图G中是否有环
  69.     public boolean hasCycle() {
  70.         return hasCycle;
  71.     }
  73. }

2.4.5 顶点排序

如果要把图中的顶点生成线性序列其实是一件非常简单的事，之前我们学习并使用了多次深度优先搜索，我们会发
现其实深度优先搜索有一个特点，那就是在一个连通子图上，每个顶点只会被搜索一次，如果我们能在深度优先搜
索的基础上，添加一行代码，只需要将搜索的顶点放入到线性序列的数据结构中，我们就能完成这件事。

2.4.6 顶点排序原理

顶点排序实现在API的设计中，我们添加了一个栈reversePost用来存储顶点，当我们深度搜索图时，每搜索完毕一个顶点，把该顶点放入到reversePost中，这样就可以实现顶点排序。
图解：
image.png
image.png
image.png
image.png
image.png

2.4.7 代码实现

  1. package com.ycc.data.structure.graph;
  3. import com.ycc.data.structure.line.MyArrayQueue;
  4. import com.ycc.data.structure.line.MyArrayStack;
  6. /**
  7.  * 顶点排序
  8.  *
  9.  * @author liaozx
  10.  * @date 2020/10/17
  11.  */
  13. public class DepthFirstOrder {
  14.     //索引代表顶点，值表示当前顶点是否已经被搜索
  15.     private boolean[] marked;
  16.     //使用栈，存储顶点序列
  17.     private MyArrayStack<Integer> reversePost;
  19.     //创建一个检测环对象，检测图G中是否有环
  20.     public DepthFirstOrder(Digraph G) {
  21.         //初始化marked数组
  22.         this.marked = new boolean[G.V()];
  23.         //初始化reversePost栈
  24.         this.reversePost = new MyArrayStack<Integer>();
  26.         //遍历图中的每一个顶点，让每个顶点作为入口，完成一次深度优先搜索
  27.         for (int v = 0; v < G.V(); v++) {
  28.             if (!marked[v]) {
  29.                 dfs(G, v);
  30.             }
  31.         }
  32.     }
  34.     //基于深度优先搜索，把顶点排序
  35.     private void dfs(Digraph G, int v) {
  36.         //标记当前v已经被搜索
  37.         marked[v] = true;
  38.         //通过循环深度搜索顶点v
  39.         MyArrayQueue<Integer> arrayQueue = G.adj(v);
  40.         for (int i = 0; i < arrayQueue.length(); i++) {
  41.             Integer w = arrayQueue.get(i);
  42.             //如果当前顶点w没有搜索，则递归调用dfs进行搜索
  43.             if (!marked[w]) {
  44.                 dfs(G, w);
  45.             }
  46.         }
  47.         //让顶点v进栈
  48.         reversePost.push(v);
  49.     }
  51.     //获取顶点线性序列
  52.     public MyArrayStack<Integer> reversePost() {
  53.         return reversePost;
  54.     }
  55. }

2.4.8 拓扑排序

基于一幅图，先检测有没有环，如果没有环，则调用顶点排序即可

  1. package com.ycc.data.structure.graph;
  4. import com.ycc.data.structure.line.MyArrayStack;
  6. /**
  7.  * @author liaozx
  8.  * @date 2020/10/17
  9.  */
  11. public class Topology {
  12.     //顶点的拓扑排序
  13.     private MyArrayStack<Integer> order;
  15.     //构造拓扑排序对象
  16.     public Topology(Digraph G) {
  17.         //创建一个检测有向环的对象
  18.         DirectedCycle cycle = new DirectedCycle(G);
  19.         //判断G图中有没有环，如果没有环，则进行顶点排序：创建一个顶点排序对象
  20.         if (!cycle.hasCycle()) {
  21.             DepthFirstOrder depthFirstOrder = new DepthFirstOrder(G);
  22.             order = depthFirstOrder.reversePost();
  23.         }
  24.     }
  26.     //判断图G是否有环
  27.     private boolean isCycle() {
  28.         return order == null;
  29.     }
  31.     //获取拓扑排序的所有顶点
  32.     public MyArrayStack<Integer> order() {
  33.         return order;
  34.     }
  35. }

2.5 加权有向图

2.5.1 加权有向边

  1. package com.ycc.data.structure.graph;
  3. /**
  4.  * 有向边
  5.  *
  6.  * @author liaozx
  7.  * @date 2020/10/19
  8.  */
  9. public class DirectedEdge {
  10.     private final int v;//起点
  11.     private final int w;//终点
  12.     private final double weight;//当前边的权重
  14.     //通过顶点v和w，以及权重weight值构造一个边对象
  15.     public DirectedEdge(int v, int w, double weight) {
  16.         this.v = v;
  17.         this.w = w;
  18.         this.weight = weight;
  19.     }
  21.     //获取边的权重值
  22.     public double weight() {
  23.         return weight;
  24.     }
  26.     //获取有向边的起点
  27.     public int from() {
  28.         return v;
  29.     }
  31.     //获取有向边的终点
  32.     public int to() {
  33.         return w;
  34.     }
  35. }

2.5.2 加权有向图

  1. package com.ycc.data.structure.graph;
  4. import com.ycc.data.structure.line.MyArrayQueue;
  6. /**
  7.  * 加权有向图
  8.  *
  9.  * @author liaozx
  10.  * @date 2020/10/19
  11.  */
  12. public class EdgeWeightedDigraph {
  13.     //顶点总数
  14.     private final int V;
  15.     //边的总数
  16.     private int E;
  17.     //邻接表
  18.     private MyArrayQueue<DirectedEdge>[] adj;
  20.     //创建一个含有V个顶点的空加权有向图
  21.     public EdgeWeightedDigraph(int V) {
  22.         //初始化顶点数量
  23.         this.V = V;
  24.         //初始化边的数量
  25.         this.E = 0;
  26.         //初始化邻接表
  27.         this.adj = new MyArrayQueue[V];
  28.         for (int i = 0; i < adj.length; i++) {
  29.             adj[i] = new MyArrayQueue<DirectedEdge>();
  30.         }
  31.     }
  33.     //获取图中顶点的数量
  34.     public int V() {
  35.         return V;
  36.     }
  38.     //获取图中边的数量
  39.     public int E() {
  40.         return E;
  41.     }
  44.     //向加权有向图中添加一条边e
  45.     public void addEdge(DirectedEdge e) {
  46.         //边e是有方向的，所以只需要让e出现在起点的邻接表中即可
  47.         int v = e.from();
  48.         adj[v].enQueue(e);
  49.         E++;
  50.     }
  52.     //获取由顶点v指出的所有的边
  53.     public MyArrayQueue<DirectedEdge> adj(int v) {
  54.         return adj[v];
  55.     }
  57.     //获取加权有向图的所有边
  58.     public MyArrayQueue<DirectedEdge> edges() {
  59.         //遍历图中的每一个顶点，得到该顶点的邻接表，遍历得到每一条边，添加到队列中返回即可
  60.         MyArrayQueue<DirectedEdge> allEdges = new MyArrayQueue<>();
  61.         for (int v = 0; v < V; v++) {
  62.             for (DirectedEdge edge : adj[v]) {
  63.                 allEdges.enQueue(edge);
  64.             }
  65.         }
  66.         return allEdges;
  67.     }
  68. }

三 最小生成树

图的生成树是它的一棵含有其所有顶点的无环连通子图，一副加权无向图的最小生成树它的一棵权值(树中所有边的权重之和)最小的生成树。
所以具备以下性质：

  1. 用一条边接树中的任意两个顶点都会产生一个新的环
  2. 从树中删除任意一条边，将会得到两棵独立的树

    3.1 贪心算法思想

    贪心算法是计算图的最小生成树的基础算法，它的基本原理就是切分定理，使用切分定理找到最小生成树的一条边，不断的重复直到找到最小生成树的所有边。如果图有V个顶点，那么需要找到V-1条边，就可以表示该图的最小生成树。

在一副加权图中，给定任意的切分，它的横切边中的权重最小者必然属于图中的最小生成树

3.2 Prim算法

它的每一步都会为一棵生成中的树添加一条边。一开始这棵树只有一个顶点，然后会向它添加V-1条边，每次总是将下一条连接树中的顶点与不在树中的顶点且权重最小的边加入到树中。

3.2.1 实现原理

Prim算法将图中的顶点切分成两个集合，最小生成树顶点和非最小生成树顶点，通过不断的重复做某些操作，可以逐渐将非最小生成树中的顶点加入到最小生成树中，直到所有的顶点都加入到最小生成树中。
image.png

  1. 使用最小索引优先队列存放树中顶点与非树中顶点的有效横切边
    1. 我们可以让最小索引优先队列的索引值表示图的顶点，让最小索引优先队列中的值表示从其他某个顶点到当前顶点的边权重
  2. 初始化状态，先默认0是最小生成树中的唯一顶点，其他的顶点都不在最小生成树中，此时横切边就是顶点0的邻接表中0-2,0-4,0-6,0-7这四条边，我们只需要将索引优先队列的2、4、6、7索引处分别存储这些边的权重值就可以表示了
  3. 只需要从这四条横切边中找出权重最小的边，然后把对应的顶点加进来即可。所以找到0-7这条横切边的权重最小，因此把0-7这条边添加进来，此时0和7属于最小生成树的顶点，其他的不属于.
    1. 0-7这条边已经不是横切边了，需要让它失效：只需要调用最小索引优先队列的delMin()方法即可完成；
    2. 2和4顶点各有两条连接指向最小生成树，需要只保留一条：4-7的权重小于0-4的权重，所以保留4-7，调用索引优先队列的change(4,0.37)即可，0-2的权重小于2-7的权重，所以保留0-2，不需要做额外操作。
  4. 我们不断重复上面的动作，就可以把所有的顶点添加到最小生成树中。

    3.2.2 代码实现

    ```java package com.ycc.data.structure.graph;

import com.ycc.data.structure.heap.IndexMinPriorityQueue; import com.ycc.data.structure.line.MyArrayQueue;

/**

  • Prim 最小生成树 *
  • @author liaozx

  • @date 2020/10/19 */ public class PrimMST { //索引代表顶点，值表示当前顶点和最小生成树之间的最短边 private Edge[] edgeTo; //索引代表顶点，值表示当前顶点和最小生成树之间的最短边的权重 private double[] distTo; //索引代表顶点，如果当前顶点已经在树中，则值为true，否则为false private boolean[] marked; //存放树中顶点与非树中顶点之间的有效横切边 private IndexMinPriorityQueue pq;

    //根据一副加权无向图，创建最小生成树计算对象 public PrimMST(EdgeWeightedGraph G) {

    1.  //初始化edgeTo
    2.  this.edgeTo = new Edge[G.V()];
    3.  //初始化distTo
    4.  this.distTo = new double[G.V()];
    5.  for (int i = 0; i < distTo.length; i++) {
    6.      distTo[i] = Double.POSITIVE_INFINITY;
    7.  }
    8.  //初始化marked
    9.  this.marked = new boolean[G.V()];
    10.  //初始化pq
    11.  pq = new IndexMinPriorityQueue<Double>(G.V());
    13.  //默认让顶点0进入到树中，但是树中只有一个顶点0，因此，0顶点默认没有和其他的顶点相连，所以让distTo对应位置处的值存储0.0
    14.  distTo[0] = 0.0;
    15.  pq.insert(0, 0.0);
    17.  //遍历索引最小优先队列，拿到最小和N切边对应的顶点，把该顶点加入到最小生成树中
    18.  while (!pq.isEmpty()) {
    19.      visit(G, pq.delMin());
    20.  }

    }

  1. //将顶点v添加到最小生成树中，并且更新数据
  2. private void visit(EdgeWeightedGraph G, int v) {
  3.     //把顶点v添加到最小生成树中
  4.     marked[v] = true;
  5.     //更新数据
  6.     MyArrayQueue<Edge> arrayQueue = G.adj(v);
  7.     for (int i = 0; i < arrayQueue.length(); i++) {
  8.         Edge e = arrayQueue.get(i);
  9.         //获取e边的另外一个顶点(当前顶点是v)
  10.         int w = e.other(v);
  11.         //判断另外一个顶点是不是已经在树中，如果在树中，则不做任何处理，如果不再树中，更新数据
  12.         if (marked[w]) {
  13.             continue;
  14.         }
  15.         //判断边e的权重是否小于从w顶点到树中已经存在的最小边的权重；
  16.         if (e.weight() < distTo[w]) {
  17.             //更新数据
  18.             edgeTo[w] = e;
  19.             distTo[w] = e.weight();
  20.             if (pq.contains(w)) {
  21.                 pq.changeItem(w, e.weight());
  22.             } else {
  23.                 pq.insert(w, e.weight());
  24.             }
  25.         }
  26.     }
  27. }
  29. //获取最小生成树的所有边
  30. public MyArrayQueue<Edge> edges() {
  31.     //创建队列对象
  32.     MyArrayQueue<Edge> allEdges = new MyArrayQueue<>();
  33.     //遍历edgeTo数组，拿到每一条边，如果不为null，则添加到队列中
  34.     for (int i = 0; i < edgeTo.length; i++) {
  35.         if (edgeTo[i] != null) {
  36.             allEdges.enQueue(edgeTo[i]);
  37.         }
  38.     }
  39.     return allEdges;
  40. }

}

  1. <a name="Nsn8I"></a>
  2. ### 3.2.3 代码测试
  3. ```java
  4. package com.ycc.data.structure.graph.test;
  7. import com.ycc.data.structure.graph.Edge;
  8. import com.ycc.data.structure.graph.EdgeWeightedGraph;
  9. import com.ycc.data.structure.graph.PrimMST;
  10. import com.ycc.data.structure.line.MyArrayQueue;
  12. public class PrimMSTTest {
  14.     public static void main(String[] args) throws Exception {
  16.         //8
  17.         //16
  18.         //4 5 0.35
  19.         //4 7 0.37
  20.         //5 7 0.28
  21.         //0 7 0.16
  22.         //1 5 0.32
  23.         //0 4 0.38
  24.         //2 3 0.17
  25.         //1 7 0.19
  26.         //0 2 0.26
  27.         //1 2 0.36
  28.         //1 3 0.29
  29.         //2 7 0.34
  30.         //6 2 0.40
  31.         //3 6 0.52
  32.         //6 0 0.58
  33.         //6 4 0.93
  34.         EdgeWeightedGraph graph = new EdgeWeightedGraph(8);
  35.         graph.addEdge(new Edge(4, 5, 0.35));
  36.         graph.addEdge(new Edge(4, 7, 0.37));
  37.         graph.addEdge(new Edge(5, 7, 0.28));
  38.         graph.addEdge(new Edge(0, 7, 0.16));
  39.         graph.addEdge(new Edge(1, 5, 0.32));
  40.         graph.addEdge(new Edge(0, 4, 0.38));
  41.         graph.addEdge(new Edge(2, 3, 0.17));
  42.         graph.addEdge(new Edge(1, 7, 0.19));
  43.         graph.addEdge(new Edge(0, 2, 0.26));
  44.         graph.addEdge(new Edge(1, 2, 0.36));
  45.         graph.addEdge(new Edge(1, 3, 0.29));
  46.         graph.addEdge(new Edge(2, 7, 0.34));
  47.         graph.addEdge(new Edge(6, 2, 0.40));
  48.         graph.addEdge(new Edge(3, 6, 0.52));
  49.         graph.addEdge(new Edge(6, 0, 0.58));
  50.         graph.addEdge(new Edge(6, 4, 0.93));
  52.         //创建一个PrimMST对象，计算加权无向图中的最小生成树
  53.         PrimMST primMST = new PrimMST(graph);
  54.         //获取最小生成树中的所有边
  55.         MyArrayQueue<Edge> edges = primMST.edges();
  56.         //遍历打印所有的边
  57.         for (int i = 0; i < edges.length(); i++) {
  58.             Edge edge = edges.get(i);
  59.             int v = edge.either();
  60.             int w = edge.other(v);
  61.             System.out.println(v + "-" + w + " :: " + edge.weight());
  62.         }
  63.     }
  64. }

输出结果

  1. 1-7 :: 0.19
  2. 0-2 :: 0.26
  3. 2-3 :: 0.17
  4. 4-5 :: 0.35
  5. 5-7 :: 0.28
  6. 6-2 :: 0.4
  7. 0-7 :: 0.16

3.3 kruskal算法

它的主要思想是按照边的权重(从小到大)处理它们，将边加入最小生成树中，加入的边不会与已经加入最小生成树的边构成环，直到树中含有V-1条边为止。

3.3.1 实现原理

  1. Prim算法是一条边一条边的构造最小生成树，每一步都为一棵树添加一条边。
  2. kruskal算法构造最小生成树的时候也是一条边一条边地构造，但它的切分规则是不一样的。它每一次寻找的边会连接一片森林中的两棵树。如果一副加权无向图由V个顶点组成，初始化情况下每个顶点都构成一棵独立的树，则V个顶点对应V棵树，组成一片森林，
  3. kruskal算法每一次处理都会将两棵树合并为一棵树，直到整个森林中只剩一棵树为止。

image.png
具体实现步骤

  1. 使用了一个MinPriorityQueue pq存储图中所有的边，每次使用pq.delMin()取出权重最小的边，并得到该边关联的两个顶点v和w，
  2. 通过uf.connect(v,w)判断v和w是否已经连通，如果连通，则证明这两个顶点在同一棵树中，那么就不能再把这条边添加到最小生成树中，因为在一棵树的任意两个顶点上添加一条边，都会形成环，而最小生成树不能有环的存在，
  3. 如果不连通，则通过uf.connect(v,w)把顶点v所在的树和顶点w所在的树合并成一棵树，并把这条边加入到mst队列中，这样如果把所有的边处理完，最终mst中存储的就是最小生树的所有边

image.png
image.png
image.png
image.png
image.png

3.3.2 代码实现

  1. package com.ycc.data.structure.graph;
  4. import com.ycc.data.structure.heap.MinPriorityQueue;
  5. import com.ycc.data.structure.line.MyArrayQueue;
  6. import com.ycc.data.structure.uf.UFTreeWeighted;
  8. /**
  9.  * 最小生成树
  10.  *
  11.  * @author liaozx
  12.  * @date 2020/10/19
  13.  */
  15. public class KruskalMST {
  16.     //保存最小生成树的所有边
  17.     private MyArrayQueue<Edge> mst;
  18.     //索引代表顶点，使用uf.connect(v,w)可以判断顶点v和顶点w是否在同一颗树中，使用uf.union(v,w)可以把顶点v所在的树和顶点w所在的树合并
  19.     private UFTreeWeighted uf;
  20.     //存储图中所有的边，使用最小优先队列，对边按照权重进行排序
  21.     private MinPriorityQueue<Edge> pq;
  23.     //根据一副加权无向图，创建最小生成树计算对象
  24.     public KruskalMST(EdgeWeightedGraph G) {
  26.         //初始化mst
  27.         this.mst = new MyArrayQueue<Edge>();
  28.         //初始化uf
  29.         this.uf = new UFTreeWeighted(G.V());
  30.         //初始化pq
  31.         this.pq = new MinPriorityQueue<>(G.E() + 1);
  32.         MyArrayQueue<Edge> arrayQueue = G.edges();
  33.         //把图中所有的边存储到pq中
  34.         for (int i = 0; i < arrayQueue.length(); i++) {
  35.             Edge edge = arrayQueue.get(i);
  36.             pq.enqueue(edge);
  37.         }
  39.         //遍历pq队列，拿到最小权重的边，进行处理
  40.         while (!pq.isEmpty() && mst.length() < G.V() - 1) {
  41.             //找到权重最小的边
  42.             Edge e = pq.dequeue();
  43.             //找到该边的两个顶点
  44.             int v = e.either();
  45.             int w = e.other(v);
  47.             //判断这两个顶点是否已经在同一颗树中，如果在同一颗树中，则不对该边做处理，如果不在一棵树中，则让这两个顶点属于的两棵树合并成一棵树
  48.             if (uf.connected(v, w)) {
  49.                 continue;
  50.             }
  51.             uf.union(v, w);
  52.             //让边e进入到mst队列中
  53.             mst.enQueue(e);
  54.         }
  56.     }
  58.     //获取最小生成树的所有边
  59.     public MyArrayQueue<Edge> edges() {
  60.         return mst;
  61.     }
  62. }

3.3.3 测试代码

  1. package com.ycc.data.structure.graph.test;
  4. import com.ycc.data.structure.graph.Edge;
  5. import com.ycc.data.structure.graph.EdgeWeightedGraph;
  6. import com.ycc.data.structure.graph.KruskalMST;
  7. import com.ycc.data.structure.line.MyArrayQueue;
  9. public class KruskalMSTTest {
  11.     public static void main(String[] args) throws Exception {
  14.         EdgeWeightedGraph graph = new EdgeWeightedGraph(8);
  15.         graph.addEdge(new Edge(4, 5, 0.35));
  16.         graph.addEdge(new Edge(4, 7, 0.37));
  17.         graph.addEdge(new Edge(5, 7, 0.28));
  18.         graph.addEdge(new Edge(0, 7, 0.16));
  19.         graph.addEdge(new Edge(1, 5, 0.32));
  20.         graph.addEdge(new Edge(0, 4, 0.38));
  21.         graph.addEdge(new Edge(2, 3, 0.17));
  22.         graph.addEdge(new Edge(1, 7, 0.19));
  23.         graph.addEdge(new Edge(0, 2, 0.26));
  24.         graph.addEdge(new Edge(1, 2, 0.36));
  25.         graph.addEdge(new Edge(1, 3, 0.29));
  26.         graph.addEdge(new Edge(2, 7, 0.34));
  27.         graph.addEdge(new Edge(6, 2, 0.40));
  28.         graph.addEdge(new Edge(3, 6, 0.52));
  29.         graph.addEdge(new Edge(6, 0, 0.58));
  30.         graph.addEdge(new Edge(6, 4, 0.93));
  31.         //创建一个KruskalMST对象，计算加权无向图中的最小生成树
  32.         KruskalMST primMST = new KruskalMST(graph);
  34.         //获取最小生成树中的所有边
  35.         MyArrayQueue<Edge> edges = primMST.edges();
  36.         //遍历打印所有的边
  37.         for (int i = 0; i < edges.length(); i++) {
  38.             Edge edge = edges.get(i);
  39.             int v = edge.either();
  40.             int w = edge.other(v);
  41.             System.out.println(v + "-" + w + " :: " + edge.weight());
  42.         }
  43.     }
  44. }

四 最短路径

例如在一副地图中，找到顶点a与地点b之间的路径，这条路径可以是距离最短，也可以是时间最短，也可以是费用最小等，如果我们把 距离/时间/费用看做是成本，那么就需要找到地点a和地点b之间成本最小的路径，也就是我们接下来要解决的最短路径问题.

4.1 最短路径概念

在一副加权有向图中，从顶点s到顶点t的最短路径是所有从顶点s到顶点t的路径中总权重最小的那条路径。
image.png
性质：

  1. 路径具有方向性；
  2. 权重不一定等价于距离。权重可以是距离、时间、花费等内容，权重最小指的是成本最低
  3. 只考虑连通图。一副图中并不是所有的顶点都是可达的，如果s和t不可达，那么它们之间也就不存在最短路径，为了简化问题，这里只考虑连通图。
  4. 最短路径不一定是唯一的。从一个顶点到达另外一个顶点的权重最小的路径可能会有很多条，这里只需要找出一

条即可。
最短路径树：
给定一副加权有向图和一个顶点s，以s为起点的一棵最短路径树是图的一副子图，它包含顶点s以及从s可达的所有顶点。这棵有向树的根结点为s，树的每条路径都是有向图中的一条最短路径。

4.2 Dijstra算法

4.2.1 实现原理

4.2.2 代码实现

  1. package com.ycc.data.structure.graph;
  3. import com.ycc.data.structure.heap.IndexMinPriorityQueue;
  4. import com.ycc.data.structure.line.MyArrayQueue;
  6. /**
  7.  * 最短路径
  8.  *
  9.  * @author liaozx
  10.  * @date 2020/10/19
  11.  */
  12. public class DijkstraSP {
  13.     //索引代表顶点，值表示从顶点s到当前顶点的最短路径上的最后一条边
  14.     private DirectedEdge[] edgeTo;
  15.     //索引代表顶点，值从顶点s到当前顶点的最短路径的总权重
  16.     private double[] distTo;
  17.     //存放树中顶点与非树中顶点之间的有效横切边
  18.     private IndexMinPriorityQueue<Double> pq;
  20.     //根据一副加权有向图G和顶点s，创建一个计算顶点为s的最短路径树对象
  21.     public DijkstraSP(EdgeWeightedDigraph G, int s) {
  22.         //初始化edgeTo
  23.         this.edgeTo = new DirectedEdge[G.V()];
  24.         //初始化distTo
  25.         this.distTo = new double[G.V()];
  26.         for (int i = 0; i < distTo.length; i++) {
  27.             distTo[i] = Double.POSITIVE_INFINITY;
  28.         }
  29.         //初始化pq
  30.         this.pq = new IndexMinPriorityQueue<>(G.V());
  31.         //找到图G中以顶点s为起点的最短路径树
  32.         //默认让顶点s进入到最短路径树中
  33.         distTo[s] = 0.0;
  34.         pq.insert(s, 0.0);
  35.         //遍历pq
  36.         while (!pq.isEmpty()) {
  37.             relax(G, pq.delMin());
  38.         }
  39.     }
  41.     //松弛图G中的顶点v
  42.     private void relax(EdgeWeightedDigraph G, int v) {
  43.         MyArrayQueue<DirectedEdge> arrayQueue = G.adj(v);
  44.         for (int i = 0; i < arrayQueue.length(); i++) {
  45.             DirectedEdge edge = arrayQueue.get(i);
  46.             //获取到该边的终点w
  47.             int w = edge.to();
  48.             //通过松弛技术，判断从起点s到顶点w的最短路径是否需要先从顶点s到顶点v，然后再由顶点v到顶点w
  49.             if (distTo(v) + edge.weight() < distTo(w)) {
  50.                 distTo[w] = distTo[v] + edge.weight();
  51.                 edgeTo[w] = edge;
  52.                 //判断pq中是否已经存在顶点w，如果存在，则更新权重，如果不存在，则直接添加
  53.                 if (pq.contains(w)) {
  54.                     pq.changeItem(w, distTo(w));
  55.                 } else {
  56.                     pq.insert(w, distTo(w));
  57.                 }
  59.             }
  60.         }
  61.     }
  63.     //获取从顶点s到顶点v的最短路径的总权重
  64.     public double distTo(int v) {
  65.         return distTo[v];
  66.     }
  68.     //判断从顶点s到顶点v是否可达
  69.     public boolean hasPathTo(int v) {
  70.         return distTo[v] < Double.POSITIVE_INFINITY;
  71.     }
  73.     //查询从起点s到顶点v的最短路径中所有的边
  74.     public MyArrayQueue<DirectedEdge> pathTo(int v) {
  75.         //判断从顶点s到顶点v是否可达，如果不可达，直接返回null
  76.         if (!hasPathTo(v)) {
  77.             return null;
  78.         }
  79.         //创建队列对象
  80.         MyArrayQueue<DirectedEdge> allEdges = new MyArrayQueue<>();
  81.         while (true) {
  82.             DirectedEdge e = edgeTo[v];
  83.             if (e == null) {
  84.                 break;
  85.             }
  86.             allEdges.enQueue(e);
  87.             v = e.from();
  88.         }
  90.         return allEdges;
  91.     }
  93. }

4.2.3 测试代码

  1. package com.ycc.data.structure.graph.test;
  4. import com.ycc.data.structure.graph.DijkstraSP;
  5. import com.ycc.data.structure.graph.DirectedEdge;
  6. import com.ycc.data.structure.graph.EdgeWeightedDigraph;
  7. import com.ycc.data.structure.line.MyArrayQueue;
  9. public class DijkstraSPTest {
  11.     public static void main(String[] args) throws Exception {
  12.         //8
  13.         //15
  14.         //4 5 0.35
  15.         //5 4 0.35
  16.         //4 7 0.37
  17.         //5 7 0.28
  18.         //7 5 0.28
  19.         //5 1 0.32
  20.         //0 4 0.38
  21.         //0 2 0.26
  22.         //7 3 0.39
  23.         //1 3 0.29
  24.         //2 7 0.34
  25.         //6 2 0.40
  26.         //3 6 0.52
  27.         //6 0 0.58
  28.         //6 4 0.93
  29.         EdgeWeightedDigraph digraph = new EdgeWeightedDigraph(8);
  30.         digraph.addEdge(new DirectedEdge(4, 5, 0.35));
  31.         digraph.addEdge(new DirectedEdge(5, 4, 0.35));
  32.         digraph.addEdge(new DirectedEdge(4, 7, 0.37));
  33.         digraph.addEdge(new DirectedEdge(5, 7, 0.28));
  34.         digraph.addEdge(new DirectedEdge(7, 5, 0.28));
  35.         digraph.addEdge(new DirectedEdge(5, 1, 0.32));
  36.         digraph.addEdge(new DirectedEdge(0, 4, 0.38));
  37.         digraph.addEdge(new DirectedEdge(0, 2, 0.26));
  38.         digraph.addEdge(new DirectedEdge(7, 3, 0.39));
  39.         digraph.addEdge(new DirectedEdge(1, 3, 0.29));
  40.         digraph.addEdge(new DirectedEdge(2, 7, 0.34));
  41.         digraph.addEdge(new DirectedEdge(6, 2, 0.40));
  42.         digraph.addEdge(new DirectedEdge(3, 6, 0.52));
  43.         digraph.addEdge(new DirectedEdge(6, 0, 0.58));
  44.         digraph.addEdge(new DirectedEdge(6, 4, 0.93));
  45.         //创建DijkstraSP对象，查找最短路径树
  46.         DijkstraSP dijkstraSP = new DijkstraSP(digraph, 0);
  47.         //查找最短路径,0->6的最短路径
  48.         MyArrayQueue<DirectedEdge> edges = dijkstraSP.pathTo(6);
  50.         //遍历打印所有的边
  51.         for (int i = 0; i < edges.length(); i++) {
  52.             DirectedEdge edge = edges.get(i);
  53.             System.out.println(edge.from() + "->" + edge.to() + " ：： " + edge.weight());
  54.         }
  56.     }
  57. }