Depth First Search for a Graph

Depth First Traversal (or Search) for a graph is similar to Depth First Traversal of a tree. The only catch here is, that, unlike trees, graphs may contain cycles (a node may be visited twice). To avoid processing a node more than once, use a boolean visited array. A graph can have more than one DFS traversal.

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.

Depth First Search Example (Interative, with stack)

Let’s see how the Depth First Search algorithm works with an example. We use an undirected graph with 5 vertices.

We start from vertex 0, the DFS algorithm starts by putting it in the Visited list and putting all its adjacent vertices in the stack.

Next, we visit the element at the top of stack i.e. 1 and go to its adjacent nodes. Since 0 has already been visited, we visit 2 instead.

Vertex 2 has an unvisited adjacent vertex in 4, so we add that to the top of the stack and visit it.

After we visit the last element 3, it doesn’t have any unvisited adjacent nodes, so we have completed the Depth First Traversal of the graph.

Depth First Search Example (Interative, with recursion)

DFS(G, u)
    u.visited = true
    for each v ∈ G.Adj[u]
        if v.visited == false
            DFS(G,v)
     
init() {
    For each u ∈ G
        u.visited = false
     For each u ∈ G
       DFS(G, u)
}

Code (github code)

#include <iostream>
#include <vector>
#include <list>
using namespace std;

class Graph {
    int numVertices;
    vector<list<int>> adjLists; // Vector of lists for adjacency lists
    vector<bool> visited;        // Vector to track visited vertices

public:
    // Constructor to initialize the graph
    Graph(int vertices);
    void addEdge(int src, int dest);
    void DFS(int vertex);
    void resetVisited();  // Utility function to reset visited nodes
};

// Initialize graph with given number of vertices
Graph::Graph(int vertices) : numVertices(vertices), adjLists(vertices), visited(vertices, false) {}

// Add an edge to the graph (for directed graphs)
void Graph::addEdge(int src, int dest) {
    adjLists[src].push_back(dest);
}

// Recursive DFS function
void Graph::DFS(int vertex) {
    visited[vertex] = true;
    cout << vertex << " ";

    // Visit all unvisited adjacent vertices
    for (int adjVertex : adjLists[vertex]) {
        if (!visited[adjVertex]) {
            DFS(adjVertex);
        }
    }
}

// Reset the visited array to reuse the DFS traversal
void Graph::resetVisited() {
    fill(visited.begin(), visited.end(), false);
}

// Main function to demonstrate DFS
int main() {
    Graph g(4);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 2);
    g.addEdge(2, 3);

    cout << "DFS traversal starting from vertex 2:\n";
    g.DFS(2);

    cout << "\n\nResetting visited vertices and running DFS from vertex 0:\n";
    g.resetVisited();
    g.DFS(0);

    return 0;
}