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
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