• 图的遍历-----深度优先遍历（dfs）,广度优先遍历（bfs）【java详解】

    目录

    简单介绍：什么是深度、广度优先遍历？

     深度优先搜索（DFS，Depth First Search）：

    大致图解：

     广度优先搜索（BFS，Breadth First Search）：

    大致图解：

    一.图的创建（邻接矩阵）

     图的创建完整代码：

    运行结果：

    二.图的深度优先遍历（DFS）:

    遍历思想：

    算法步骤：

     访问初始结点v：

     查找结点v的第一个邻接结点w：

    深度搜索算法：

     ​编辑

     三.图的广度优先遍历（BFS）:

    广度优先算法：

    深度 优先遍历 && 广度优先遍历的区别：

    测试用例：

    小结：

    简单介绍：什么是深度、广度优先遍历？

    图的遍历是指，从给定图中任意指定的顶点（称为初始点）出发，按照某种搜索方法沿着图的边访问图中的所有顶点，使每个顶点仅被访问一次，这个过程称为图的遍历。遍历过程中得到的顶点序列称为图遍历序列。

    图的遍历过程中，根据搜索方法的不同，又可以划分为两种搜索策略：

    • 深度优先搜索（DFS，Depth First Search）
    • 广度优先搜索（BFS，Breadth First Search）

     深度优先搜索（DFS，Depth First Search）：

    遍历思想：：首先从图中某个顶点v0出发，访问此顶点，标记已访问的顶点，然后依次从v0相邻的顶点出发深度优先遍历，直至图中所有与v路径相通的顶点都被访问了；若此时尚有顶点未被访问，则从中选一个顶点作为起始点，重复上述过程，直到所有的顶点都被访问。

    大致图解：

     广度优先搜索（BFS，Breadth First Search）：

    遍历思想：首先，从图的某个顶点v0出发，访问了v0之后，依次访问与v0相邻的未被访问的顶点，然后分别从这些顶点出发，广度优先遍历，直至所有的顶点都被访问完。

    大致图解：

    一.图的创建（邻接矩阵）

     图的遍历基础是我们首先得有个图，这里我们创建一个图，用邻接矩阵的方法。这里我们创建一个如下图所示的图（左边是图，右边是图所对应的表示方法）：

     图的创建完整代码：

    1. import java.util.*;
    2. public class Graph {
    3.     private ArrayList vertexList;//一个一维数组用于存储顶点的信息
    4.     private int[][] edges;//一个二维数组用于存储对应边的信息
    5.     private int numOfEdges;//记录边的个数
    6.     private boolean[] isVisited;//判断顶点是否被访问
    7.      //测试
    8.     public static void main(String[] args){
    9.         String vertexs[] = {"A","B","C","D","E"};
    10.         Graph graph = new Graph(5);
    11.         for(String vertex : vertexs){
    12.             graph.insertVertex(vertex);
    13.         }
    14.         //插入的节点展示：
    15.         System.out.println("插入的节点展示：");
    16.         for(String vertex : vertexs){
    17.             System.out.print(vertex+" ");
    18.         }
    19.         System.out.println();                 //  A B C D E
    20.         graph.insertEdge(0,1,1);              //A 0 1 1 0 0
    21.         graph.insertEdge(0,2,1);              //B 1 0 1 1 1
    22.         graph.insertEdge(1,2,1);              //C 1 1 0 0 0
    23.         graph.insertEdge(1,3,1);              //D 0 1 0 0 0
    24.         graph.insertEdge(1,4,1);              //E 0 1 0 0 0
    25.         //创建的图展示：
    26.         System.out.println("创建的图展示：");
    27.         graph.showGraph();
    28.         //边个数
    29.         System.out.println("边个数:"+graph.numOfEdges);
    30.     }
    31.     //构造器
    32.     public Graph(int n){
    33.         vertexList = new ArrayList(n);
    34.         edges = new int[n][n];
    35.         numOfEdges = 0;
    36.     }
    37.  
    38.     //图的创建和展示--》方法
    39.     //展示图
    40.     public void showGraph(){
    41.         for(int[] link : edges){
    42.             System.out.println(Arrays.toString(link));
    43.         }
    44.     }
    45.     //插入顶点
    46.     public void insertVertex(String vertex){
    47.         vertexList.add(vertex);
    48.     }
    49.     //插入边
    50.     public void insertEdge(int v1,int v2,int weight){
    51.         edges[v1][v2] = 1;
    52.         edges[v2][v1] = 1;
    53.         numOfEdges++;
    54.     }
    55. //图的常见方法
    56.    //得到顶点个数
    57.     public int getNumOfVertex(){
    58.         return vertexList.size();
    59.     }
    60.     //通过索引得到对应的顶点
    61.     public String gerValueByIndex(int i){
    62.         return vertexList.get(i);
    63.     }
    64.     //得到对应边的权重
    65.     public int getWeight(int v1,int v2){
    66.         return edges[v1][v2];
    67.     }
    68. }

    运行结果：

    二.图的深度优先遍历（DFS）:

    遍历思想：

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

    算法步骤：

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

     还是以上面创建的图为例：

     访问初始结点v：

    1. //1.得到第一个邻接点的下标
    2.     public int getFirstNeifhbor(int index){
    3.         for(int j = 0;j < vertexList.size();j++){
    4.             if(edges[index][j] > 0){
    5.                 return j;
    6.             }
    7.         }
    8.         return -1;
    9.     }

     查找结点v的第一个邻接结点w：

    1. //2.根据前一个邻接点的下标获取下一个邻接点
    2.     public int getNextNeighbor(int v1,int v2){
    3.         for(int j = v2 + 1;j < vertexList.size();j++){
    4.             if(edges[v1][j] > 0){
    5.                 return j;
    6.             }
    7.         }
    8.         return -1;
    9.     }

    深度搜索算法：

    1. //深搜遍历算法
    2.     //first step
    3.     private void dfs(boolean[] isVisited,int i){
    4.         System.out.print(getValueByIndex(i)+"->");
    5.         isVisited[i] = true;
    6.         int w = getFirstNeifhbor(i);
    7.         while(w != -1){
    8.             if(!isVisited[w]){
    9.                 dfs(isVisited,w);
    10.             }
    11.             w = getNextNeighbor(i,w);
    12.         }
    13.     }
    14. //second step
    15.     public void dfs(){
    16.         isVisited = new boolean[vertexList.size()];
    17.         for(int i = 0;i < vertexList.size();i++){
    18.             if(!isVisited[i]){
    19.                 dfs(isVisited,i);
    20.             }
    21.         }
    22.     }

    遍历结果：

     

     三.图的广度优先遍历（BFS）:

    基本思想：

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

    算法步骤：

    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。

    广度优先算法：

    用LinkedList 模拟队列：

    1. //对一个结点进行广度优先遍历的方法
    2. private void bfs(boolean[] isVisited, int i) {
    3. 	int u ; // 表示队列的头结点对应下标
    4. 	int w ; // 邻接结点w
    5. 	//队列，记录结点访问的顺序
    6. 	LinkedList queue = new LinkedList();
    7. 	//访问结点，输出结点信息
    8. 	System.out.print(getValueByIndex(i) + "=>");
    9. 	//标记为已访问
    10. 	isVisited[i] = true;
    11. 	//将结点加入队列
    12. 	queue.addLast(i);
    13. 	
    14. 	while( !queue.isEmpty()) {
    15. 		//取出队列的头结点下标
    16. 		u = (Integer)queue.removeFirst();
    17. 		//得到第一个邻接结点的下标 w 
    18. 		w = getFirstNeighbor(u);
    19. 		while(w != -1) {//找到
    20. 			//是否访问过
    21. 			if(!isVisited[w]) {
    22. 				System.out.print(getValueByIndex(w) + "=>");
    23. 				//标记已经访问
    24. 				isVisited[w] = true;
    25. 				//入队
    26. 				queue.addLast(w);
    27. 			}
    28. 			//以u为前驱点，找w后面的下一个邻结点
    29. 			w = getNextNeighbor(u, w); //体现出我们的广度优先
    30. 		}
    31. 	}
    32. 	
    33. } 
    34. //遍历所有的结点，都进行广度优先搜索
    35. public void bfs() {
    36. 	isVisited = new boolean[vertexList.size()];
    37. 	for(int i = 0; i < getNumOfVertex(); i++) {
    38. 		if(!isVisited[i]) {
    39. 			bfs(isVisited, i);
    40. 		}
    41. 	}
    42. }

     用Queue集合：

    1. //广度优先遍历
    2.     public void bfs(boolean[] isVisited,int i){
    3.         int u;
    4.         int w;
    5.         Queue queue = new LinkedList<>();
    6.         System.out.print(getValueByIndex(i)+"->");
    7.         isVisited[i] = true;
    8.         queue.add(i);
    9.         while(!queue.isEmpty()){
    10.             u = queue.poll();
    11.             w = getFirstNeighbor(u);
    12.             while(w != -1){
    13.                 if(!isVisited[w]){
    14.                     System.out.print(getValueByIndex(w)+"->");
    15.                     isVisited[w] = true;
    16.                     queue.add(w);
    17.                 }
    18.                 w = getNextNeighbor(u,w);
    19.             }
    20.         }
    21.     }
    22.     public void bfs(){
    23.         isVisited = new boolean[vertexList.size()];
    24.         for(int i = 0;i < vertexList.size();i++){
    25.             if(!isVisited[i]){
    26.                 bfs(isVisited,i);
    27.             }
    28.         }
    29.     }

    遍历结果： 

    深度 优先遍历 && 广度优先遍历的区别：

     这里由于上面的图比较简单，看不出深度和广度优先遍历的区别，我在举一个图的栗子：

    测试用例：

    1.  public static void main(String[] args){
    2.  
    3.         int n = 8;  //结点的个数
    4.         String Vertexs[] = {"1", "2", "3", "4", "5", "6", "7", "8"};
    5.  
    6.         //创建图对象
    7.         Graph graph = new Graph(n);
    8.         //循环的添加顶点
    9.         for(String vertex: Vertexs) {
    10.             graph.insertVertex(vertex);
    11.         }
    12.  
    13.         //更新边的关系
    14.         graph.insertEdge(0, 1, 1);
    15.         graph.insertEdge(0, 2, 1);
    16.         graph.insertEdge(1, 3, 1);
    17.         graph.insertEdge(1, 4, 1);
    18.         graph.insertEdge(3, 7, 1);
    19.         graph.insertEdge(4, 7, 1);
    20.         graph.insertEdge(2, 5, 1);
    21.         graph.insertEdge(2, 6, 1);
    22.         graph.insertEdge(5, 6, 1);
    23.  
    24.         //显示一把邻结矩阵
    25.         System.out.println("图的创建：");
    26.         graph.showGraph();
    27.  
    28.         //测试一把，我们的dfs遍历是否ok
    29.         System.out.println("深度优先遍历：");
    30.         graph.dfs(); // A->B->C->D->E [1->2->4->8->5->3->6->7]
    31.         System.out.println();
    32.         System.out.println("广度优先遍历：");
    33.         graph.bfs(); // A->B->C->D-E [1->2->3->4->5->6->7->8]
    34.     }

    运行结果：

    最后完整代码：

    1. import java.util.*;
    2.  
    3. public class Graph {
    4.     private ArrayList vertexList;
    5.     private int[][] edges;
    6.     private int numOfEdges;
    7.     private boolean[] isVisited;
    8.  
    9.     public static void main(String[] args){
    10.  
    11.         int n = 8;  //结点的个数
    12.         String Vertexs[] = {"1", "2", "3", "4", "5", "6", "7", "8"};
    13.  
    14.         //创建图对象
    15.         Graph graph = new Graph(n);
    16.         //循环的添加顶点
    17.         for(String vertex: Vertexs) {
    18.             graph.insertVertex(vertex);
    19.         }
    20.  
    21.         //更新边的关系
    22.         graph.insertEdge(0, 1, 1);
    23.         graph.insertEdge(0, 2, 1);
    24.         graph.insertEdge(1, 3, 1);
    25.         graph.insertEdge(1, 4, 1);
    26.         graph.insertEdge(3, 7, 1);
    27.         graph.insertEdge(4, 7, 1);
    28.         graph.insertEdge(2, 5, 1);
    29.         graph.insertEdge(2, 6, 1);
    30.         graph.insertEdge(5, 6, 1);
    31.  
    32.         //显示一把邻结矩阵
    33.         System.out.println("图的创建：");
    34.         graph.showGraph();
    35.  
    36.         //测试一把，我们的dfs遍历是否ok
    37.         System.out.println("深度优先遍历：");
    38.         graph.dfs(); // A->B->C->D->E [1->2->4->8->5->3->6->7]
    39.         System.out.println();
    40.         System.out.println("广度优先遍历：");
    41.         graph.bfs(); // A->B->C->D-E [1->2->3->4->5->6->7->8]
    42.     }
    43.     //构造器
    44.     public Graph(int n){
    45.         vertexList = new ArrayList(n);
    46.         edges = new int[n][n];
    47.         numOfEdges = 0;
    48.     }
    49.  
    50.     //图的常见方法
    51.     public int getNumOfVertex(){
    52.         return vertexList.size();
    53.     }
    54.     public String getValueByIndex(int i){
    55.         return vertexList.get(i);
    56.     }
    57.     public int getWeight(int v1,int v2){
    58.         return edges[v1][v2];
    59.     }
    60.     //图的创建和展示
    61.     public void showGraph(){
    62.         for(int[] link : edges){
    63.             System.out.println(Arrays.toString(link));
    64.         }
    65.     }
    66.     public void insertVertex(String vertex){
    67.         vertexList.add(vertex);
    68.     }
    69.     public void insertEdge(int v1,int v2,int weight){
    70.         edges[v1][v2] = 1;
    71.         edges[v2][v1] = 1;
    72.         numOfEdges++;
    73.     }
    74.     //深度优先搜索：
    75.     //1.得到第一个邻接点的下标
    76.     public int getFirstNeighbor(int index){
    77.         for(int j = 0;j < vertexList.size();j++){
    78.             if(edges[index][j] > 0){
    79.                 return j;
    80.             }
    81.         }
    82.         return -1;
    83.     }
    84.     //2.根据前一个邻接点的下标获取下一个邻接点
    85.     public int getNextNeighbor(int v1,int v2){
    86.         for(int j = v2 + 1;j < vertexList.size();j++){
    87.             if(edges[v1][j] > 0){
    88.                 return j;
    89.             }
    90.         }
    91.         return -1;
    92.     }
    93.     //深搜遍历算法
    94.     //first step
    95.     private void dfs(boolean[] isVisited,int i){
    96.         System.out.print(getValueByIndex(i)+"->");
    97.         isVisited[i] = true;
    98.         int w = getFirstNeighbor(i);
    99.         while(w != -1){
    100.             if(!isVisited[w]){
    101.                 dfs(isVisited,w);
    102.             }
    103.             w = getNextNeighbor(i,w);
    104.         }
    105.     }
    106.     //second step
    107.     public void dfs(){
    108.         isVisited = new boolean[vertexList.size()];
    109.         for(int i = 0;i < vertexList.size();i++){
    110.             if(!isVisited[i]){
    111.                 dfs(isVisited,i);
    112.             }
    113.         }
    114.     }
    115.  
    116.     //广度优先遍历：
    117.     //first steop
    118.     public void bfs(boolean[] isVisited,int i){
    119.         int u;
    120.         int w;
    121.         LinkedList queue = new LinkedList();
    122.         System.out.print(getValueByIndex(i)+"->");
    123.         isVisited[i] = true;
    124.         queue.addLast(i);
    125.         while(!queue.isEmpty()){
    126.             u = (Integer) queue.removeFirst();
    127.             w = getFirstNeighbor(u);
    128.             while(w != -1){
    129.                 if(!isVisited[w]){
    130.                     System.out.print(getValueByIndex(w)+"->");
    131.                     isVisited[w] = true;
    132.                     queue.addLast(w);
    133.                 }
    134.                 w = getNextNeighbor(u,w);
    135.             }
    136.         }
    137.     }
    138.     //second step
    139.     public void bfs(){
    140.         isVisited = new boolean[vertexList.size()];
    141.         for(int i = 0;i < getNumOfVertex();i++){
    142.             if(!isVisited[i]){
    143.                 bfs(isVisited,i);
    144.             }
    145.         }
    146.     }
    147. }

    小结：

    图的深度优先遍历（Depth First Search，DFS）和广度优先遍历（Breadth First Search，BFS）是两种常用的图遍历算法，它们的主要区别如下：

    1. 遍历顺序：

      • DFS：从起始节点开始，沿着一条路径尽可能深入地遍历，直到无法继续深入为止，然后回溯到前一个节点，再选择另一条路径继续遍历，直到遍历完所有节点。
      • BFS：从起始节点开始，先遍历其所有相邻节点，然后再依次遍历这些相邻节点的相邻节点，以此类推，直到遍历完所有节点。

    2. 数据结构：

      • DFS：通常使用栈（Stack）数据结构来实现，通过递归或显式栈来保存遍历路径。
      • BFS：通常使用队列（Queue）数据结构来实现，通过将节点按照遍历顺序依次加入队列中。

    3. 遍历顺序的特点：

      • DFS：深度优先遍历更加注重深度，会优先探索离起始节点较远的节点，可能会在较深的层级上找到目标节点。
      • BFS：广度优先遍历更加注重广度，会优先探索离起始节点较近的节点，可能会在较浅的层级上找到目标节点。

    结语： 写博客不仅仅是为了分享学习经历，同时这也有利于我巩固自己的知识点，总结该知识点，由于作者水平有限，对文章有任何问题的还请指出，接受大家的批评，让我改进。同时也希望读者们不吝啬你们的点赞+关注+收藏，你们的鼓励是我创作的最大动力！

  • 相关阅读:
    SAP-QM-动态检验规则
    Windows原理深入学习系列-Windows内核提权
    直播平台源码开发搭建APP的DASH协议：流媒体技术其中一环
    解读PowerJob的秘密武器：探索Akka Toolkit原理
    创建基于多任务的并发服务器
    【遥感科学】遥感科学绪论
    CentOS7启动网卡
    山海鲸大屏：驱动医药零售智能化变革
    蓝桥杯DP算法——区间DP（C++）
    文件批量重命名加前缀的方法
  • 原文地址：https://blog.csdn.net/2302_79862386/article/details/136216060