Graph: DFS graph traversal

Graph: DFS graph traversal

DFS stands for Depth First Search.

In this we will traverse adjacent vertices one by one.

This is similar to Preorder traversal of a tree, only difference is that the graph may contain cycle.

To avoid processing the node multiple times, we use a visited array.

Depending upon the start vertex, traversal path will be different.

Example:

Input: adj[][] =  [[2, 3], [1, 4], [1, 4], [3, 2]]


1 --- 2
|     |
|     |
3 ----4

Solution

Start with a vertex and mark it as visited and explore the path as deeply as possible.

Then when the vertex do not have any un-visited neighbors, it will backtrace to the previous vertex and explore the un-visited path.

Then continue this step till all the vertices are reachable from the source vertex are visited.

Code

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

void dfsHelperFunction(vector<vector<int>> &adj, vector<bool> &visited, int s, vector<int> &res) 
{

    visited[s] = true;

    res.push_back(s);

    for (int i : adj[s])
        if (visited[i] == false)
            dfsHelperFunction(adj, visited, i, res);
}

vector<int> perform_dfs(vector<vector<int>> &adj) 
{
    vector<bool> visited(adj.size(), false);

    vector<int> res;
    
    dfsHelperFunction(adj, visited, 1, res);
    
    return res;
}

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

int main() 
{
    int V = 5;
    vector<vector<int>> adj(V);
    
    //adjacency list
    addAdjacencyList(adj, 1, 2);
    addAdjacencyList(adj, 1, 3);
    addAdjacencyList(adj, 2, 1);
    addAdjacencyList(adj, 2, 4);
    addAdjacencyList(adj, 3, 1);
    addAdjacencyList(adj, 3, 4);
    addAdjacencyList(adj, 4, 3);  
    addAdjacencyList(adj, 4, 2);  

    vector<int> res = perform_dfs(adj); 

    for (int i = 0; i < V-1; i++)
        cout << res[i] << " ";
}

Output:

1 2 4 3

BFS graph traversal

BFS stands for Breadth First Search.

In this we will take a node and traverse the graph level by level.

Visit all the nodes directly adjacent to the source node.

Then visit the adjacent nodes of that node and continue till all the nodes are reached.

BFS can be used to detect cycle in directed and un-directed graph, find the shortest path etc.

Example:

Input: adj[][] =  [[2, 3], [1, 4], [1, 4], [3, 2]]


1 --- 2
|     |
|     |
3 ----4

Solution

Start with a node and insert into the back of the queue.

Then take the front of the queue and add into the visited list.

Then add the unvisited node into the queue and repeat the steps.

Code

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

vector<int> perform_bfs(vector<vector<int>> &adj) 
{
    int V = adj.size();
    vector<bool> visited(V, false);
    vector<int> res;
    
    queue<int> q;
    
    int src = 1;
    visited[src] = true;
    q.push(src);

    while (!q.empty()) 
    {
        int curr = q.front();
        q.pop();
        res.push_back(curr);

        for (int x : adj[curr]) 
        {
            if (!visited[x]) 
            {
                visited[x] = true;
                q.push(x);
            }
        }
    }
    
    return res;
}

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

int main() 
{
    int V = 5;
    vector<vector<int>> adj(V);
    
    //adjacency list
    addAdjacencyList(adj, 1, 2);
    addAdjacencyList(adj, 1, 3);
    addAdjacencyList(adj, 2, 1);
    addAdjacencyList(adj, 2, 4);
    addAdjacencyList(adj, 3, 1);
    addAdjacencyList(adj, 3, 4);
    addAdjacencyList(adj, 4, 3);  
    addAdjacencyList(adj, 4, 2);  

    vector<int> res = perform_bfs(adj); 

    for (int i = 0; i < V-1; i++)
        cout << res[i] << " ";
}

Output:

1 2 3 4