CmSc 250 Intro to Algorithms


Elementary Graph Algorithms
Breadth-First Search and Depth-First Search in a Graph

  1. Breadth-first search: the basic algorithm
  2. Shortest Path Tree
  3. Complexity of the BFS algorithm
  4. Depth-First Search: Basic idea
  5. Implementation of DFS
  6. Relation between DFS and BFS
  7. Exercise

Exam-like questions


  1. Breadth-first search: the basic algorithm

  2. Given a graph with N vertices and a selected vertex A:

    for(i = 1; there are unvisited vertices ; i++)

    Visit all unvisited vertices at distance i
    (i is the length of the shortest path between A and currently processed vertices)

    As we saw, the algorithm for single source shortest path uses breadth-first search

    For a graph with N vertices the shortest path between two vertices can be
    at most N-1. The search is implemented by storing the neighbors in a queue.

    BFS algorithm

    1. Store source vertex S in a queue and mark as processed

    2. While queue is not empty

    Read vertex v from the queue
    For all neighbors w:

    If w is not processed
    Mark as processed
    Append in the queue
    Record the parent of w to be v
    (parent is necessary only if we need the shortest path tree)

    We can use a distance table to mark vertices as processed by storing the distance to the source vertex.

    Adjacency lists

    A: B, C, E
    B: A, C, E
    C: A, B, D
    D: C, E
    E: A, E

    Let's select A as the starting node.

    Distance table:

    Nodes

    A

    B

    C

    D

    E

    Distance to A

    0

     

     

     

     

    Parent

    0

     

     

     

     

    Queue: A

    1. After reading A from the queue and processing its neighbors:

    Distance table:

    Nodes

    A

    B

    C

    D

    E

    Distance to A

    0

    1

    1

     

    1

    Parent

    0

    A

    A

     

    A

    Queue: B, C, E

    2. Read B. Its neighbors are A, C and E. All are processed.

    Queue: C, E

    3. Read C. Its neighbors are A, B and D. A and B are processed. D is not. After processing D we have;

    Distance table

    Nodes

    A

    B

    C

    D

    E

    Distance to A

    0

    1

    1

    2

    1

    Parent

    0

    A

    A

    C

    A

    Queue: E, D

    4. Read E. Its neighbors are processed

    5. Read D. Its neighbors are processed

    The queue is empty and the algorithm ends.

    Question: Is there a more efficient way to organize the ‘while’ loop above?

  3. Shortest Path Tree

  4. Consider the distance table:

    Nodes

    A

    B

    C

    D

    E

    Distance to A

    0

    1

    1

    2

    1

    Parent

    0

    A

    A

    C

    A

    The table defines the shortest path tree, rooted at A.

  5. Complexity of the BFS algorithm

  6. Consider the algorithm’s basic loop:

    While queue is not empty:

    1. Read vertex v from the queue
    2. For all neighbors w:
    If w is not processed
    Mark w as processed
    Append w in the queue

    In step 1 we read a node from the queue. The question to be answered is: how many nodes are stored in the queue? The answer is: each node is stored only once – if it is not processed. Thus the reading step will be performed O(V) times, where V is the number of the nodes in the graph.

    In step 2 we examine all neighbors, i.e. we examine all edges of the currently read node. Since the graph is not oriented, we will examine 2*E edges, where E is the number of the edges in the graph.

    Hence the complexity of BFS is O(V + 2*E)
    If we use adjacency matrix instead of adjacency lists, the complexity will be O(V2)

    Attention: a typical error in determining the complexity is to multiply the number of the nodes by the number of the edges. Why we should not multiply the number of the edges by the number of the nodes?

  7. Depth-First Search: Basic Idea

  8. For a selected vertex A let B1, B2, .. Bm be adjacent vertices. For all adjacent vertices, if Bk is not visited, visit Bk and all vertices reachable from Bk before proceeding with Bk+1.

    General algorithm:

    Procedure dfs(s)

    mark all vertices in the graph as not reached
    invoke scan(s)

    Procedure scan(s)

    mark and visit s
    for each neighbor w of s
    if the neighbor is not reached
    invoke scan(w)

  9. Implementation of DFS

  10. DFS builds a DFS tree T which shows how the vertices are visited.
    The initialization step consists in marking all vertices as unvisited and selecting a start vertex.

    • Recursive implementation of depth-first search:
    • DepthFirst(Vertex v) { visit(v) for each neighbor w of v if (w is not visited) add edge (v,w) to tree T DepthFirst(w) } Visit(v) { mark v as visited }

    • Non-recursive implementation
    • The non-recursive implementation uses a stack

      Initialization: mark all vertices as unvisited, visit(s) while the stack is not empty: { pop (v,w) if w is not visited add (v,w) to tree T visit(w) } visit(v) { mark v as visited for each edge (v,w) push (v,w) in the stack }

    Example:

    1. Trace the non-recursive algorithm with start vertex A
    2. Trace the recursive algorithm with start vertex A

  11. Relation between DFS and BFS

  12. BFS and DFS are very closely related to each other. The difference is that BFS uses a queue while DFS uses a stack. Queues can be described as lists where we write at the end and read from the beginning. Stacks can be described as lists where we write at the end and read from the end. Thus we can describe BFS and DFS in the following way:

    bfs(G)
        list L = empty
        tree T = empty
        choose a starting vertex x
        visit(x)
        while(L nonempty)
            remove edge (v,w) from beginning of L
            if w not visited
               add (v,w) to T
               visit(w)
                
    
    dfs(G)
        list L = empty
        tree T = empty
        choose a starting vertex x
        visit(x)
        while(L nonempty)
            remove edge (v,w) from end of L
            if w not visited
               add (v,w) to T
               visit(w)
                
    
    visit(vertex v)
        mark v as visited
        for each edge (v,w)
            add edge (v,w) to end of L
        
    

  13. Exercise

    1. Construct a graph for the following maze:
    2. Which traversal – DFS or BFS would you use if you found yourself in a maze and why?

    3. Find a route through the maze.


Exam-like questions

  1. Given a graph and a node in the graph, build the shortest path tree.
  2. Explain the complexity of BFS algorithm
  3. Outline the solution of the following problems (give the pseudocode of the solution)
    1. Represent a tree given by its edges.
    2. Determine the root of a tree represented by its edges.
    3. Determine the leaves of a tree represented by its edges
    4. For a given node, print the path from the root to that node
    5. Determine the height of a node
    6. Determine the depth of a node
    7. Determine the longest path in the tree
    8. Determine the height of the root
    9. Determine whether the graph is connected
  4. Given a graph and a vertex, write down the order of visiting the vertices in a depth-first manner.
  5. Give the recursive algorithm for depth-first search in a graph
  6. Give the non-recursive algorithm for depth-first search in a graph

Back to Contents page
Created by Lydia Sinapova