数据结构 - 图 （图的深度优先和广度优先）

叁歲伎倆 2023-07-12 05:11 127阅读 0赞

图的基本介绍

为什么要有图这种数据结构

  1. 数据结构有线性表和树
  2. 线性表局限与一个直接前驱和一个直接后继的关系
  3. 树也只能右一个直接前驱也就是父节点
  4. 当我们需要表示多对多的关系时，这里我们就需要用到图这种数据结构

图是一种数据结构，其中节点可以具有零个或者多个相邻的元素。2个节点之间的连接称为边。节点也可以称为顶点。 如图：
在这里插入图片描述
图的常用概念

  1. 顶点（vertex）
  2. 边（edge）
  3. 路径
  4. 无向图（如图）
    在这里插入图片描述
  5. 有向图 （如下图）
  6. 带权图
    在这里插入图片描述

图的表示方式

图的表示方式有两种：二维数组表示（邻接矩阵）；链表表示（邻接表）。

邻接矩阵

邻接矩阵是表示图形中顶点之间相邻关系的矩阵，对于n个顶点的图而言，矩阵是的row和 col表示的是1…n个点。
在这里插入图片描述

邻接表

  1. 邻接矩阵需要为每个顶点都分配n个边的空间，其实有很多边都是不存在,会造成空间的一定损失.
  2. 邻接表的实现只关心存在的边，不关心不存在的边。因此没有空间浪费，邻接表由数组+链表组成
    在这里插入图片描述

图的案例入门
要求：代码实现如下图结构
在这里插入图片描述
思路：
保存顶点用ArrayList集合 ，保存顶点之间相邻关系的用邻接矩阵，即二维数组表示。

  1. public class Graph { 
  2.     // 存放顶点的集合
  3.     private List<String> vertexList;
  4.     // 邻接矩阵，存放顶点关系
  5.     private int[][] edges;
  6.     // 边的数目
  7.     private int numOfEdges;
  9.     public Graph(int n) { 
  10.         // n表示顶点的个数
  11.         vertexList = new ArrayList<>(n);
  12.         edges = new int[n][n];
  13.         numOfEdges = 0;
  14.     }
  16.     /** * 添加顶点的方法 * @param vertex */
  17.     public void addVertex(String vertex) { 
  18.         vertexList.add(vertex);
  19.     }
  21.     /** * 获取顶点个数 */
  22.     public int getVertexNum() { 
  23.         return vertexList.size();
  24.     }
  26.     /** * 返回对于下标的顶点 * @param i * @return */
  27.     public String getVertex(int i) { 
  28.         return vertexList.get(i);
  29.     }
  31.     /** * 添加边 * @param v1 表示第几个下标的顶点的位置 * @param v2 表示第二个顶点的下标 * @param weight 边的权 */
  32.     public void addEdge(int v1, int v2, int weight) { 
  33.         // 表示下标v1和v2顶点的边
  34.         edges[v1][v2] = weight;
  35.         // 表示下标v2和v1顶点的边
  36.         edges[v2][v1] = weight;
  37.         numOfEdges++;
  38.     }
  40.     /** * 遍历顶点 */
  41.     public void listVertex() { 
  42.         for (String s : vertexList) { 
  43.             System.out.print(s + " ");
  44.         }
  45.     }
  47.     /** * 遍历邻接矩阵，边 */
  48.     public void listEdge() { 
  49.         for (int[] edge : edges) { 
  50.             System.out.println(Arrays.toString(edge));
  51.         }
  52.     }
  53. }

测试

  1. public class MyTest { 
  3.     public static void main(String[] args) { 
  4.         Graph graph = new Graph(5);
  5.          String[] vertexs = { "A", "B", "C", "D", "E"};
  6.         for (String vertex : vertexs) { 
  7.             // 添加顶点
  8.             graph.addVertex(vertex);
  9.         }
  11.         // 添加边 A-B
  12.         graph.addEdge(0,1,1);
  13.         // 添加边 A-C
  14.         graph.addEdge(0,2,1);
  15.         // 添加边 B-C
  16.         graph.addEdge(1,2,1);
  17.         // 添加边 B-D
  18.         graph.addEdge(1,3,1);
  19.         // 添加边 B-E
  20.         graph.addEdge(1,4,1);
  22.         // 遍历顶点
  23.         graph.listVertex();
  24.         System.out.println();
  25.         // 遍历边
  26.         graph.listEdge();
  27.     }
  28. }

输出结果

  1. A B C D E 
  2. [0, 1, 1, 0, 0]
  3. [1, 0, 1, 1, 1]
  4. [1, 1, 0, 0, 0]
  5. [0, 1, 0, 0, 0]
  6. [0, 1, 0, 0, 0]

