广度优先搜索(bfs)

概念

       与树的遍历类似，我们希望从图的某一顶点出发访遍图中其余节点，并且使每一个顶点仅被访问一次。这个过程就叫做图的遍历。

       由于图的连接可能存在环路，沿着边依次访问的过程可能会使得某个顶点被访问多次，所以可以使用辅助数组visited[0…n-1]记录某个顶点是否已经被访问。它的初始值可以是false,如果某个顶点i被访问过了，就将visited[i]置为true.

       广度优先遍历类似于树的层次遍历，假设从图中的某个顶点v出发，在访问了v之后依次访问v的各个未曾被访问过的邻接点，然后分别再从这些邻接点出发依次访问它们的邻接点，直到图中所有已经被访问的顶点的邻接点都被访问到。如果图中此时还有顶点未被访问到，则选择一个未被访问过的邻接点为起始点，重复上述过程，直到图中所有的邻接点都被访问。

       换句话说，广度优先搜索遍历图是以v为起始点，由近至远，依次访问和v路径相通且路径长度为1，2…的顶点。

图示

 

对于如图所示的图形，先从0开始访问，然后访问0的邻接点1和2，然后依次访问2的邻接点5和6，以及1的邻接点3和4，最后访问4的邻接点7.由于这些顶点的邻接点都已经被访问，并且图中所有的顶点都被访问。由此完成了图的遍历。

       遍历的顺序应该为0->1->2->5->6->3->4->7

       为了顺次访问路径长度为2，3…的顶点，需要用队列来记录已经被访问过的路径长度为1，2…的顶点。

算法(伪代码)

Void BFSTraverse(Graph G){

       Visited[] = new Boolean[G.size()];

       For(i = 0;I < G.size();i++)visited[i] = false;

       Init(queue);

       For(I = 0; I < G.size();i++){

              If(!visited[i]){

                     Visited[i] = true;

                     Print(i);

                     Queue.push(i);

                     while(!queue.isEmpty){

                            u = queue.poll();

                            for(int w : u的邻接点){

                                   if(!visited[w]){

                                          visited[w] = true;

                                          print(w);

                                          queue.push(w);                  

                                   }

                            }

              }

}     

代码

 

import java.util.*;

public class Solution {
    public static void main(String[] args) {
        List<Integer> l0 = new ArrayList<>();
        List<Integer> l1 = new ArrayList<>();
        List<Integer> l2 = new ArrayList<>();
        List<Integer> l3 = new ArrayList<>();
        List<Integer> l4 = new ArrayList<>();
        List<Integer> l5 = new ArrayList<>();
        List<Integer> l6 = new ArrayList<>();
        List<Integer> l7 = new ArrayList<>();
        List<List<Integer>> graph = new ArrayList<>();
        l0.add(1);
        l0.add(2);
        graph.add(l0);
        l1.add(3);
        l1.add(4);
        graph.add(l1);
        l2.add(5);
        l2.add(6);
        graph.add(l2);
        l3.add(1);
        l3.add(7);
        graph.add(l3);
        l4.add(1);
        l4.add(7);
        graph.add(l4);
        l5.add(2);
        l5.add(6);
        graph.add(l5);
        l6.add(2);
        l6.add(5);
        graph.add(l6);
        l7.add(3);
        l7.add(4);
        graph.add(l7);
        BFSTraverse(graph);
    }
    public static void BFSTraverse(List<List<Integer>> graph){
        boolean[] visited = new boolean[graph.size()];
        for(int i = 0;i < visited.length;i++)visited[i] = false;
        Queue<Integer> queue = new LinkedList<>();
        for(int i = 0;i < graph.size();i++){
            if(!visited[i]){
                visited[i] = true;
                System.out.println(i + " has been visited!");
                ((LinkedList<Integer>) queue).push(i);
                while(!queue.isEmpty()){
                    int v = queue.poll();
                    for(int w : graph.get(v)){
                        if(!visited[w]){
                            visited[w] = true;
                            System.out.println(w + " has been visited!");
                            ((LinkedList<Integer>) queue).push(w);
                        }
                    }
                }
            }
        }
    }

}

 

总结

深度优先搜索的时间复杂度为O(n+e).n为顶点个数，e为弧的个数。