Thursday, May 26, 2016
C++ OOP STL Easy Graph Representation, BFS Traversal with shortest path retracing through parent nodes
May 26, 2016
algorithm
,
beginner
,
bfs
,
c++
,
code
,
directed undirected
,
distance calculation
,
easy
,
explanation commented
,
graph
,
implementation
,
oop
,
path finding
,
self loop
,
shortest path
,
sssp
,
stl
,
tutorial
Explanation:
TODOVisual Graph Example 1:
TODOExample 1 Graph as Adjacency List:
TODOExample 1 Graph as Sample Input:
TODOVisual Graph Example 2:
TODOExample 2 Graph as Adjacency List:
TODOExample 2 Graph as Sample Input:
TODOCode:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /** | |
| * Author: Asif Ahmed | |
| * Site: http://quickgrid.blogspot.com | |
| * Description: C++ easy Graph BFS Traversal with shortest path finding for undirected graphs | |
| * and shortest path retracing thorough parent nodes. | |
| */ | |
| #include<bits/stdc++.h> | |
| using namespace std; | |
| // I have used this value as Infinite since I assume a graph | |
| // larger than this won't be tested on this code. Rather other | |
| // standard libraries should be used. | |
| #define INF 2 << 22 | |
| // Create the class for graph and define necessary properties and functions. | |
| // adjList is stores the whole adjacency list structure as shown in the books. | |
| // See my other post on graph for visual representation and other ways. | |
| // addEdge function connects an edge u with another edge v. | |
| class Graph{ | |
| private: | |
| int V; | |
| vector< list<int> > adjList; | |
| public: | |
| Graph(int const &V); | |
| void addEdge(int const &u, int const &v); | |
| void BFS(int const &s); | |
| }; | |
| // Initialize the graph with node count and scale the adjacency list with node count. | |
| Graph::Graph(int const &V){ | |
| this->V = V; | |
| adjList.resize(V); | |
| } | |
| // Go to the (u) th vector position then add v to the linked list. | |
| void Graph::addEdge(int const &u, int const &v){ | |
| adjList[u].push_back( v ); | |
| } | |
| // Find path though the graph from a given node to another. | |
| // If start and end node are same then nothing to do just print that node. | |
| // Else | |
| void findPath(int const &startNode, int const &endNode, int* &parent){ | |
| if( startNode == endNode || endNode == -1){ | |
| printf("%d\n", startNode); | |
| } | |
| else{ | |
| findPath(startNode, parent[endNode], parent); | |
| printf("%d\n", endNode); | |
| } | |
| } | |
| // Performs BFS on given node, also prints distance array and parent array. | |
| // Set distance array to infinite for all nodes and parent to -1. Set distance | |
| // of parent node to zero and push to the queue. Take it out of queue and push | |
| // all the reachable nodes from current node to queue. | |
| // Also set the distance of the current node as the distance of its parent node | |
| // plus one assuming all the distances are one instead of another same value. | |
| // Set parent of current node to the node that was taken out of queue. | |
| void Graph::BFS(int const &s){ | |
| int *dist = new int[V]; | |
| int *parent = new int[V]; | |
| for(int v = 0; v < V; ++v){ | |
| dist[v] = INF; | |
| parent[v] = -1; | |
| } | |
| dist[s] = 0; | |
| queue<int> Q; | |
| Q.push( s ); | |
| while( !Q.empty() ){ | |
| int u = Q.front(); | |
| Q.pop(); | |
| cout << u << " "; | |
| list<int>::iterator it; | |
| for(it = adjList[u].begin(); it != adjList[u].end(); ++it){ | |
| if( dist[*it] == INF ){ | |
| Q.push(*it); | |
| dist[*it] = dist[u] + 1; | |
| parent[*it] = u; | |
| } | |
| } | |
| } | |
| // Print all the reachable nodes with distance from current nodes. | |
| printf("\n"); | |
| for(int v = 0; v < V; ++v){ | |
| if(dist[v] != INF){ | |
| printf("%d -> %d: %d\n", s, v, dist[v]); | |
| }else{ | |
| printf("%d -> %d: No Path\n", s, v); | |
| } | |
| } | |
| // Print the parent array. | |
| for(int v = 0; v < V; ++v){ | |
| printf("parent of %d: %d\n", v, parent[v]); | |
| } | |
| // Try to find the shortest path from current node to another. | |
| // This can be modified based on need. Return the vector or | |
| // array from here to main in order to call function from there. | |
| int node; | |
| printf("Find shortest path from node %d to another:\n", s); | |
| cin >> node; | |
| if( dist[node] != INF ) | |
| findPath(s, node, parent); | |
| else | |
| printf("No paths available"); | |
| } | |
| int main(){ | |
| // | |
| printf("Enter node count:\n"); | |
| int n; | |
| scanf("%d", &n); | |
| // Create a graph given in the above diagram | |
| Graph *g = new Graph(n); | |
| // For inputting undirected graph either uncomment below or, | |
| // create Edges pointing from (u,v) and (v,u) | |
| int u, v; | |
| printf("Enter edges:\n"); | |
| while( scanf("%d%d", &u, &v) == 2 ){ | |
| g->addEdge(u,v); | |
| //g->addEdge(v,u); | |
| } | |
| // Run DFS on graph | |
| cout << "Breadth First Search Traversal: \n"; | |
| int node; | |
| cin >> node; | |
| g->BFS(node); | |
| return 0; | |
| } |
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment