Breadth-First Search (BFS)

The breadth-first search of a graph visits the vertices level by level. The first level consists of the starting vertex. Each next level consists of the vertices adjacent to the vertices in the preceding level. The breadth-first traversal of a graph is like the breadth-first traversal of a tree discussed in Tree Traversal. With breadth-first traversal of a tree, the nodes are visited level by level. First the root is visited, then all the children of the root, then the grandchildren of the root, and so on. Similarly, the breadth-first search of a graph first visits a vertex, then all its adjacent vertices, then all the vertices adjacent to those vertices, and so on. To ensure that each vertex is visited only once, it skips a vertex if it has already been visited.

Breadth-First Search Algorithm

The algorithm for the breadth-first search starting from vertex v in a graph is described in the code below.

Input: G = (V, E) and a starting vertex v
Output: a BFS tree rooted at v
1 Tree bfs(vertex v) {
2 create an empty queue for storing vertices to be visited;
3 add v into the queue;
4 mark v visited;
5
6 while (the queue is not empty) {
7 dequeue a vertex, say u, from the queue;
8 add u into a list of traversed vertices;
9 for each neighbor w of u
10 if w has not been visited {
11 add w into the queue;
12 set u as the parent for w in the tree;
13 mark w visited;
14 }
15 }
16 }

Consider the graph in Figure below (a). Suppose you start the breadth-first search from vertex 0. First visit 0, then visit all its neighbors, 1, 2, and 3, as shown in Figure below (b). Vertex 1 has three neighbors: 0, 2, and 4. Since 0 and 2 have already been visited, you will now visit just 4, as shown in Figure below (c). Vertex 2 has three neighbors, 0, 1, and 3, which have all been visited. Vertex 3 has three neighbors, 0, 2, and 4, which have all been visited. Vertex 4 has two neighbors, 1 and 3, which have all been visited. Hence, the search ends.

Since each edge and each vertex is visited only once, the time complexity of the bfs method is O(|E| + |V|), where |E| denotes the number of edges and |V| the number of vertices.

Implementation of Breadth-First Search

The bfs(int v) method is defined in the Graph interface and implemented in the AbstractGraph.java class (lines 197–222). It returns an instance of the Tree class with vertex v as the root. The method stores the vertices searched in the list searchOrder (line 198), the parent of each vertex in the array parent (line 199), uses a linked list for a queue (lines 203–204), and uses the isVisited array to indicate whether a vertex has been visited (line 207). The search starts from vertex v. v is added to the queue in line 206 and is marked as visited (line 207). The method now examines each vertex u in the queue (line 210) and adds it to searchOrder (line 211). The method adds each unvisited neighbor e.v of u to the queue (line 214), sets its parent to u (line 215), and marks it as visited (line 216).

The code below gives a test program that displays a BFS for the graph in Figure above starting from Chicago.

public class TestBFS {

    public static void main(String[] args) {
        String[] vertices = {"Seattle", "San Francisco", "Los Angeles", "Denver", "Kansas City", "Chicago", "Boston", "New York", "Atlanta", "Miami", "Dallas", "Houston"};

        int[][] edges = {
                {0, 1}, {0, 3}, {0, 5},
                {1, 0}, {1, 2}, {1, 3},
                {2, 1}, {2, 3}, {2, 4}, {2, 10},
                {3, 0}, {3, 1}, {3, 2}, {3, 4}, {3, 5},
                {4, 2}, {4, 3}, {4, 5}, {4, 7}, {4, 8}, {4, 10},
                {5, 0}, {5, 3}, {5, 4}, {5, 6}, {5, 7},
                {6, 5}, {6, 7},
                {7, 4}, {7, 5}, {7, 6}, {7, 8},
                {8, 4}, {8, 7}, {8, 9}, {8, 10}, {8, 11},
                {9, 8}, {9, 11},
                {10, 2}, {10, 4}, {10, 8}, {10, 11},
                {11, 8}, {11, 9}, {11, 10}
        };

        Graph<String> graph = new UnweightedGraph<>(vertices, edges);
        AbstractGraph<String>.Tree bfs = graph.bfs(graph.getIndex("Chicago"));

        java.util.List<Integer> searchOrders = bfs.getSearchOrder();
        System.out.println(bfs.getNumberOfVerticesFound() + " vertices are searched in this BFS order:");
        for(int i = 0; i < searchOrders.size(); i++)
            System.out.print(graph.getVertex(searchOrders.get(i)) + " ");
        System.out.println();

        for(int i = 0; i < searchOrders.size(); i++)
            if(bfs.getParent(i) != -1)
                System.out.println("parent of " + graph.getVertex(i) + " is " + graph.getVertex(bfs.getParent(i)));
    }

}

12 vertices are searched in this order:
Chicago Seattle Denver Kansas City Boston New York
San Francisco Los Angeles Atlanta Dallas Miami Houston
parent of Seattle is Chicago
parent of San Francisco is Seattle
parent of Los Angeles is Denver
parent of Denver is Chicago
parent of Kansas City is Chicago
parent of Boston is Chicago
parent of New York is Chicago
parent of Atlanta is Kansas City
parent of Miami is Atlanta
parent of Dallas is Kansas City
parent of Houston is Atlanta

Applications of the BFS

Many of the problems solved by the DFS can also be solved using the BFS. Specifically, the BFS can be used to solve the following problems:

• Detecting whether a graph is connected. A graph is connected if there is a path between any two vertices in the graph.
• Detecting whether there is a path between two vertices.
• Finding a shortest path between two vertices. You can prove that the path between the root and any node in the BFS tree is a shortest path between the root and the node.
• Finding all connected components. A connected component is a maximal connected subgraph in which every pair of vertices are connected by a path.
• Detecting whether there is a cycle in the graph.
• Finding a cycle in the graph.
• Testing whether a graph is bipartite. (A graph is bipartite if the vertices of the graph can be divided into two disjoint sets such that no edges exist between vertices in the same set.)

The above is the detailed content of Breadth-First Search (BFS). For more information, please follow other related articles on the PHP Chinese website!