devbox
小小林熬夜学编程
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

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

作者：小小林熬夜学编程 | 2024-03-22 17:06:07

赞

踩

图的遍历-----深度优先遍历（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<String> 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<String>(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<Integer> 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<String> 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<String>(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：广度优先遍历更加注重广度，会优先探索离起始节点较近的节点，可能会在较浅的层级上找到目标节点。

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

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小小林熬夜学编程/article/detail/289607
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号