图的深度优先遍历

  • 图的遍历介绍

    所谓图的遍历，即使对节点的访问。一个图右很多节点，如何遍历这些节点，我们需要一定的策略，一般有两种策略：1.深度优先遍历，2.广度优先遍历

  • 图的深度优先遍历（Depth First Search）

    • 深度优先遍历，从初始访问结点出发，初始访问结点可能有多个邻接结点，深度优先遍历的策略就是首先访问第一个邻接结点，然后再以这个被访问的邻接结点作为初始结点，访问它的第一个邻接结点， 可以这样理解：每次都在访问完当前结点后首先访问当前结点的第一个邻接结点。
    • 我们可以看到，这样的访问策略是优先往纵向挖掘深入，而不是对一个结点的所有邻接结点进行横向访问。
    • 显然，深度优先搜索是一个递归的过程

  • 深度优先遍历算法步骤

    1. 访问初始节点V，并标记该节点V为已访问。
    2. 查找节点V的第一个邻接节点W。
    3. 若W存在，则执行步骤4，若W不存在，则回到步骤1，将从V的下一个连接节点继续
    4. 若W未被访问，对W进行深度优先遍历递归（即把 W当做另一个V，然后进行步骤123）。
    5. 若W已被访问，则查找V的W的邻接节点的下一个邻接节点，然后转到步骤3。

在这里插入图片描述

图的广度优先遍历

图的广度优先搜索类似于一个分成搜索过程，广度优先遍历需要使用一个队列以保持访问过节点的顺序，以便按这个顺序来访问这些节点的邻接节点

  • 广度优先遍历算法步骤

    1. 访问初始节点V，并标记节点V为已访问。
    2. 节点V入队列
    3. 当队列非空时，继续执行，否则算法结束
    4. 出队列，取得队头结点u。
    5. 查找结点u的第一个邻接结点w。
    6. 若结点u的邻接结点w不存在，则转到步骤3；否则循环执行以下三个 步骤
      6.1 若结点w尚未被访问，则访问结点w并标记为已访问。
      6.2 结点w入队列
      6.3 查找结点u的继w邻接结点后的下一个邻接结点w，转到步骤6。

深度优先遍历和广度优先遍历代码示例

