Group 2
Exercise 2
Write pseudocodes and find time complexity of BFS algorithm to find shortest path from a
source to end node.
1 2
0 3
5 4
Breadth First Search (BFS) Pseudocodes and Time Complexity:
Pseudocodes:
BFS (G, s) //Where G is the graph and s is the source node
let Q be queue
Q.enqueue(s) //Inserting s in queue until all its neighbour vertices are marked.
mark s as visited
while (Q is not empty)
//Removing that vertex from queue,whose neighbour will be visited now
v = Q.dequeue()
//processing all the neighbours of v
for all neighbours w of v in Graph G
if w is not visited
Q.enqueue(w) //Stores w in Q to further visit its neighbour
mark w as visited
1 2
E = Edge
0 3 V = Vertex
5 4
Time Complexity:
V = Vertices
E = Edges
where V is number of vertices in the graph and E is number of edges in the graph.
BFS Time Complexity: O(V+E)
1
Group 2
Shortest path from a source to end node:
Step 1: Step 2:
1 2 1 2
0 3 0 3
5 4 5 4
0 1 2 3 4 5 0 1 2 3 4 5
Visited: 0 0 0 0 0 0 Visited: 1 0 0 0 0 0
Queue: Queue: 0
BFS: BFS:
Step 3: Step 4:
1 2 1 2
0 3 0 3
5 4 5 4
0 1 2 3 4 5 0 1 2 3 4 5
Visited: 1 1 1 0 0 0 Visited: 1 1 1 1 0 0
Queue: 2 1 Queue: 1 3
BFS: 0 BFS: 0 2
Step 5: Step 6:
1 2 1 2
0 3 0 3
5 4 5 4
0 1 2 3 4 5 0 1 2 3 4 5
Visited: 1 1 1 1 1 0 Visited: 1 1 1 1 1 0
Queue: 3 4 Queue: 4
BFS: 0 2 1 BFS: 0 2 1 3
2
Group 2
Step 7: Step 8:
1 2 1 2
0 3 0 3
5 4 5 4
0 1 2 3 4 5 0 1 2 3 4 5
Visited: 1 1 1 1 1 1 Visited: 1 1 1 1 1 1
Queue: 5 Queue:
BFS: 0 2 1 3 4 BFS: 0 2 1 3 4 5
Result Short BFS: 0 2 1 3 4 5
