Graph Traversal Algorithms

There are two standard graph traversal algorithms:

1. BFS (Breadth First Search)
2. DFS (Depth First Search)

1 BFS Graph Traversal in Data Structure

It is also known as Level Wise Algorithm.

Breadth-First Search (BFS) is a graph traversal algorithm that explores all the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level. It explores vertices in layers, starting from the initial vertex and moving level by level.

This algorithm uses a queue as a data structure as an additional data structure to store nodes for further processing. Queue size is the maximum total number of vertices in the graph

Algorithm:

1. Initialization:
   1. Start from a specific vertex (usually called the source or root).
   2. Enqueue the starting node into a queue.
   3. Mark it as visited.
2. Exploration:
   1. While the queue is not empty:
      1. Dequeue a node from the queue.
      2. Visit the node (e.g., print its value).
      3. For each unvisited neighbor of the dequeued node:
         1. Enqueue the neighbor into the queue.
         2. Mark the neighbor as visited.
3. Termination:
   1. Repeat step 2 until the queue is empty.

Example:

In the above diagram, the full way of traversing is shown using arrows.

• Step 1: Create a queue with the same size as the total number of vertices in the graph.
• Step 2: Choose 12 as your beginning point for the traversal. Visit 12 and add it to the Queue.
• Step 3: Insert all the adjacent vertices of 12 that are in front of the Queue but have not been visited into the Queue. So far, we have 5, 23, and 3.
• Step 4: Delete the vertex in front of the Queue when there are no new vertices to visit from that vertex. We now remove 12 from the list.
• Step 5: Continue steps 3 and 4 until the queue is empty.
• Step 6: When the queue is empty, generate the final spanning tree by eliminating unnecessary graph edges.

Code Implementation:

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>

using namespace std;

void bfs(vector<vector<int>>& graph, int start) {
    queue<int> q;
    unordered_set<int> visited;
    
    q.push(start);
    visited.insert(start);

    while (!q.empty()) {
        int current = q.front();
        q.pop();
        cout << current << " ";

        for (int neighbor : graph[current]) {
            if (visited.find(neighbor) == visited.end()) {
                q.push(neighbor);
                visited.insert(neighbor);
            }
        }
    }
}

int main() {
    // Example graph represented by adjacency list
    vector<vector<int>> graph = {
        {1, 2},
        {0, 3, 4},
        {0, 3},
        {1, 2, 4},
        {1, 3, 5},
        {4}
    };

    cout << "BFS Traversal: ";
    bfs(graph, 0); // Start BFS from vertex 0

    return 0;
}

#include <bits/stdc++.h>
using namespace std;

class Solution {
  public:
    // Function to return Breadth First Traversal of given graph.
    vector<int> bfsOfGraph(int V, vector<int> adj[]) {
        int vis[V] = {0}; 
        vis[0] = 1; 
        queue<int> q;
        // push the initial starting node 
        q.push(0); 
        vector<int> bfs; 
        // iterate till the queue is empty 
        while(!q.empty()) {
           // get the topmost element in the queue 
            int node = q.front(); 
            q.pop(); 
            bfs.push_back(node); 
            // traverse for all its neighbours 
            for(auto it : adj[node]) {
                // if the neighbour has previously not been visited, 
                // store in Q and mark as visited 
                if(!vis[it]) {
                    vis[it] = 1; 
                    q.push(it); 
                }
            }
        }
        return bfs; 
    }
};

void addEdge(vector <int> adj[], int u, int v) {
    adj[u].push_back(v);
    adj[v].push_back(u);
}

void printAns(vector <int> &ans) {
    for (int i = 0; i < ans.size(); i++) {
        cout << ans[i] << " ";
    }
}

int main() 
{
    vector <int> adj[6];
    
    addEdge(adj, 0, 1);
    addEdge(adj, 1, 2);
    addEdge(adj, 1, 3);
    addEdge(adj, 0, 4);

    Solution obj;
    vector <int> ans = obj.bfsOfGraph(5, adj);
    printAns(ans);

    return 0;
}

Output:

BFS Traversal: 0 1 2 3 4 5 

Complexity Analysis

Time Complexity: O( V + E)

Explanation:

• V is the number of vertices in the graph.
• E is the number of edges in the graph.

1. Initialization: O(1)
2. Queue Operations:
   1. Enqueueing each vertex: O(1) (amortized)
   2. Dequeuing each vertex: O(1) (amortized)
   3. Each vertex is enqueued and dequeued exactly once : O(V)
