尚硅谷图解Java数据结构和算法.pdf

1、基本介绍

定义

  • 当我们需要表示多对多的关系时，我们就需要图
  • 图是一种数据结构，其中结点可以具有零个或多个相邻元素。两个结点之间的连接称为边。结点也可以称为顶点

九、图结构 - 图1

表示方法

邻接矩阵

  • 邻接矩阵是表示图形中顶点之间相邻关系的矩阵，对于n个顶点的图而言，矩阵是的row和 col表示的是1…n个点

如上图的邻接矩阵就是
0 1 0 0 1
1 0 1 1 0
0 1 0 0 0
0 1 0 0 1
1 0 0 1 0
其中0表示没有连接，1表示有连接

邻接表

  • 邻接矩阵需要为每个顶点都分配 n个边的空间，其实有很多边都是不存在,会造成空间的一定损失
  • 邻接表的实现只关心存在的边，不关心不存在的边。因此没有空间浪费，邻接表由数组+链表组成
    • 数组的索引代表顶点
    • 链表中元素的值代表与该顶点相连的顶点的值

如上图的进阶表就是
九、图结构 - 图2

2、图的创建

邻接矩阵创建图

image.png

  1. package graph;
  2. import java.util.ArrayList;
  3. import java.util.Arrays;
  4. /**
  5.  * @author Voyager1
  6.  * @create 2021-10-15 11:18
  7.  */
  8. public class Graph {
  9.     private ArrayList<String> vertexList;//存放节点的集合
  10.     private int[][] edges;//存储对应的邻接矩阵
  11.     private int numofEdges;// 表示边的数目
  13.     public static void main(String[] args) {
  14.         int n = 5;
  15.         String Vertexs[] = {"A", "B", "C", "D", "E"};
  17.         //创建图对象
  18.         Graph graph = new Graph(n);
  19.         //循环的添加顶点
  20.         for(String vertex: Vertexs) {
  21.             graph.insertVertex(vertex);
  22.         }
  24.         //添加边
  25.         //A-B A-C B-C B-D B-E 无向图
  26.         graph.insertEdge(0, 1, 1); // A-B
  27.         graph.insertEdge(0, 2, 1); // A-C
  28.         graph.insertEdge(1, 2, 1); // B-C
  29.         graph.insertEdge(1, 3, 1); // B-D
  30.         graph.insertEdge(1, 4, 1); // B-E
  32.         graph.showGraph();
  33.     }
  35.     //初始化图
  36.     public Graph(int n){
  37.         vertexList = new ArrayList<>(n);
  38.         edges = new int[n][n];
  39.         numofEdges = 0;
  40.     }
  42.     //图中常用方法
  43.     //1 返回结点的个数
  44.     public int getNumofVertex(){
  45.         return vertexList.size();
  46.     }
  47.     //2 返回边的个数
  48.     public int getNumofEdges(){
  49.         return numofEdges;
  50.     }
  51.     //3 返回节点i(下标) 对应的数据 0->"A" 1->"B"
  52.     public String getValueByIndex(int i){
  53.         return vertexList.get(i);
  54.     }
  55.     //返回v1和v2的权值
  56.     public int getWeight(int v1,int v2){
  57.         return edges[v1][v2];
  58.     }
  59.     //插入结点
  60.     public void insertVertex(String vertex){
  61.         vertexList.add(vertex);
  62.     }
  63.     /**
  64.      * 添加边
  65.      * @param v1 表示点的下标即使第几个顶点  "A"-"B" "A"->0 "B"->1
  66.      * @param v2 第二个顶点对应的下标
  67.      * @param weight 边的权值
  68.      */
  69.     public void insertEdge(int v1,int v2,int weight){
  70.         edges[v1][v2] = weight;
  71.         edges[v2][v1] = weight;
  72.         numofEdges++;
  73.     }
  74.     //显示图对应的矩阵
  75.     public void showGraph(){
  76.         for (int[] link:edges){
  77.             System.out.println(Arrays.toString(link));
  78.         }
  79.     }
  80. }

3、图的遍历

对该图进行深度优先遍历和广度优先遍历
九、图结构 - 图4

