广度优先

1.定义

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。

2.个人理解

广度优先就是遍历他的所有的子节点再遍历他的子节点的子节点，直到为空才停止（遍历市也是要威访问过的），同样万一有断点，所以需要for循环一遍

3.代码讲解

需要一个队列来进行排序，先压入所有节点标为已经访问过的，再排出一个节点，并把这个节点的子节点全部压入标记已经访问，当队列为空才停止

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static void bfs(int i,int[][] arr,boolean[] visited){
        Queue<Integer> queue=new LinkedList<>();
        System.out.print(i+"->");
        queue.add(i);
        visited[i]=true;
        while (!queue.isEmpty()){
            int v=queue.remove();
            for (int j = 0; j < arr.length; j++) {
                if (arr[v][j]==1&&!visited[j]){
                    System.out.print(j+"->");
                    visited[j]=true;
                    queue.add(j);
                }
            }
        }

    }

同样也有断点需要全部for一遍

1
2
3
4
5
6
7
8
9
10
11
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);
           }
       }


   }