Problem: Given an unweighted undirected graph, we have to find the shortest path from the given source to the given destination using the Breadth-First Search algorithm.
The idea is to traverse the graph using Breadth-First Search Traversal until we reach the end node and print the route by tracing back the path to the start node.
How to check whether recached the end node?
Every time we visit a node, we compare it with the end node. If they match, we stop BFS.
How to stop BFS when we reach the end node?
BFS uses the queue to visit the next node, it runs until the queue is empty.
So, we can either clear the queue to stop BFS or use an explicit boolean flag such as end_reached to mark the end of BFS.
How to trace path from end to start node?
To trace the route, we use an extra node property called prev that stores the reference of the preceding node.
Every time we visit a node, we also update its prev value.
Using the prev value, we trace the route back from the end node to the starting node. Example for the given graph, route = E <- B <- A
Shortest Path in Unweighted Graph (represented using Adjacency List) using BFS
Every vertex (or node) in the graph has an adjacency list that describes the set of its neighbors.
In our program, we represent every node as a class object with the following attributes:
neighbors– Adjacency list to store neighbor nodes.name– Name of the node.visited– To mark the node has been visited.prev– For storing the reference to the preceding node.
Here is the implementation of the algorithm for the above given unweighted graph in C++, Java and Python:
Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 | #class representing node of a graph class Node: def __init__(self, name): self.name = name self.prev = None self.neighbors = [] self.visited = False #Method to connect nodes def add_neighbor(self, node): self.neighbors.append(node) node.neighbors.append(self) #Node representaion def __repr__(self): return self.name class ShortestPath: def __init__(self, start, end): self.start = start self.end = end def bfs(self): #Create queue queue = [] #Visit and add the start node to the queue self.start.visited = True queue.append(self.start) #BFS until queue is empty while queue: #Pop a node from queue for search operation current_node = queue.pop(0) #Loop through neighbors nodes to find the 'end' node for node in current_node.neighbors: if not node.visited: #visit and add neighbors nodes to the queue node.visited = True queue.append(node) #update its preceding node node.prev = current_node #stop BFS if the visited node is the end node if node == self.end: queue.clear() break; #BFS completed, now trace the route self.trace_route() #Function to trace the route using preceding nodes def trace_route(self): node = self.end route = [] #start node has no preceding node #so loop until node->prev is null while node: route.append(node) node = node.prev #reverse the route bring start to the front route.reverse() #output route print(route) if __name__ == '__main__': #create nodes node_A = Node('A') node_B = Node('B') node_C = Node('C') node_D = Node('D') node_E = Node('E') #connect nodes (i.e. create graph) node_A.add_neighbor(node_B) node_B.add_neighbor(node_C) node_C.add_neighbor(node_D) node_D.add_neighbor(node_E) node_B.add_neighbor(node_E) ShortestPath(node_A, node_E).bfs() |
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 | #include <iostream> #include <queue> #include<list> using namespace std; //class representing node of a graph class Node{ public: //Adjacency List of the vertex list<Node*> neighbors; char name; bool visited = false; Node* prev = nullptr; Node(char name){ this->name = name;} //Method to connect vertices void addNeighbour(Node* v){ this->neighbors.push_back(v); v->neighbors.push_back(this); } }; class BFS{ Node* start; Node* end; public: BFS(Node* start, Node* end){ this->start = start; this->end = end; } void findPath(){ //Create queue and declare variables queue<Node*> Queue; bool reached_end = false; //Visit start node and add to queue start->visited = true; Queue.push(start); //BFS until queue is empty while(!Queue.empty() && !reached_end){ //Pop a node from queue for search operation Node* current_node=Queue.front(); Queue.pop(); //Loop through neighbors nodes to find the 'end' node for(Node* node: current_node->neighbors){ if(!node->visited){ //Visit and add neighbor nodes to the queue node->visited= true; Queue.push(node); node->prev = current_node; //stop BFS if the end node is found if(node == end){ reached_end = true; break; } } } } trace_route(); } //Function to trace back route void trace_route(){ list<Node*> route; Node* node = end; //start.prev is always null //so loop until node->prev is null to trace route while(node != nullptr){ route.push_front(node); node = node->prev; } //Display the route for(Node* n: route){ cout << n->name <<" "; } } }; int main() { //create nodes Node node_A('A'), node_B('B'), node_C('C'), node_D('D'), node_E('E'); //connect nodes (i.e. create graph) node_A.addNeighbour(&node_B); node_B.addNeighbour(&node_C); node_C.addNeighbour(&node_C); node_D.addNeighbour(&node_D); node_B.addNeighbour(&node_E); //Driver Code BFS bfs(&node_A, &node_E); bfs.findPath(); } |
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 | import java.util.*; //Class representing graph nodes class Node{ String name; List<Node> neighbors; boolean visited = false; Node prev = null; Node(String name){ this.name = name; this.neighbors = new ArrayList<>(); } //Method to connect nodes void add_neighbor(Node node){ this.neighbors.add(node); node.neighbors.add(this); } //Node representation public String toString(){ return this.name; } } //class implmenting the algorithm class ShortestPath{ Node start, end; ShortestPath(Node start, Node end){ this.start = start; this.end = end; } public void bfs(){ //Create queue Queue<Node> queue = new LinkedList<>(); //Visit and add start node to the queue start.visited = true; queue.add(start); //BFS until queue is empty and not reached to the end node while(!queue.isEmpty()){ //pop a node from queue for search operation Node current_node = queue.poll(); //Loop through neighbors node to find the 'end' for(Node node: current_node.neighbors){ if(!node.visited){ //Visit and add the node to the queue node.visited =true; queue.add(node); //update its precedings nodes node.prev = current_node; //If reached the end node then stop BFS if(node==end){ queue.clear(); break; } } } } trace_route(); } //Function to trace the route using preceding nodes private void trace_route(){ Node node = end; List<Node> route = new ArrayList<>(); //Loop until node is null to reach start node //becasue start.prev == null while(node != null){ route.add(node); node = node.prev; } //Reverse the route - bring start to the front Collections.reverse(route); //Output the route System.out.println(route); } } //Driver Code class Main { public static void main(String[] args) { //create nodes Node node_A = new Node("A"); Node node_B = new Node("B"); Node node_C = new Node("C"); Node node_D = new Node("D"); Node node_E = new Node("E"); //connect nodes (i.e. create graph) node_A.add_neighbor(node_B); node_B.add_neighbor(node_C); node_C.add_neighbor(node_D); node_D.add_neighbor(node_E); node_B.add_neighbor(node_E); new ShortestPath(node_A, node_E).bfs(); } } |
Output:
[A, B, E]Since we are generating the route from end node to the start node, we have to reverse the route list to correct its order.
Shortest Path in Unweighted Graph (represented using Adjacency Matrix) using BFS
Adjacency Matrix is an 2D array that indicates whether the pair of nodes are adjacent or not in the graph.
Since we are representing the graph using an adjacency matrix, it will be best to also mark visited nodes and store preceding nodes using arrays.
Here are the implementations of the algorithm for the above given unweighted graph using BFS in Python, C++ and Java:
Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 | class ShortestPath: def __init__(self, start, end): self.start = start self.end = end def bfs(self): queue = [] #Visit and add the start node to the queue visited[self.start] = 1 queue.append(self.start) #BFS until queue is empty while queue: #Pop a node from queue for search operation current_node = queue.pop(0) #Loop through neighbors nodes to find the 'end' node #add unvisited neighbors to the queue while self.unvisitedNeighbor(current_node) != -1: neighbor_node = self.unvisitedNeighbor(current_node) #Visit and add neighbor nodes to the queue visited[neighbor_node] = 1; queue.append(neighbor_node); #update preceding node prev[neighbor_node] = current_node; #stop BFS if the end node is found if neighbor_node == self.end: queue.clear() break #BFS completed, now trace the route self.trace_route() #Function returns the index of unvisited neighbors def unvisitedNeighbor(self, index): for i in range(len(nodes_names)): if adjacencyM[index][i] == 1 and visited[i] == 0: return i return -1 #Function to trace the route using preceding nodes def trace_route(self): node = self.end route = [] #start node has no preceding node #so loop until node->prev is null while node != -1: route.append(nodes_names[node]) node = prev[node] #reverse the route bring start to the front route.reverse() #output route print(route) if __name__ == '__main__': #vertices or nodes nodes_names = ['A', 'B', 'C', 'D', 'E']; #Adjacency Matrix adjacencyM = [[0, 1, 0, 0, 0], [1, 0, 1, 0, 1], [0, 1, 0, 1, 1], [0, 0, 1 ,0, 1], [0, 1, 0, 1, 0]]; #List to mark visited nodes visited = [0 for x in range(len(nodes_names))] #List to stores preceding nodes prev = [-1 for x in range(len(nodes_names))] #Driver code sp = ShortestPath(0, 4) sp.bfs() |
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 | #include <iostream> #include <queue> #include<list> #define N 6 using namespace std; //vertices or nodes char nodes_name[] = {'A', 'B', 'C', 'D', 'E'}; //Adjacency Matrix int adjacencyM[N][N] = {{0, 1, 0, 0, 0}, {1, 0, 1, 0, 1}, {0, 1, 0, 1, 1}, {0, 0, 1 ,0, 1}, {0, 1, 0, 1, 0}}; class ShortestPath{ //array to store preceding nodes int prev[N] = {-1}; //array mapping to make visited vertices int visited[N] = {0}; //start and end nodes index int start, end; public: ShortestPath(int start, int end){ this->start = start; this->end = end; } void bfs(){ //Create queue queue<int> Queue; //To know whether reached, so that can stop BFS bool reached_end = false; //Visit start node and add to queue visited[start] = 1; Queue.push(start); //BFS until queue is empty while(!Queue.empty() && !reached_end){ //Pop a node from queue for search operation int current_node=Queue.front(); Queue.pop(); //Loop through neighbors nodes to find the 'end' node //add unvisited connected nodes to the queue int neighbor_node; while((neighbor_node =unvisitedNeighbor(current_node)) != -1){ //Visit and add neighbor nodes to the queue visited[neighbor_node] = 1; Queue.push(neighbor_node); //update preceding node prev[neighbor_node] = current_node; //stop BFS if the end node is found if(neighbor_node == end){ reached_end = true; break; } } } trace_route(); } //Function returns index of unvisited connected vertices int unvisitedNeighbor(int index){ for(int i=0; i<N; i++){ if(adjacencyM[index][i] == 1 && (visited[i] == 0)){ return i; } } return -1; } //Function to trace back route void trace_route(){ list<char> route; int node = end; //start node has no preceding node //so loop until prev[node] is -1 while(node != -1){ route.push_front(nodes_name[node]); node = prev[node]; } //Display the route for(char n: route){ cout << n <<" "; } } }; int main() { //Driver Code ShortestPath shortestPath(0, 4); shortestPath.bfs(); } |
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 | import java.util.*; class ShortestPath{ int adjacencyM[][]; char nodes[]; int prev[]; int visited[]; int start, end; ShortestPath(int adjacencyM[][], char[] nodes, int start, int end){ this.adjacencyM = adjacencyM; this.nodes = nodes; this.start = start; this.end = end; //array mapping to make visited vertices this.visited = new int[nodes.length]; //array to store preceding nodes this.prev = new int[nodes.length]; Arrays.fill(this.prev, -1); } public void bfs(){ //Create queue Queue<Integer> queue = new LinkedList<>(); //Visit and add start node to the queue visited[start] = 1; queue.add(start); //BFS until queue is empty while(!queue.isEmpty()){ //Pop a node from the queue for search int current_node = queue.poll(); //Loop through neighbors nodes to find the 'end' node int neighbor_node; while((neighbor_node =unvisitedNeighbor(current_node)) != -1){ //visit and add neighbors nodes to the queue visited[neighbor_node] = 1; queue.add(neighbor_node); //update its preceding node prev[neighbor_node] = current_node; //End BFS if the end node is found if(neighbor_node==end){ queue.clear(); break; } } } //BFS complete, now trace route trace_route(); } //Function returns index of unvisited neighbors private int unvisitedNeighbor(int index){ for(int i=0; i<adjacencyM.length; i++){ if(adjacencyM[index][i] == 1 && visited[i] == 0){ return i; } } return -1; } //Function to trace route using preceding nodes private void trace_route(){ int node = end; List<Character> route = new ArrayList<>(); //start node has no preceding node //so loop until prev[node] is -1 while(node!=-1){ route.add(nodes[node]); node = prev[node]; } //Reverse route to bring start at front Collections.reverse(route); //Output the route System.out.println(route); } } class Main { public static void main(String[] args) { //vertices or nodes array char nodes[] = {'A', 'B', 'C', 'D', 'E'}; //Adjacency Matrix int adjacencyM[][] = {{0, 1, 0, 0, 0}, {1, 0, 1, 0, 1}, {0, 1, 0, 1, 1}, {0, 0, 1 ,0, 1}, {0, 1, 0, 1, 0}}; //Driver Code ShortestPath shortestPath = new ShortestPath(adjacencyM, nodes, 0, 4); shortestPath.bfs(); } } |
Output:
[A, B, E]The worst-case time complexity of the discussed methods is equivalent to the time complexity of the BFS algorithm i.e. O(V+E), where V and E respectively are the numbers of vertices (nodes) and edges of the given graph.
In this tutorial, we learned to find the shortest path in an unweighted graph using the BFS algorithm with Python, C++ and Java programming languages.