Thursday, May 26, 2016
C++ OOP STL Easy DFS Traversal with Connected Component Counting
May 26, 2016
algorithm
,
beginner
,
c++
,
code
,
connected components
,
depth first traversal
,
dfs
,
directed undirected
,
easy
,
explanation commented
,
graph
,
implementation
,
oop
,
path finding
,
self loop
,
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: Inputting and Representing unweighted graph in C++ STL vector lists. | |
| * Easy implementation of Depth first search ( DFS ) with connected | |
| * components count. | |
| */ | |
| #include<bits/stdc++.h> | |
| using namespace std; | |
| // Adjacency list representation of graph. | |
| class Graph{ | |
| private: | |
| int V; | |
| int connectedComponentsCount; | |
| vector< list<int> > adjList; | |
| void DFSVisit(int const &v, bool* &visited); | |
| public: | |
| Graph(int const &V); | |
| void addEdge(int const &u, int const &v); | |
| void DFS(); | |
| int getConnectedComponentsCount(); | |
| }; | |
| // Initialize the graph with V nodes. | |
| Graph::Graph(int const &V){ | |
| this->V = V; | |
| adjList.resize(V); | |
| } | |
| // Push node v to the list of node u. | |
| void Graph::addEdge(int const &u, int const &v){ | |
| adjList[u].push_back(v); | |
| } | |
| // Keep an array to track visited nodes. | |
| // If the node is not visited recursively visit it. | |
| void Graph::DFSVisit(int const &v, bool* &visited){ | |
| visited[v] = true; | |
| cout << v << " "; | |
| list<int>::iterator it; | |
| for( it = adjList[v].begin(); it != adjList[v].end(); ++it ){ | |
| if( !visited[*it] ){ | |
| DFSVisit(*it, visited); | |
| } | |
| } | |
| } | |
| // Fun for all nodes in the graph. | |
| // The number of unvisited nodes here are the connected components of the graph. | |
| void Graph::DFS(){ | |
| connectedComponentsCount = 0; | |
| bool* visited = new bool[V]; | |
| for(int v = 0; v < V; ++v){ | |
| visited[v] = false; | |
| } | |
| for(int v = 0; v < V; ++v){ | |
| if( !visited[v] ){ | |
| ++connectedComponentsCount; | |
| DFSVisit(v, visited); | |
| } | |
| } | |
| } | |
| // Getter method to get the connected components count. | |
| int Graph::getConnectedComponentsCount(){ | |
| return connectedComponentsCount; | |
| } | |
| 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); | |
| // Add u,v and v,u in input for undirected graph or, | |
| // uncomment the addeEdge(v,u) function call. | |
| 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 << "Depth First Search Traversal: \n"; | |
| g->DFS(); | |
| // Show connected components count | |
| cout << "\n"; | |
| cout << "Connected Components Count: "; | |
| cout << g->getConnectedComponentsCount() << "\n"; | |
| return 0; | |
| } |
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment