深度优先

1.定义

深度优先遍历算法步骤

1)访问初始结点v，并标记结点v为已访问。

2)查找结点v的第一个邻接结点w。

3)若w存在，则继续执行4，如果w不存在，则回到第1步，将从v的下一个结点继续。

4)若w未被访问，对w进行深度优先遍历递归（即把w当做另一个v，然后进行步骤123）。

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

2.个人理解

先设置第一个点为已经访问过的再看这个点与其他拿几个点连接过，并且那些点没有访问过，那么久把这个点递归dfs（递归基停止是都访问过就直接跳回上一个

3.代码讲解

首先设置为已经访问过的，在用for循环看邻接矩阵是否这两个相连并没有访问过，那么久把这个点用dfs在递归

1
2
3
4
5
6
7
8
9
10
public static void dfs(int i,int[][] arr,boolean[] visited){
       visited[i]=true;
       System.out.print(i+"->");
       for (int j = 0; j < arr.length; j++) {
           if (arr[i][j]==1&&!visited[j]){
               dfs(j,arr,visited);
           }
       }

   }

上面只是访问的所有相连的节点，万一还有断点，所以需要for循环所有节点

1
2
3
4
5
6
7
8
for (int i = 0; i < 5; i++) {
           if (!visited[i]){
               //depthfs(i,arr,visited);
               dfs(i,arr,visited);
               //brofs(i,arr,visited);
               //bfs(i,arr,visited);
           }
       }