深度优先遍历（DFS）

  • 深度优先遍历，从初始访问结点出发，初始访问结点可能有多个邻接结点，深度优先遍历的策略就是首先访问第一个邻接结点，然后再以这个被访问的邻接结点作为初始结点，访问它的第一个邻接结点，可以这样理解：每次都在访问完当前结点后首先访问当前结点的第一个邻接结点。
  • 这样的访问策略是优先往纵向挖掘深入

  • 深度优先搜索是一个递归的过程

    思路

  • 访问初始结点v，并标记结点v为已访问

  • 查找结点v的第一个邻接结点w
  • 若w存在，则继续执行4，如果w不存在，则回到第1步，将从v的下一个结点继续
  • 若w未被访问，对w进行深度优先遍历递归（即把w当做另一个v，然后进行步骤123）

  • 查找结点v的w邻接结点的下一个邻接结点，转到步骤 3

    实现代码

    ```java public class Graph { private ArrayList vertexList;//存放节点的集合 private int[][] edges;//存储对应的邻接矩阵 private int numofEdges;// 表示边的数目 //定义给数组boolean[], 记录某个结点是否被访问 private boolean[] isVisited;

    public static void main(String[] args) {

    1.   int n = 5;
    2.   String Vertexs[] = {"A", "B", "C", "D", "E"};
    4.   //创建图对象
    5.   Graph graph = new Graph(n);
    6.   //循环的添加顶点
    7.   for(String vertex: Vertexs) {
    8.       graph.insertVertex(vertex);
    9.   }
    11.   //添加边
    12.   //A-B A-C B-C B-D B-E 无向图
    13.   graph.insertEdge(0, 1, 1); // A-B
    14.   graph.insertEdge(0, 2, 1); // A-C
    15.   graph.insertEdge(1, 2, 1); // B-C
    16.   graph.insertEdge(1, 3, 1); // B-D
    17.   graph.insertEdge(1, 4, 1); // B-E
    19.   graph.showGraph();
    20.   //测试一把，我们的dfs遍历是否ok
    21.   System.out.println("深度遍历");
    22.   graph.dfs();

    }

    //初始化图 public Graph(int n){

    1.   vertexList = new ArrayList<>(n);
    2.   edges = new int[n][n];
    3.   numofEdges = 0;
    4.   isVisited = new boolean[n];

    }

    //图中常用方法 //1 返回结点的个数 public int getNumofVertex(){

    1.   return vertexList.size();

    } //2 返回边的个数 public int getNumofEdges(){

    1.   return numofEdges;

    } //3 返回节点i(下标) 对应的数据 0->”A” 1->”B” public String getValueByIndex(int i){

    1.   return vertexList.get(i);

    } //返回v1和v2的权值 public int getWeight(int v1,int v2){

    1.   return edges[v1][v2];

    } //插入结点 public void insertVertex(String vertex){

    1.   vertexList.add(vertex);

    } /**

    • 添加边
    • @param v1 表示点的下标即使第几个顶点 “A”-“B” “A”->0 “B”->1
    • @param v2 第二个顶点对应的下标

    • @param weight 边的权值 */ public void insertEdge(int v1,int v2,int weight){ edges[v1][v2] = weight; edges[v2][v1] = weight; numofEdges++; } //显示图对应的矩阵 public void showGraph(){ for (int[] link:edges){

      1.  System.out.println(Arrays.toString(link));

      } }

      /* 得到第一个邻接结点的下标 w

    • @param index
    • @return 如果存在就返回对应的下标，否则返回-1 */ public int getFirstNeighbor(int index){ for (int j = 0; j < vertexList.size(); j++){ if(edges[index][j] > 0){
      1.    return j;
      } } return -1; } //根据前一个邻接结点的下标来获取下一个邻接结点 public int getNextNeighbor(int v1,int v2){ for (int j = v2 + 1;j < vertexList.size(); j++){
      1.  if (edges[v1][j] > 0){
      2.      return j;
      3.  }
      } return -1; } /**
    • 深度优先遍历算法
    • @param isVisited 检查节点是否被访问过
    • @param i 第一次就是 0 */ private void dfs(boolean[] isVisited,int i){ //首先我们访问该结点,输出 System.out.print(getValueByIndex(i) + “->”); //将结点设置为已经访问 isVisited[i] = true; //查找结点i的第一个邻接结点w int w = getFirstNeighbor(i); while(w != -1){//说明有
      1.  if (!isVisited[w]){
      2.      dfs(isVisited,w);
      3.  }
      4.  //如果w结点已经被访问过
      5.  w = getNextNeighbor(i,w);
      } } //对dfs 进行一个重载, 遍历我们所有的结点，并进行 dfs public void dfs(){ for (int i = 0; i < getNumofVertex(); i++){
      1.  if (!isVisited[i]) {
      2.      dfs(isVisited, i);
      3.  }
      } } } 运行结果

邻接矩阵 [0, 1, 1, 0, 0] [1, 0, 1, 1, 1] [1, 1, 0, 0, 0] [0, 1, 0, 0, 0] [0, 1, 0, 0, 0] 进行深度优先遍历 A->B->C->E->D->

  1. <a name="GORbi"></a>
  2. ### 广度优先遍历（BFS）
  4. - 类似于一个**分层搜索**的过程，广度优先遍历需要使用一个**队列**以保持访问过的结点的顺序，以便按这个顺序来访问这些结点的邻接结点
  5. <a name="eD2A6"></a>
  6. #### 思路
  8. - 访问初始结点 v并标记结点 v为已访问
  9. - 结点v入队列
  10. - 当队列非空时，继续执行，否则算法结束
  11. - 出队列，取得队头结点u
  12. - 查找结点 u的第一个邻接结点 w。
  13. - 若结点 u的邻接结点 w不存在，则转到步骤 3；否则循环执行以下三个步骤：
  14.    - 若结点 w尚未被访问，则访问结点 w并标记为已访问
  15.    - 结点 w入队列
  16.    - 查找结点 u的继 w邻接结点后的下一个邻接结点 w，转到步骤6
  17. <a name="sEH3Q"></a>
  18. #### 实现代码
  19. ```java
  20. public class Graph {
  21.     private ArrayList<String> vertexList;//存放节点的集合
  22.     private int[][] edges;//存储对应的邻接矩阵
  23.     private int numofEdges;// 表示边的数目
  24.     //定义给数组boolean[], 记录某个结点是否被访问
  25.     private boolean[] isVisited;
  27.     public static void main(String[] args) {
  28.         int n = 5;
  29.         String Vertexs[] = {"A", "B", "C", "D", "E"};
  31.         //创建图对象
  32.         Graph graph = new Graph(n);
  33.         //循环的添加顶点
  34.         for(String vertex: Vertexs) {
  35.             graph.insertVertex(vertex);
  36.         }
  38.         //添加边
  39.         //A-B A-C B-C B-D B-E 无向图
  40.         graph.insertEdge(0, 1, 1); // A-B
  41.         graph.insertEdge(0, 2, 1); // A-C
  42.         graph.insertEdge(1, 2, 1); // B-C
  43.         graph.insertEdge(1, 3, 1); // B-D
  44.         graph.insertEdge(1, 4, 1); // B-E
  46.         graph.showGraph();
  47.         //测试一把，我们的dfs遍历是否ok
  48.         //System.out.println("深度优先遍历");
  49.         //graph.dfs();
  50.         System.out.println("广度优先遍历");
  51.         graph.bfs();
  52.     }
  54.     //初始化图
  55.     public Graph(int n){
  56.         vertexList = new ArrayList<>(n);
  57.         edges = new int[n][n];
  58.         numofEdges = 0;
  59.         isVisited = new boolean[n];
  60.     }
  61.     /**
  62.      *得到第一个邻接结点的下标 w
  63.      * @param index
  64.      * @return 如果存在就返回对应的下标，否则返回-1
  65.      */
  66.     public int getFirstNeighbor(int index){
  67.       for (int j = 0; j < vertexList.size(); j++){
  68.           if(edges[index][j] > 0){
  69.               return j;
  70.           }
  71.       }
  72.       return -1;
  73.     }
  74.     //根据前一个邻接结点的下标来获取下一个邻接结点
  75.     public int getNextNeighbor(int v1,int v2){
  76.         for (int j = v2 + 1;j < vertexList.size(); j++){
  77.             if (edges[v1][j] > 0){
  78.                 return j;
  79.             }
  80.         }
  81.         return -1;
  82.     }
  83.     //对一个结点进行广度优先遍历的方法
  84.     public void bfs(boolean[] isVisited,int i){
  85.         int u;// 表示队列的头结点对应下标
  86.         int w;// 邻接结点w
  87.         //队列，记录结点访问的顺序
  88.         LinkedList queue = new LinkedList();
  89.         //访问结点，输出结点信息
  90.         System.out.print(getValueByIndex(i) + "->");
  91.         //标记为已访问
  92.         isVisited[i] = true;
  93.         //将结点加入队列
  94.         queue.addLast(i);
  96.         while (!queue.isEmpty()){
  97.             //取出队列的头结点下标
  98.             u = (Integer)queue.removeFirst();
  99.             //得到第一个邻接结点的下标 w
  100.             w = getFirstNeighbor(u);
  101.             while (w != -1){
  102.                 //是否访问过
  103.                 if (!isVisited[w]){
  104.                     System.out.print(getValueByIndex(w) + "->");
  105.                     //标记已经访问过
  106.                     isVisited[w] = true;
  107.                     //加入队列
  108.                     queue.addLast(w);
  109.                 }
  110.                 //以u为前驱点，找w后面的下一个邻结点
  111.                 w = getNextNeighbor(u, w); //体现出我们的广度优先
  112.             }
  113.         }
  114.     }
  115.     //遍历所有的结点，都进行广度优先搜索
  116.     public void bfs(){
  117.         for (int i = 0;i < getNumofVertex(); i++){
  118.             if (!isVisited[i]){
  119.                 bfs(isVisited,i);
  120.             }
  121.         }
  122.     }
  123. }
  125. 运行结果
  127. 邻接矩阵
  128. [0, 1, 1, 1, 0]
  129. [1, 0, 1, 0, 1]
  130. [1, 1, 0, 0, 0]
  131. [1, 0, 0, 0, 0]
  132. [0, 1, 0, 0, 0]
  133. 进行广度优先遍历
  134. A->B->C->D->E->

