Created
May 30, 2015 22:55
-
-
Save omermuneer/ea86e8e2620a0228fa28 to your computer and use it in GitHub Desktop.
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
#include<iostream> | |
#include <list> | |
using namespace std; | |
// Graph class represents a directed graph using adjacency list representation | |
class Graph | |
{ | |
int V; // No. of vertices | |
list<int> *adj; // Pointer to an array containing adjacency lists | |
void DFSUtil(int v, bool visited[]); // A function used by DFS | |
public: | |
Graph(int V); // Constructor | |
void addEdge(int v, int w); // function to add an edge to graph | |
void DFS(int v); // DFS traversal of the vertices reachable from v | |
}; | |
Graph::Graph(int V) | |
{ | |
this->V = V; | |
adj = new list<int>[V]; | |
} | |
void Graph::addEdge(int v, int w) | |
{ | |
adj[v].push_back(w); // Add w to v’s list. | |
} | |
void Graph::DFSUtil(int v, bool visited[]) | |
{ | |
// Mark the current node as visited and print it | |
visited[v] = true; | |
cout << v << " "; | |
// Recur for all the vertices adjacent to this vertex | |
list<int>::iterator i; | |
for(i = adj[v].begin(); i != adj[v].end(); ++i) | |
if(!visited[*i]) | |
DFSUtil(*i, visited); | |
} | |
// DFS traversal of the vertices reachable from v. It uses recursive DFSUtil() | |
void Graph::DFS(int v) | |
{ | |
// Mark all the vertices as not visited | |
bool *visited = new bool[V]; | |
for(int i = 0; i < V; i++) | |
visited[i] = false; | |
// Call the recursive helper function to print DFS traversal | |
DFSUtil(v, visited); | |
} | |
int main() | |
{ | |
// Create a graph given in the above diagram | |
Graph g(4); | |
g.addEdge(0, 1); | |
g.addEdge(0, 2); | |
g.addEdge(1, 2); | |
g.addEdge(2, 0); | |
g.addEdge(2, 3); | |
g.addEdge(3, 3); | |
cout << "Following is Depth First Traversal (starting from vertex 2) \n"; | |
g.DFS(2); | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment