Breadth-First Search

Definition

Breadth-first search (BFS) is a general technique for traversing a graph
A BFS traversal of a graph G
- Visits all the vertices and edges of G
- Determines whether G is connected
- Computes the connected components of G
- Computes a spanning forest of G
BFS on a graph with n vertices and m edges takes O(n + m ) time
BFS can be further extended to solve other graph problems
- Find and report a path with the minimum number of edges between two given vertices
- Find a simple cycle, if there is one
Application: Using the template method pattern, we can specialize the BFS traversal of a graph G to solve the following problems in O(n + m) time:
- Compute the connected components of G
- Compute a spanning forest of G
- Find a simple cycle in G, or report that G is a forest
- Given two vertices of G, find a path in G between them with the minimum number of edges, or report that no such path exists

BFS Algorithm

The algorithm uses a mechanism for setting and getting “labels” of vertices and edges

Algorithm BFS(G)
  Input graph G
  Output labeling of the edges and partition of the vertices of G
  for all u ∈ G.vertices()
    setLabel(u, UNEXPLORED)
  for all e ∈ G.edges()
    setLabel(e, UNEXPLORED)
  for all v ∈ G.vertices()
    if getLabel(v) = UNEXPLORED
      BFS(G, v)

Algorithm BFS(G, s)
  L0 ← new empty sequence
  L0.insertLast(s)
  setLabel(s, VISITED)
  i ← 0
  while ¬Li.isEmpty()
    Li +1 ← new empty sequence
    for all v ∈ Li.elements()
      for all e ∈ G.incidentEdges(v)
        if getLabel(e) = UNEXPLORED
          w ← opposite(v,e)
        if getLabel(w) = UNEXPLORED
          setLabel(e, DISCOVERY)
          setLabel(w, VISITED)
          Li +1.insertLast(w)
        else
          setLabel(e, CROSS)
    i ← i +1

BFS_Example

Properties

Notation
- G_s: connected component of s
Property 1
- BFS(G, s) visits all the vertices and edges of G_s
Property 2
- The discovery edges labeled by BFS(G, s) form a spanning tree T_s of G_s
Property 3
For each vertex v in L_i
- The path of T_s from s to v has i edges
- Every path from s to v in G_s has at least i edge

BFS_Properties

Analysis

Setting/getting a vertex/edge label takes O(1) time
Each vertex is labeled twice
- once as UNEXPLORED
- once as VISITED
Each edge is labeled twice
- once as UNEXPLORED
- once as DISCOVERY or CROSS
Each vertex is inserted once into a sequence L_i
Method incidentEdges is called once for each vertex
BFS runs in O(n + m) time provided the graph is represented by the adjacency list structure
- Recall that Σ_v deg(v) = 2m

DFS vs. BFS

BFS_vs_DFS

DFS Back edge (v,w)
- w is an ancestor of v in the tree of discovery edges
BFS Back edge (v,w)
- w is in the same level as v or in the next level in the tree of discovery edges

BFS_vs_DFS

Code

package examples;
import graphLib.*;
import graphTool.Algorithm;
import graphTool.Attribute;
import graphTool.GraphTool;

import java.awt.Color;
import java.io.Serializable;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Random;


public class GraphExamples<V,E> {
    /**
     * visits all vertices starting with 'v'
     * using a breadth first search
     *
     * @param v
     */
    @Algorithm(vertex=true)
    public void visitBFS(Graph<V,E> g, Vertex<V> v, GraphTool<V,E> t) {
        LinkedList<Vertex<V>> list = new LinkedList<>();
        v.set(Attribute.color,Color.BLUE);
        v.set(Attribute.VISITED,null);
        list.addLast(v);
        t.show(g);
        while (! list.isEmpty()){        
            Vertex w = list.removeFirst();
            Iterator<Edge<E>> it = g.incidentEdges(w);
            while (it.hasNext()){
                Edge e = it.next();
                Vertex n = g.opposite(e, w);
                if ( ! n.has(Attribute.VISITED)){
                    e.set(Attribute.color,Color.GREEN);
                    n.set(Attribute.color,Color.GREEN);
                    n.set(Attribute.VISITED,null);
                    n.set(Attribute.DISCOVERY,e);    // for path finding!
                    n.set(v,e); // set the gatway-edge wich leads to 'v'
                    list.addLast(n);
                    t.show(g);
                }
            }
        }
    }


    /**
     * @param args
     *
     */
    public static void main(String[] args) {

        //         make an undirected graph
        IncidenceListGraph<String,String> g =
                new IncidenceListGraph<>(true);
        GraphExamples<String,String> ge = new GraphExamples<>();
        Vertex vA = g.insertVertex("A");
        vA.set(Attribute.name,"A");
        Vertex vB = g.insertVertex("B");
        vB.set(Attribute.name,"B");
        Vertex vC = g.insertVertex("C");
        vC.set(Attribute.name,"C");
        Vertex vD = g.insertVertex("D");
        vD.set(Attribute.name,"D");
        Vertex vE = g.insertVertex("E");
        vE.set(Attribute.name,"E");
        Vertex vF = g.insertVertex("F");
        vF.set(Attribute.name,"F");
        Vertex vG = g.insertVertex("G");
        vG.set(Attribute.name,"G");

        Edge e_a = g.insertEdge(vA,vB,"AB");
        Edge e_b = g.insertEdge(vD,vC,"DC");
        Edge e_c = g.insertEdge(vD,vB,"DB");
        Edge e_d = g.insertEdge(vC,vB,"CB");
        Edge e_e = g.insertEdge(vC,vE,"CE");
        e_e.set(Attribute.weight,2.0);
        Edge e_f = g.insertEdge(vB,vE,"BE");
        e_f.set(Attribute.weight, 7.0);
        Edge e_g = g.insertEdge(vD,vE,"DE");
        Edge e_h = g.insertEdge(vE,vG,"EG");
        e_h.set(Attribute.weight,3.0);
        Edge e_i = g.insertEdge(vG,vF,"GF");
        Edge e_j = g.insertEdge(vF,vE,"FE");
        GraphTool t = new GraphTool(g,ge);

        //    A__B     F
        //      /|\   /|
        //     / | \ / |
        //    C__D__E__G   
        //    \     /
        //     \___/
        //   
    }
}