//Author: Bishal Sarang //BFS Implementation /* Sample Input 9 11 1 2 1 3 2 4 3 4 3 7 4 5 4 6 5 7 7 8 8 9 6 9 1 */ #include #define MAX 100 using namespace std; //Adjacency list vector adj[MAX + 2]; vector path(MAX * MAX); //array to keep trackof distance int dist[MAX + 2]; //boolean array to keep trackof visited vertex bool visited[MAX + 2]; //Backtrack Path by taking destination and backtracking all the parent nodes during traversal void print_path(int u, int s) { if(u == s) { cout << u << " -> " ; return; } print_path(path[u], s); cout << u << " -> "; } void bfs(int s) { //cout << "Procedure BFS "; memset(dist, - 1, sizeof(dist)); memset(visited, false, sizeof(visited)); queue q; q.push(s); visited[s] = true; dist[s] = 0; int level = 0; cout << "level: " << dist[s] << " Vertex: " << s << "\n"; while(!q.empty()) { int v = q.front(); q.pop(); for(auto neighbours: adj[v]) { if(!visited[neighbours]) { visited[neighbours] = true; q.push(neighbours); dist[neighbours] = dist[v] + 1; path[neighbours] = v;// Store parent of nodes during bfs to build bfs tree cout << "level: " << dist[neighbours] << " Vertex: " << neighbours << "\n"; } } } } int main(){ //freopen("bfs.txt", "r", stdin); int num_of_vertex, num_of_edges; cout << "Enter num of vertex and num of edges "; cin >> num_of_vertex >> num_of_edges; int u, v; cout << "Enter edges: "; for(int i = 0; i < num_of_edges; i++) { cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } cout << "Enter Source \n"; int source; cin >> source; bfs(source); int destination; cin >> destination; cout << "\n"; cout << "Shortest Distance from " << source << " to " << destination << " is: " << dist[destination] << "\n"; //Shortest path printf("Shortest Path\n"); print_path(destination, source); return 0; }

Breadth first search