主要方法：深度优先（dfs），广度优先（bfs）

  1. public class Graph { 
  2.     // 存放顶点的集合
  3.     private List<String> vertexList;
  4.     // 邻接矩阵，存放顶点关系
  5.     private int[][] edges;
  6.     // 边的数目
  7.     private int numOfEdges;
  8.     // 是否被访问
  9.     private boolean[] isVisited;
  11.     public Graph(int n) { 
  12.         // n表示顶点的个数
  13.         vertexList = new ArrayList<>(n);
  14.         edges = new int[n][n];
  15.         numOfEdges = 0;
  17.     }
  19.     /** * 添加顶点的方法 * @param vertex */
  20.     public void addVertex(String vertex) { 
  21.         vertexList.add(vertex);
  22.     }
  24.     /** * 查找下标为index顶点的的第一个邻接节点 * @param index * @return 返回找到的下标 ,没有找到就返回-1 */
  25.     public int getFirstNeighbor(int index) { 
  26.         for (int i = 0; i < vertexList.size(); i++) { 
  27.             if (edges[index][i] == 1){ 
  28.                 return i;
  29.             }
  30.         }
  31.         return -1;
  32.     }
  34.     /** * * @param index 初始顶点下标 * @param firstNeighbor 初始顶点的第一个个邻接节点 * @return 返回初始节点的下一个邻接节点的下标，没有就返回-1 */
  35.     public int getNextNeighbor(int index, int firstNeighbor) { 
  36.         for (int i = firstNeighbor + 1; i < vertexList.size(); i++) { 
  37.             if (edges[index][i] == 1) { 
  38.                 return i;
  39.             }
  40.         }
  41.         return -1;
  42.     }
  44.     /** * 深度优先遍历 * @param isVisited 要访问的节点是否被访问 * @param index 要访问的初始节点 */
  45.     private void dfs(boolean[] isVisited, int index) { 
  46.         isVisited = new boolean[vertexList.size()];
  47.         // 1. 访问初始节点，并把该节点标记为已访问
  48.         System.out.print(vertexList.get(index) + "->");
  49.         isVisited[index] = true;
  50.         //2. 查找节点index的第一个邻接节点
  51.         int firstNeighbor = getFirstNeighbor(index);
  52.         //3. firstNeighbor != -1 说明有邻接节点
  53.         while ( firstNeighbor != -1) { 
  54.             // 判断这邻接节点是否被访问
  55.             if (!isVisited[firstNeighbor]) { 
  56.                 //4. 没有被访问，则进行递归,把firstNeighbor当成初始节点进行递归访问
  57.                 dfs(isVisited, firstNeighbor);
  58.             }
  59.             // 5.该邻接节点已被访问，则查找index除了firstNeighbor节点的下一个邻接节点
  60.             firstNeighbor = getNextNeighbor(index, firstNeighbor);
  61.         }
  62.     }
  64.     /** * 深度优先遍历 */
  65.     public void dfs () { 
  66.         for (int i = 0; i < vertexList.size(); i++) { 
  67.             if (!isVisited[i]) { 
  68.                 dfs(isVisited, i);
  69.             }
  70.         }
  71.     }
  73.     /** * 广度优先遍历 * @param isVisited * @param index */
  74.     private void bfs(boolean[] isVisited, int index) { 
  75.         isVisited = new boolean[vertexList.size()];
  76.         // 定义一个队列，来保存访问过节点的顺序
  77.         LinkedList<Integer> queue = new LinkedList<>();
  79.         // 1. 访问初始节点，标记为已访问
  80.         System.out.println(vertexList.get(index) + "->");
  81.         isVisited[index] = true;
  82.         // 将访问过的节点入队列,注意加 到最后一个，取的时候是第一个
  83.         queue.addLast(index);
  84.         // 当队列不为空时，一直循环执行
  85.         int v;  // 用来存放队列里去除的节点下标
  86.         while (!queue.isEmpty()) { 
  87.             // 取出队列的头节点
  88.             v = queue.removeFirst();
  89.             // 查找节点v的邻接节点
  90.             int neighbor = getFirstNeighbor(v);
  91.             // 若邻接节点存在
  92.             while (neighbor != -1) { 
  93.                 // 若该节点未被访问
  94.                 if (!isVisited[neighbor]) { 
  95.                     System.out.print(vertexList.get(neighbor) + "->");
  96.                     // 标记为已访问
  97.                     isVisited[neighbor] = true;
  98.                     // 加入队列
  99.                     queue.addLast(neighbor);
  100.                 }
  101.                 // 查找v的继neighbor的下一个邻接节点
  102.                 neighbor = getNextNeighbor(v, neighbor);
  103.             }
  104.         }
  105.     }
  107.     public void bfs() { 
  108.         for (int i = 0; i < vertexList.size(); i++) { 
  109.             if (!isVisited[i]) { 
  110.                 bfs(isVisited,i);
  111.             }
  112.         }
  113.     }
  115.     /** * 获取顶点个数 */
  116.     public int getVertexNum() { 
  117.         return vertexList.size();
  118.     }
  120.     /** * 返回对于下标的顶点 * @param i * @return */
  121.     public String getVertex(int i) { 
  122.         return vertexList.get(i);
  123.     }
  125.     /** * 添加边 * @param v1 表示第几个下标的顶点的位置 * @param v2 表示第二个顶点的下标 * @param weight 边的权 */
  126.     public void addEdge(int v1, int v2, int weight) { 
  127.         // 表示下标v1和v2顶点的边
  128.         edges[v1][v2] = weight;
  129.         // 表示下标v2和v1顶点的边
  130.         edges[v2][v1] = weight;
  131.         numOfEdges++;
  132.     }
  134.     /** * 遍历顶点 */
  135.     public void listVertex() { 
  136.         for (String s : vertexList) { 
  137.             System.out.print(s + " ");
  138.         }
  139.     }
  141.     /** * 遍历邻接矩阵，边 */
  142.     public void listEdge() { 
  143.         for (int[] edge : edges) { 
  144.             System.out.println(Arrays.toString(edge));
  145.         }
  146.     }
  147. }

测试类

  1. public class MyTest { 
  2.     public static void main(String[] args) { 
  3.         Graph graph = new Graph(5);
  4.         String[] vertexs = { "A", "B", "C", "D", "E"};
  5.         for (String vertex : vertexs) { 
  6.             // 添加顶点
  7.             graph.addVertex(vertex);
  8.         }
  10.         // 添加边 A-B
  11.         graph.addEdge(0,1,1);
  12.         // 添加边 A-C
  13.         graph.addEdge(0,2,1);
  14.         // 添加边 B-C
  15.         graph.addEdge(1,2,1);
  16.         // 添加边 B-D
  17.         graph.addEdge(1,3,1);
  18.         // 添加边 B-E
  19.         graph.addEdge(1,4,1);
  21.         System.out.println("对图进行深度优先遍历：");
  22.         graph.dfs();
  24.         System.out.println();
  25.         System.out.println("广度优先遍历");
  26.         graph.bfs();
  27.     }
  28. }

测试结果

  1. 对图进行深度优先遍历：
  2. A->B->C->D->E->
  3. 广度优先遍历
  4. A->B->C->D->E->

总结：注意分析代码，深度优先和广度优先主要区别在于：

  1. 深度优先是先从初始节点开始，寻找到他的下一个邻节点，然后在以这个邻接点为初始节点，继续重复这些操作。
  2. 广度优先是从初始节点开始，寻找他的邻节点，然后再继续寻找他下一个邻节点，直到把他所有的邻节点找到，在换成队列另一个节点继续重复上面的操作，

发表评论

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

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

相关阅读