C++ Depth First Search (DFS)














































C++ Depth First Search (DFS)



                  Depth First Search (DFS)

Depth first Search or Depth first traversal is a recursive algorithm for searching all the vertices of a graph or tree data structure. Traversal means visiting all the nodes of a graph

Depth First Search Algorithm
A standard DFS implementation puts each vertex of the graph into one of two categories:
1.Visited
2.Not Visited
The purpose of the algorithm is to mark each vertex as visited while avoiding cycles.

The DFS algorithm works as follows:
1.Start by putting any one of the graph's vertices on top of a stack.
2.Take the top item of the stack and add it to the visited list.
3.Create a list of that vertex's adjacent nodes. Add the ones which aren't in the visited list to the top of the stack.
4.Keep repeating steps 2 and 3 until the stack is empty.

//Here goes the code
#include <iostream> #include <list> using namespace std; class Graph { int numVertices; list<int> *adjLists; bool *visited; public: Graph(int V); void addEdge(int src, int dest); void DFS(int vertex); }; Graph::Graph(int vertices) { numVertices = vertices; adjLists = new list<int>[vertices]; visited = new bool[vertices]; } void Graph::addEdge(int src, int dest) { adjLists[src].push_front(dest); } void Graph::DFS(int vertex) { visited[vertex] = true; list<int> adjList = adjLists[vertex]; cout << vertex << " "; list<int>::iterator i; for (i = adjList.begin(); i != adjList.end(); ++i) if (!visited[*i]) DFS(*i); } int main() { Graph g(4); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 2); g.addEdge(2, 3); g.addEdge(2,1); cout<<"Depth First Search from vertex 2 is :"<<endl; g.DFS(2); return 0; }

output:




Comments