0
0

DFS和BFS（广度优先搜索和深度优先搜索）5个经典例子

目录标题

题目1

在这里插入图片描述

  1. static String b[] = { "a", "b", "c", "d", "e", "f", "g" };
  2. static int [][]arr= {
  3.             {0,0,1,1,0,1,0},
  4.             {0,0,1,0,0,0,0},
  5.             {1,1,0,1,0,0,0},
  6.             {1,0,1,0,0,0,0},
  7.             {0,0,0,0,0,0,1},
  8.             {1,0,0,0,0,0,1},
  9.             {0,0,0,0,1,1,0}
  10.     };

对此二维数组进行深度搜索与广度搜索，并遍历结果。

深搜结果
a c b d f g e
广搜结果
a c d f b g e

深搜的遍历过程就是尽可能深的搜索树的分支，当一个节点的所有子节点都被探寻过了，搜索将回溯到发现该节点的那那条边的起始节点
这个过程会一直持续到已发现节点可到达所有节点为止。
如果还存在未发现的节点则进程会随便选择一个未发现的节点重复以上的过程
整个进程直到所有节点都被访问过为止。

深度优先搜索遍历过程
从a开始搜索可以看到a的子节点有c、d、f系统会依次对其进行深度优先搜索
进程先对c进行子节点的搜索可以看出c有两个子节点b、d
可以看出b没有子节点了，但是d节点作为c的子节点还没有被访问所有这个时候程序会走到d的位置
但是d也没有子节点这个时候进程会回溯到发现d的这条边的起始节点a的位置然后在对其进行搜索
a的子节点中只有f没有被遍历了所以进程只能进到f的位置然后在对其进行遍历可以看出f的两个子节点也没有子节点
所以进程在对g、e进行完遍历之后进程结束

广度优先搜索
和深搜不同广搜会沿着树的高度和宽度对节点进行依次遍历
从树的根节点a开始，会发现a的子节点有c、d、f三个子节点，进程会先对这三个节点进行访问然后再访问其的子节点
对c、d、f完成访问之后进行则会探寻这三个节点的子节点并对其进行遍历，可以从图中看出他们的子节点有c、g、e
可以看出c、g、e没有子节点了所以程序对其遍历之后随之结束

  1. 深搜代码
  2. public class dfs {
  3.     // 构造图的边
  4.     private int[][] edges = { 
  5.             {0,0,1,1,0,1,0},
  6.             {0,0,1,0,0,0,0},
  7.             {1,1,0,1,0,0,0},
  8.             {1,0,1,0,0,0,0},
  9.             {0,0,0,0,0,0,1},
  10.             {1,0,0,0,0,0,1},
  11.             {0,0,0,0,1,1,0}
  12.             };
  13.     // 构造图的顶点
  14.     private String[] vertexs = { "a", "b", "c", "d", "e", "f", "g" };
  15.     // 记录被访问顶点
  16.     private boolean[] verStatus;
  17.     // 顶点个数
  18.     private int vertexsNum = vertexs.length;
  19.     public void DFSTra() {
  20.         verStatus = new boolean[vertexsNum];
  21.         for (int i = 0; i < vertexsNum; i++) {
  22.             if (verStatus[i] == false) {
  23.                 DFS(i);
  24.             }
  25.         }
  26.     }
  27.     // 递归深搜
  28.     private void DFS(int i) {
  29.         System.out.print(vertexs[i] + " ");
  30.         verStatus[i] = true;
  31.         //深度搜索子节点
  32.         for (int j = firstAdjVex(i); j >= 0; j = nextAdjvex(i, j)) {
  33.             if (!verStatus[j]) {
  34.                 DFS(j);
  35.             }
  36.         }
  37.     }
  38.     // 返回与i相连的第一个顶点
  39.     private int firstAdjVex(int i) {
  40.         for (int j = 0; j < vertexsNum; j++) {
  41.             if (edges[i][j] > 0) {
  42.                 return j;
  43.             }
  44.         }
  45.         return -1;
  46.     }
  47.     // 返回与i相连的下一个顶点
  48.     private int nextAdjvex(int i, int k) {
  49.         for (int j = (k + 1); j < vertexsNum; j++) {
  50.             if (edges[i][j] == 1) {
  51.                 return j;
  52.             }
  53.         }
  54.         return -1;
  55.     }
  57.     // 测试
  58.     public static void main(String[] args) {
  59.         new dfs().DFSTra();
  60.     }
  62. }
  64. 广搜代码
  65. import java.util.LinkedList;
  66. import java.util.Queue;
  68. public class bfs {
  69.      // 构造图的边
  70.     private int[][] edges = { 
  71.             {0,0,1,1,0,1,0},
  72.             {0,0,1,0,0,0,0},
  73.             {1,1,0,1,0,0,0},
  74.             {1,0,1,0,0,0,0},
  75.             {0,0,0,0,0,0,1},
  76.             {1,0,0,0,0,0,1},
  77.             {0,0,0,0,1,1,0}
  78.             };
  79.     // 构造图的顶点
  80.     private String[] vertexs = { "a", "b", "c", "d", "e", "f", "g" };
  81.     // 记录被访问顶点
  82.     private boolean[] verStatus;
  83.     // 顶点个数
  84.     private int vertexsNum = vertexs.length;
  85.     // 广搜
  86.     private void BFS() {
  87.         verStatus = new boolean[vertexsNum];
  88.         Queue<Integer> temp = new LinkedList<Integer>();
  89.         //遍历每个节点
  90.         for (int i = 0; i < vertexsNum; i++) {
  91.             //判断当前节点是否被访问过
  92.             if (!verStatus[i]) {//如果没有被访问的话则将其加入队列
  93.                 System.out.print(vertexs[i] + " ");
  94.                 verStatus[i] = true;
  95.                 temp.offer(i);
  96.                 while (!temp.isEmpty()) {
  97.                     //将最先进入队列的节点移除
  98.                     int j = temp.poll();
  99.                     //广度搜索子节点
  100.                     for (int k = firstAdjvex(j); k >= 0; k = nextAdjvex(j, k)) {
  101.                         if (!verStatus[k]) {
  102.                             System.out.print(vertexs[k] + " ");
  103.                             verStatus[k] = true;
  104.                             temp.offer(k);
  105.                         }
  106.                     }
  107.                 }
  108.             }
  109.         }
  110.     }
  111.     // 返回与i相连的第一个顶点
  112.     private int firstAdjvex(int i) {
  113.         for (int j = 0; j < vertexsNum; j++) {
  114.             if (edges[i][j] > 0) {
  115.                 return j;
  116.             }
  117.         }
  118.         return -1;
  119.     }
  120.     // 返回与i相连的下一个顶点
  121.     private int nextAdjvex(int i, int k) {
  122.         for (int j = (k + 1); j < vertexsNum; j++) {
  123.             if (edges[i][j] > 0) {
  124.                 return j;
  125.             }
  126.         }
  127.         return -1;
  128.     }
  130.     // 测试
  131.     public static void main(String args[]) {
  132.         new bfs().BFS();
  133.     }
  134. }

题目2

在这里插入图片描述
static int[][] nums = {
{ 0 , 1 , 0 , 0 , 0 , 0 , 0, 1 , 0},
{ 1 , 0, 1 ,0 , 1 , 0 , 0 , 0 , 0},
{ 0 , 1 , 0 , 1 , 0 ,0 , 0 , 0 , 0},
{ 0 , 0 , 1 , 0 , 1 , 1 , 0 , 0 ,0},
{ 0 , 1 , 0 , 1 , 0 , 0 , 0 , 0 , 0},
{ 0 , 0 , 0 , 1 , 0 , 0 , 1 , 1 , 0},
{ 0 , 0 , 0 , 0 , 0 , 1, 0 , 0 , 0},
{ 1 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 1},
{ 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0}
};

static String res[] = {“1”,“2”,“3”,“4”,“5”,“6”,“7”,“8”,“9” };
对此二维数组进行深度搜索与广度搜索，并遍历结果。

深搜结果
1 2 3 4 5 6 7 8 9
广搜结果
1 2 8 3 5 6 9 4 7

深搜的遍历过程就是尽可能深的搜索树的分支，当一个节点的所有子节点都被探寻过了，搜索将回溯到发现该节点的那那条边的起始节点
这个过程会一直持续到已发现节点可到达所有节点为止。
如果还存在未发现的节点则进程会随便选择一个未发现的节点重复以上的过程
整个进程直到所有节点都被访问过为止。

深搜遍历过程
从1开始搜索可以看到1的子节点有2、8两个，进程会依次对其进行深度优先搜索
进程先对2进行子节点的搜索可以看出2也有两个子节点3、5
然后进程又会对3进行子节点的搜索可以看出只有一个子节点4，而4没有子节点了这个时候进程就会回溯到2的位置然后对5进行子节点的搜索
可以看出5的子节点也是只有一个4，但是这个时候5还有一个父节点6没有被访问所以进程不会回溯到2的位置
而是对6进行子节点的搜索，6的子节点只有一个7这个时候进程又会发现6有父节点8没有访问过
所以进程会对8再次再次进行子节点的搜索，发现子节点只有6和9但是6已经访问过了，而9也没有子节点
到这里树的所有节点就完成了全部的探索了

广搜遍历过程
和深搜不同广搜会沿着树的高度和宽度对节点进行依次遍历
从树的根节点1开始，会发现1的子节点有2、8两个子节点，进程会先对这两个节点进行访问然后再访问其的子节点
对2、8完成访问之后进行则会探寻这两个节点的子节点并对其进行遍历，可以从图中看出他们的子节点有3、5、6、9
然后进程对着4个节点完成遍历之后会再次探寻其的子节点可以看出只有4和7了且无子节点
在对4和7完成遍历之后整个进程也就随之结束了

  1. 深搜代码
  2. publicclass dfs {// 构造图的边privateint[][] edges ={{0,1,0,0,0,0,0,1,0},{1,0,1,0,1,0,0,0,0},{0,1,0,1,0,0,0,0,0},{0,0,1,0,1,1,0,0,0},{0,1,0,1,0,0,0,0,0},{0,0,0,1,0,0,1,1,0},{0,0,0,0,0,1,0,0,0},{1,0,0,0,0,1,0,0,1},{0,0,0,0,0,0,0,1,0}};// 构造图的顶点privateString[] vertexs ={"1","2","3","4","5","6","7","8","9"};// 记录被访问顶点privateboolean[] verStatus;// 顶点个数privateint vertexsNum = vertexs.length;publicvoidDFSTra(){
  3.         verStatus =newboolean[vertexsNum];for(int i =0; i < vertexsNum; i++){if(verStatus[i]==false){DFS(i);}}}// 递归深搜privatevoidDFS(int i){System.out.print(vertexs[i]+" ");
  4.         verStatus[i]=true;//深度搜索子节点for(int j =firstAdjVex(i); j >=0; j =nextAdjvex(i, j)){if(!verStatus[j]){DFS(j);}}}// 返回与i相连的第一个顶点privateintfirstAdjVex(int i){for(int j =0; j < vertexsNum; j++){if(edges[i][j]>0){return j;}}return-1;}// 返回与i相连的下一个顶点privateintnextAdjvex(int i,int k){for(int j =(k +1); j < vertexsNum; j++){if(edges[i][j]==1){return j;}}return-1;}// 测试publicstaticvoidmain(String[] args){newdfs().DFSTra();}}
  1. 广搜代码
  2. importjava.util.LinkedList;importjava.util.Queue;publicclass bfs {// 构造图的边privateint[][] edges ={{0,1,0,0,0,0,0,1,0},{1,0,1,0,1,0,0,0,0},{0,1,0,1,0,0,0,0,0},{0,0,1,0,1,1,0,0,0},{0,1,0,1,0,0,0,0,0},{0,0,0,1,0,0,1,1,0},{0,0,0,0,0,1,0,0,0},{1,0,0,0,0,1,0,0,1},{0,0,0,0,0,0,0,1,0}};// 构造图的顶点privateString[] vertexs ={"1","2","3","4","5","6","7","8","9"};// 记录被访问顶点privateboolean[] verStatus;// 顶点个数privateint vertexsNum = vertexs.length;// 广搜privatevoidBFS(){
  3.         verStatus =newboolean[vertexsNum];Queue<Integer> temp =newLinkedList<Integer>();//遍历每个节点for(int i =0; i < vertexsNum; i++){//判断当前节点是否被访问过if(!verStatus[i]){//如果没有被访问的话则将其加入队列System.out.print(vertexs[i]+" ");
  4.                 verStatus[i]=true;
  5.                 temp.offer(i);while(!temp.isEmpty()){//将最先进入队列的节点移除int j = temp.poll();//广度搜索子节点for(int k =firstAdjvex(j); k >=0; k =nextAdjvex(j, k)){if(!verStatus[k]){System.out.print(vertexs[k]+" ");
  6.                             verStatus[k]=true;
  7.                             temp.offer(k);}}}}}}// 返回与i相连的第一个顶点privateintfirstAdjvex(int i){for(int j =0; j < vertexsNum; j++){if(edges[i][j]>0){return j;}}return-1;}// 返回与i相连的下一个顶点privateintnextAdjvex(int i,int k){for(int j =(k +1); j < vertexsNum; j++){if(edges[i][j]>0){return j;}}return-1;}// 测试publicstaticvoidmain(String args[]){newbfs().BFS();}}

题目3

在这里插入图片描述
static int[][] nums = {
{ 0 , 1 , 1 , 1 , 0 , 0 , 0},
{ 1 , 0 , 1 , 0 , 0 , 1 , 0},
{ 1 , 1 , 0 , 1 , 1 , 0 , 0},
{ 1 , 0 , 1 , 0 , 0 , 0 , 1},
{ 0 , 0 , 1 , 0 , 0 , 0 , 0},
{ 0 , 1 , 0 , 0 , 0 , 0 , 1},
{ 0 , 0 , 0 , 1 , 0 , 1 , 0},
};

static String res[] = { “v1”, “v2”, “v3”, “v4”, “v5”, “v6”, “v7” };
对此二维数组进行深度搜索与广度搜索，并遍历结果。

深搜结果
v1 v2 v3 v4 v7 v6 v5
广搜结果
v1 v2 v3 v4 v6 v5 v7

深搜的遍历过程就是尽可能深的搜索树的分支，当一个节点的所有子节点都被探寻过了，搜索将回溯到发现该节点的那那条边的起始节点
这个过程会一直持续到已发现节点可到达所有节点为止。
如果还存在未发现的节点则进程会随便选择一个未发现的节点重复以上的过程
整个进程直到所有节点都被访问过为止。

深搜遍历过程
从v1开始搜索可以看到a的子节点有v2、v3、v4系统会依次对其进行深度优先搜索
进程先对v2进行子节点的搜索可以看出v2有两个子节点v3、v4
进程会先对v3进行遍历会发现v3的子节点只有v4，然后v4只有一个子节点v7
进程遍历到v7的时候因为v7还有一个父节点v6没有被访问所以进程会走到v6的位置因为v6的根节点已经遍历了
所以进程会返回到发现v6这条边的起始点也就是v1，但是这个时候还有节点没有被遍历所以
进程会随便选择一个未发现的节点进入然后遍历从图中看出只有v5没有遍历了所以
对v5进行遍历之后进程也就随之结束了

广搜遍历过程
和深搜不同广搜会沿着树的高度和宽度对节点进行依次遍历
从树的根节点v1开始，会发现v1的子节点有v2、v3、v4三个子节点，进程会先对这三个节点进行访问然后再遍历其的子节点
对v2、v3、v4完成访问之后则会探寻这三个节点的子节点并对其进行遍历，可以从图中看出他们未访问的子节点只有v6、v5、v7
而v6、v7、v5没有子节点了所以程序对其遍历之后随之结束

  1. 深搜代码
  2. publicclass dfs {privateint[][] edges ={{0,1,1,1,0,0,0},{1,0,1,0,0,1,0},{1,1,0,1,1,0,0},{1,0,1,0,0,0,1},{0,0,1,0,0,0,0},{0,1,0,0,0,0,1},{0,0,0,1,0,1,0},};// 构造图的顶点privateString[] vertexs ={"v1","v2","v3","v4","v5","v6","v7"};// 记录被访问顶点privateboolean[] verStatus;// 顶点个数privateint vertexsNum = vertexs.length;publicvoidDFSTra(){
  3.         verStatus =newboolean[vertexsNum];for(int i =0; i < vertexsNum; i++){if(verStatus[i]==false){DFS(i);}}}// 递归深搜privatevoidDFS(int i){System.out.print(vertexs[i]+" ");
  4.         verStatus[i]=true;//深度搜索子节点for(int j =firstAdjVex(i); j >=0; j =nextAdjvex(i, j)){if(!verStatus[j]){DFS(j);}}}// 返回与i相连的第一个顶点privateintfirstAdjVex(int i){for(int j =0; j < vertexsNum; j++){if(edges[i][j]>0){return j;}}return-1;}// 返回与i相连的下一个顶点privateintnextAdjvex(int i,int k){for(int j =(k +1); j < vertexsNum; j++){if(edges[i][j]==1){return j;}}return-1;}// 测试publicstaticvoidmain(String[] args){newdfs().DFSTra();}}
  1. 广搜代码
  2. publicclass bfs {// 构造图的边privateint[][] edges ={{0,1,1,1,0,0,0},{1,0,1,0,0,1,0},{1,1,0,1,1,0,0},{1,0,1,0,0,0,1},{0,0,1,0,0,0,0},{0,1,0,0,0,0,1},{0,0,0,1,0,1,0},};// 构造图的顶点privateString[] vertexs ={"v1","v2","v3","v4","v5","v6","v7"};// 记录被访问顶点privateboolean[] verStatus;// 顶点个数privateint vertexsNum = vertexs.length;// 广搜privatevoidBFS(){
  3.         verStatus =newboolean[vertexsNum];Queue<Integer> temp =newLinkedList<Integer>();//遍历每个节点for(int i =0; i < vertexsNum; i++){//判断当前节点是否被访问过if(!verStatus[i]){//如果没有被访问的话则将其加入队列System.out.print(vertexs[i]+" ");
  4.                 verStatus[i]=true;
  5.                 temp.offer(i);while(!temp.isEmpty()){//将最先进入队列的节点移除int j = temp.poll();//广度搜索子节点for(int k =firstAdjvex(j); k >=0; k =nextAdjvex(j, k)){if(!verStatus[k]){System.out.print(vertexs[k]+" ");
  6.                             verStatus[k]=true;
  7.                             temp.offer(k);}}}}}}// 返回与i相连的第一个顶点privateintfirstAdjvex(int i){for(int j =0; j < vertexsNum; j++){if(edges[i][j]>0){return j;}}return-1;}// 返回与i相连的下一个顶点privateintnextAdjvex(int i,int k){for(int j =(k +1); j < vertexsNum; j++){if(edges[i][j]>0){return j;}}return-1;}// 测试publicstaticvoidmain(String args[]){newbfs().BFS();}}

题目4

在这里插入图片描述
static int[][] nums = {
{ 0 , 1 , 1 , 0 ,0 ,0},
{ 1 , 0 ,1 , 1 ,0, 0},
{ 1 , 1 , 0 ,1 , 1 , 0},
{ 0 , 1 , 1 , 0 , 1 , 1},
{ 0 , 0 , 1 , 1 , 0 , 0},
{ 0 , 0 , 0 , 1 , 0 , 0},
};

static String res[] = { “a”, “b”, “c”, “d”, “e”, “f”};
对此二维数组进行深度搜索与广度搜索，并遍历结果。

深搜结果
a b c d e f
广搜结果
a b c d e f

深搜的遍历过程就是尽可能深的搜索树的分支，当一个节点的所有子节点都被探寻过了，搜索将回溯到发现该节点的那那条边的起始节点
这个过程会一直持续到已发现节点可到达所有节点为止。
如果还存在未发现的节点则进程会随便选择一个未发现的节点重复以上的过程
整个进程直到所有节点都被访问过为止。

深搜遍历过程
从a开始搜索可以看到1的子节点有b、c两个，进程会依次对其进行深度优先搜索
进程先对b进行子节点的搜索可以看出b也有两个子节点c、d
然后进程又会对c进行子节点的搜索可以看出它也是有两个子节点d、e
进程又会查找d的子节点可以发现d也有两个子节点e、f
这个时候e和f都没有子节点了树的所有节点也都被遍历了

广搜遍历过程
和深搜不同广搜会沿着树的高度和宽度对节点进行依次遍历
从树的根节点a开始，会发现a的子节点有b、c两个子节点，进程会先对这两个节点进行访问然后再访问其的子节点
对b、c完成遍历之后进行则会探寻这两个节点的子节点并对其进行遍历，可以从图中看出他们未遍历的子节点有d、e
然后进程对着2个节点完成遍历之后会再次探寻其的子节点
可以看出只有一个f了且f没有子节点所以程序对f完成遍历之后整个进程也就随之结束了

  1. 深搜代码
  2. publicclass dfs {// 构造图的边privateint[][] edges ={{0,1,1,0,0,0},{1,0,1,1,0,0},{1,1,0,1,1,0},{0,1,1,0,1,1},{0,0,1,1,0,0},{0,0,0,1,0,0},};// 构造图的顶点privateString[] vertexs ={"a","b","c","d","e","f"};// 记录被访问顶点privateboolean[] verStatus;// 顶点个数privateint vertexsNum = vertexs.length;publicvoidDFSTra(){
  3.         verStatus =newboolean[vertexsNum];for(int i =0; i < vertexsNum; i++){if(verStatus[i]==false){DFS(i);}}}// 递归深搜privatevoidDFS(int i){System.out.print(vertexs[i]+" ");
  4.         verStatus[i]=true;//深度搜索子节点for(int j =firstAdjVex(i); j >=0; j =nextAdjvex(i, j)){if(!verStatus[j]){DFS(j);}}}// 返回与i相连的第一个顶点privateintfirstAdjVex(int i){for(int j =0; j < vertexsNum; j++){if(edges[i][j]>0){return j;}}return-1;}// 返回与i相连的下一个顶点privateintnextAdjvex(int i,int k){for(int j =(k +1); j < vertexsNum; j++){if(edges[i][j]==1){return j;}}return-1;}// 测试publicstaticvoidmain(String[] args){newdfs().DFSTra();}}

广搜代码

  1. importjava.util.LinkedList;importjava.util.Queue;publicclass bfs {// 构造图的边privateint[][] edges ={{0,1,1,0,0,0},{1,0,1,1,0,0},{1,1,0,1,1,0},{0,1,1,0,1,1},{0,0,1,1,0,0},{0,0,0,1,0,0},};// 构造图的顶点privateString[] vertexs ={"a","b","c","d","e","f"};// 记录被访问顶点privateboolean[] verStatus;// 顶点个数privateint vertexsNum = vertexs.length;// 广搜privatevoidBFS(){
  2.         verStatus =newboolean[vertexsNum];Queue<Integer> temp =newLinkedList<Integer>();//遍历每个节点for(int i =0; i < vertexsNum; i++){//判断当前节点是否被访问过if(!verStatus[i]){//如果没有被访问的话则将其加入队列System.out.print(vertexs[i]+" ");
  3.                 verStatus[i]=true;
  4.                 temp.offer(i);while(!temp.isEmpty()){//将最先进入队列的节点移除int j = temp.poll();//广度搜索子节点for(int k =firstAdjvex(j); k >=0; k =nextAdjvex(j, k)){if(!verStatus[k]){System.out.print(vertexs[k]+" ");
  5.                             verStatus[k]=true;
  6.                             temp.offer(k);}}}}}}// 返回与i相连的第一个顶点privateintfirstAdjvex(int i){for(int j =0; j < vertexsNum; j++){if(edges[i][j]>0){return j;}}return-1;}// 返回与i相连的下一个顶点privateintnextAdjvex(int i,int k){for(int j =(k +1); j < vertexsNum; j++){if(edges[i][j]>0){return j;}}return-1;}// 测试publicstaticvoidmain(String args[]){newbfs().BFS();}}

题目5

在这里插入图片描述
static int[][] nums = {
{ 0 , 1 , 0 , 0 , 1 ,1},
{ 1 , 0 , 1, 1 , 0 , 1},
{ 0 , 1 , 0 , 1 , 0, 0},
{ 0 , 1 , 1, 0 , 1 , 1},
{ 1 , 0 , 0 , 1 , 0 , 1},
{ 1 , 1 , 0 , 1 , 1 , 0},
};

static String res[] = { “a”, “b”, “c”, “d”, “e”, “f”};
对此二维数组进行深度搜索与广度搜索，并遍历结果。

深搜结果
a b c d e f
广搜结果
a b e f c d

深搜的遍历过程就是尽可能深的搜索树的分支，当一个节点的所有子节点都被探寻过了，搜索将回溯到发现该节点的那那条边的起始节点
这个过程会一直持续到已发现节点可到达所有节点为止。
如果还存在未发现的节点则进程会随便选择一个未发现的节点重复以上的过程
整个进程直到所有节点都被访问过为止。

深度优先搜索遍历过程
从a开始搜索可以看到a的子节点有b、e、f三个进程会依次对其进行深度优先搜索
进程先对b进行子节点的搜索可以看出b也有三个子节点c、d、f
然后进程对c进行子节点的搜索可以从图中看出c的子节点只有d，在对d进行完遍历之后
d虽然没有子节点但是它还有一个没有被遍历的父节点e所以这个时候进程会走到e
e的子节点有d、f两个但是d已经被遍历了所以现在只能遍历f了
在对f完成遍历之后整个树的节点也就全部都遍历完成了

广度优先搜索
和深搜不同广搜会沿着树的高度和宽度对节点进行依次遍历
从树的根节点a开始，会发现a的子节点有b、e、f三个子节点，进程会先对这三个节点进行访问然后再访问其的子节点
对b、e、f完成访问之后进行则会探寻这三个节点的子节点并对其进行遍历，可以从图中看出他们未遍历的子节点只有c、d了
而对c、d完成遍历之后他们也就没有子节点可以遍历了所以整个程序也就结束了

深搜代码

  1. publicclass dfs {// 构造图的边privateint[][] edges ={{0,1,0,0,1,1},{1,0,1,1,0,1},{0,1,0,1,0,0},{0,1,1,0,1,1},{1,0,0,1,0,1},{1,1,0,1,1,0},};// 构造图的顶点privateString[] vertexs ={"a","b","c","d","e","f"};// 记录被访问顶点privateboolean[] verStatus;// 顶点个数privateint vertexsNum = vertexs.length;publicvoidDFSTra(){
  2.         verStatus =newboolean[vertexsNum];for(int i =0; i < vertexsNum; i++){if(verStatus[i]==false){DFS(i);}}}// 递归深搜privatevoidDFS(int i){System.out.print(vertexs[i]+" ");
  3.         verStatus[i]=true;//深度搜索子节点for(int j =firstAdjVex(i); j >=0; j =nextAdjvex(i, j)){if(!verStatus[j]){DFS(j);}}}// 返回与i相连的第一个顶点privateintfirstAdjVex(int i){for(int j =0; j < vertexsNum; j++){if(edges[i][j]>0){return j;}}return-1;}// 返回与i相连的下一个顶点privateintnextAdjvex(int i,int k){for(int j =(k +1); j < vertexsNum; j++){if(edges[i][j]==1){return j;}}return-1;}// 测试publicstaticvoidmain(String[] args){newdfs().DFSTra();}}

广搜代码

  1. importjava.util.LinkedList;importjava.util.Queue;publicclass bfs {// 构造图的边privateint[][] edges ={{0,1,0,0,1,1},{1,0,1,1,0,1},{0,1,0,1,0,0},{0,1,1,0,1,1},{1,0,0,1,0,1},{1,1,0,1,1,0},};// 构造图的顶点privateString[] vertexs ={"a","b","c","d","e","f"};// 记录被访问顶点privateboolean[] verStatus;// 顶点个数privateint vertexsNum = vertexs.length;// 广搜privatevoidBFS(){
  2.         verStatus =newboolean[vertexsNum];Queue<Integer> temp =newLinkedList<Integer>();//遍历每个节点for(int i =0; i < vertexsNum; i++){//判断当前节点是否被访问过if(!verStatus[i]){//如果没有被访问的话则将其加入队列System.out.print(vertexs[i]+" ");
  3.                 verStatus[i]=true;
  4.                 temp.offer(i);while(!temp.isEmpty()){//将最先进入队列的节点移除int j = temp.poll();//广度搜索子节点for(int k =firstAdjvex(j); k >=0; k =nextAdjvex(j, k)){if(!verStatus[k]){System.out.print(vertexs[k]+" ");
  5.                             verStatus[k]=true;
  6.                             temp.offer(k);}}}}}}// 返回与i相连的第一个顶点privateintfirstAdjvex(int i){for(int j =0; j < vertexsNum; j++){if(edges[i][j]>0){return j;}}return-1;}// 返回与i相连的下一个顶点privateintnextAdjvex(int i,int k){for(int j =(k +1); j < vertexsNum; j++){if(edges[i][j]>0){return j;}}return-1;}// 测试publicstaticvoidmain(String args[]){newbfs().BFS();}}
标签： 深度优先 算法 数据结构
本文转载自: https://blog.csdn.net/G_GUi/article/details/126313981
版权归原作者 奋斗的小G佩奇 所有， 如有侵权，请联系我们删除。
登录后发布评论

“DFS和BFS（广度优先搜索和深度优先搜索）5个经典例子”的评论:

还没有评论
关于作者
...
overfit同步小助手
文章同步
相关阅读

网络安全法-网络运行安全

使用selenium/drissionpage时如何阻止chrome自动跳转http到https

docker desktop 里部署的Open WebUI 管理员密码忘记了的处理方法

在ubuntu20.04中搭建onsite比赛运行环境

利用开源的低代码表单设计器FcDesigner高效管理和渲染复杂表单结构

Kafka学习笔记

【前端】浏览器输入url到页面呈现发生了什么？