图的深度优先 VS 广度优先

image.png

  1. public static void main(String[] args) {
  2.         int n = 8;
  3.         String Vertexs[] = {"1", "2", "3", "4", "5", "6", "7", "8"};
  5.         //创建图对象
  6.         Graph graph = new Graph(n);
  7.         //循环的添加顶点
  8.         for(String vertex: Vertexs) {
  9.             graph.insertVertex(vertex);
  10.         }
  12.         //更新边的关系
  13.         graph.insertEdge(0, 1, 1);
  14.         graph.insertEdge(0, 2, 1);
  15.         graph.insertEdge(1, 3, 1);
  16.         graph.insertEdge(1, 4, 1);
  17.         graph.insertEdge(3, 7, 1);
  18.         graph.insertEdge(4, 7, 1);
  19.         graph.insertEdge(2, 5, 1);
  20.         graph.insertEdge(2, 6, 1);
  21.         graph.insertEdge(5, 6, 1);
  23.         graph.showGraph();
  25.         //System.out.println("深度优先遍历");
  26.         //graph.dfs(); //1->2->4->8->5->3->6->7->
  27.         System.out.println("广度优先遍历");
  28.         graph.bfs(); //1->2->3->4->5->6->7->8->
  29.     }
  32. [0, 1, 1, 0, 0, 0, 0, 0]
  33. [1, 0, 0, 1, 1, 0, 0, 0]
  34. [1, 0, 0, 0, 0, 1, 1, 0]
  35. [0, 1, 0, 0, 0, 0, 0, 1]
  36. [0, 1, 0, 0, 0, 0, 0, 1]
  37. [0, 0, 1, 0, 0, 0, 1, 0]
  38. [0, 0, 1, 0, 0, 1, 0, 0]
  39. [0, 0, 0, 1, 1, 0, 0, 0]
  40. 深度优先遍历
  41. 1->2->4->8->5->3->6->7->
  42. 广度优先遍历
  43. 1->2->3->4->5->6->7->8->