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

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

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

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

Adjacency lists

Let's select A as the starting node.

Distance table:

Queue: A

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

Distance table:

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

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?

Consider the distance table:

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

Consider the algorithm’s basic loop:

While queue is not empty:

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(V²)

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?

For a selected vertex A let B₁, B₂, .. B_m be adjacent vertices. For all adjacent vertices, if B_k is not visited, visit B_k and all vertices reachable from B_k before proceeding with B_k+1.

General algorithm:

Procedure dfs(s)

Procedure scan(s)

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

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
    

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.