3. Visiting Neighbors:
   1. Visiting each neighbor of a vertex: O(1) (amortized).
   2. Each edge is visited exactly twice (once for each endpoint): O(E).

Total Time Complexity:

O(1) + O(V) + O(E) = O(V + E)

Space Complexity: O(V)

• V is the number of vertices in the graph.

2 Depth First Search

Depth-First Search (DFS) is a graph traversal algorithm that explores as far as possible along each branch before backtracking. It explores the deepest path first and then explores the shallower paths. DFS is implemented using either a stack (iterative) or recursion. Depth First Search (DFS) is a graph traversal algorithm, where we start from a selected(source) node and go into the depth of this node by recursively calling the DFS function until no children are encountered. When the dead-end is reached, this algorithm backtracks and starts visiting the other children of the current node.

The search starts on any node and explores further nodes going deeper and deeper until the specified node is found, or until a node with no children is found. If a node is found with no children, the algorithm backtracks and returns to the most recent node that has not been explored. This process continues until all the nodes have been traversed.

A stack is used as an auxiliary data structure to keep track of traversed nodes to help it backtrack when required.

Algorithm:

1. Define a Stack of size total number of vertices in the graph.
2. Select any vertex as the starting point for traversal. Visit that vertex and push it on to the Stack.
3. Visit any one of the adjacent vertices of the vertex which is at top of the stack which is not visited and push it on to the stack.
4. Repeat step 3 until there is no new vertex to visit from the vertex on top of the stack.
5. When there is no new vertex to visit then use backtracking and pop one vertex from the stack.
6. Repeat steps 3, 4 and 5 until stack becomes Empty.
7. When stack becomes Empty, then produce final spanning tree by removing unused edges from the graph

Example:

The entire path of traversal is depicted in the diagram above with arrows.

1. Step 1: Create a Stack with total number of vertices in the graph as its size.
2. Step 2: Choose 12 as your beginning point for the traversal. Go to that vertex and place it on the Stack.
3. Step 3: Push any of the adjacent vertices of the vertex at the top of the stack that has not been visited onto the stack. As a result, we push 5
4. Step 4: Repeat step 3 until there are no new vertices to visit from the stack’s top vertex.
5. Step 5: Use backtracking to pop one vertex from the stack when there is no new vertex to visit.
6. Step 6: Repeat steps 3, 4, and 5.
7. Step 7: When the stack is empty, generate the final spanning tree by eliminating unnecessary graph edges.

Code Implementation:

Recursive:

#include <iostream>
#include <vector>
#include <unordered_set>

using namespace std;

void dfs(vector<vector<int>>& graph, int vertex, unordered_set<int>& visited) {
    visited.insert(vertex);
    cout << vertex << " ";

    for (int neighbor : graph[vertex]) {
        if (visited.find(neighbor) == visited.end()) {
            dfs(graph, neighbor, visited);
        }
    }
}

int main() {
    // Example graph represented by adjacency list
    vector<vector<int>> graph = {
        {1, 2},
        {0, 3, 4},
        {0, 3},
        {1, 2, 4},
        {1, 3, 5},
        {4}
    };

    cout << "DFS Traversal: ";
    unordered_set<int> visited;
    dfs(graph, 0, visited); // Start DFS from vertex 0

    return 0;
}

Output:

DFS Traversal: 0 1 4 3 2 5 

Iterative Approach:

#include <iostream>
#include <vector>
#include <stack>
#include <unordered_set>

using namespace std;

void dfs(vector<vector<int>>& graph, int start) {
    stack<int> stk;
    unordered_set<int> visited;

    stk.push(start);
    visited.insert(start);

    while (!stk.empty()) {
        int current = stk.top();
        stk.pop();
        cout << current << " ";

        for (int neighbor : graph[current]) {
            if (visited.find(neighbor) == visited.end()) {
                stk.push(neighbor);
                visited.insert(neighbor);
            }
        }
    }
}

int main() {
    // Example graph represented by adjacency list
    vector<vector<int>> graph = {
        {1, 2},
        {0, 3, 4},
        {0, 3},
        {1, 2, 4},
        {1, 3, 5},
        {4}
    };

    cout << "DFS Traversal (Iterative): ";
    dfs(graph, 0); // Start DFS from vertex 0

    return 0;
}

Output:

DFS Traversal (Iterative): 0 2 3 4 5 1 

Complexity Analysis

Time Complexity: O(V + E)

Space Complexity: O(V)