Depth First Search for Graph in C++.

Depth First Search (DFS) is a graph traversal algorithm that explores a graph by visiting as far as possible along each branch before backtracking. It starts from a given source vertex and recursively explores all of its neighbors, marking each vertex as visited as it traverses the graph. Once it reaches the end of a branch, it backtracks to the last unexplored vertex and continues the search.

Algorithm for Depth First Search.

• Step 1: Create a visited array and initialize it to false.
• Step 2: Initialize a stack and push the source vertex onto it.
• Step 3: While the stack is not empty, do the following:
• a. Pop a vertex from the stack.
• b. If the vertex has not been visited, mark it as visited and do the following:
• i. Process the vertex (e.g., print its value).
• ii. Get its neighbors and push them onto the stack.
• Step 4: Repeat step 3 until the stack is empty.

Example with Illustration.

Step 1

We have one stack to traverse all vertices and a visited array to mark visited vertices. Push the starting vertex 0 in the stack as the initial condition. 

Step 2

Pop the top element of the stack that is 0 and mark that index as visited in the visited array and print it. Push all other neighbor vertices of 0 inside the stack if already not visited.

Step 3

Pop the top element of the stack that is 2 and mark that index as visited in the visited array and print it. Push all other neighbor vertices of 2 inside the stack if already not visited.

Step 4

Pop the top element of the stack that is 3 and mark that index as visited in the visited array and print it. Push all other neighbor vertices of 3 inside the stack if already not visited.

Step 5

Pop the top element of the stack that is 1 and mark that index as visited in the visited array and print it. Push all other neighbor vertices of 3 inside the stack if already not visited. Here the stack becomes empty which means traversal is complete.

C++ code for DFS (Depth First Search) Traversal using Stack.

//C++ code implementation for DFS Traversal of graph using Stack
#include <iostream>
#include <vector>
#include <stack>
using namespace std;

//function for dfs
void DFS(int V, vector<int> graph[], int start, vector<bool>& visited) {
    stack<int> s;
    s.push(start);

    while (!s.empty()) {
        int v = s.top();
        s.pop();

        if (!visited[v]) {
            visited[v] = true;
            cout << v << " ";

            for (int u : graph[v]) {
                s.push(u);
            }
        }
    }
}

int main() {
    int V = 4;
    vector<int> graph[V];
    graph[0] = {1, 2};
    graph[1] = {0, 2, 3};
    graph[2] = {0, 1, 3};
    graph[3] = {1, 2};

    vector<bool> visited(V, false);
    DFS(V, graph, 0, visited);
    return 0;
}

Output:

0 2 3 1

• Time Complexity: O(V + E) where V is the number of vertices and E is the number of Edges. Each vertex and each edge is explored exactly once.
• Space Complexity: O(V + E) as it uses a stack to keep track of vertices and an array to mark visited vertices. In the worst case, the stack will store all vertices of the longest path, which is the maximum the maximum depth of the recursion.

Algorithm for Depth First Search (Recursive).

• Step 1: Create a visited array and initialize it to false.
• Step 2: Call the DFS function with the starting vertex as the argument.
• Step 3: In the DFS function, mark the current vertex as visited and process it (e.g., print its value).
• Step 4: For each unvisited neighbor of the current vertex, recursively call the DFS function with the neighbor as the argument.

C++ code for DFS (Depth First Search) Traversal using Recursion:

//C++ code implementation for DFS Traversal of graph using Recursion
#include <iostream>
#include <vector>
#include <stack>
using namespace std;

//function for dfs
void DFS(int V, vector<int> graph[], int start, vector<bool>& visited) {
    visited[start] = true;
    cout << start << " ";

    for (int u : graph[start]) {
        if (!visited[u]) {
            DFS(V, graph, u, visited);
        }
    }
}

int main() {
    int V = 4;
    vector<int> graph[V];
    graph[0] = {1, 2};
    graph[1] = {0, 2, 3};
    graph[2] = {0, 1, 3};
    graph[3] = {1, 2};

    vector<bool> visited(V, false);
    DFS(V, graph, 0, visited);
    return 0;
}

Output:

0 1 2 3

• Time Complexity: O(V + E) where V is the number of vertices and E is the number of Edges.
• Space Complexity: O(V) as an array to mark visited vertices. The maximum depth of the recursion is the number of vertices.

(getButton) #text=(Breadth First Search for Graph) #icon=(link) #color=(#2339bd)

Breadth First Search (BFS) for Graph in C++

Breadth First Search (BFS) is a graph traversal algorithm that visits all the vertices of a graph in breadth-first order, meaning that it visits all the vertices at the same level before moving on to the next level. The algorithm uses a queue data structure to keep track of the vertices that need to be visited.

How BFS for Graph is different from BFS for Tree Data structure?

The main difference between the graph and the tree BFS traversal is that a tree cannot contain cycles but a graph can contain cycles. To avoid visiting the same vertex again and again we use a boolean visited array to mark the visited vertices.

If we don't mark the visited vertices, the algorithm may revisit vertices that have already been explored and get stuck in an infinite loop. This is especially true in the case of cycles, where a BFS traversal without marking visited vertices could result in an infinite loop.

Algorithm of Breadth First Search:

• Step 1: Create a queue data structure and add the starting vertex to the queue.
• Step 2: While the queue is not empty:
• Step 3: Dequeue the vertex at the front of the queue and mark it as visited.
• Step 4: Visit all the unvisited neighbors of the dequeued vertex and add them to the queue.
• Step 5: If all the vertices have been visited, the algorithm is complete.

Example with Illustration.

Step 1

The BFS traversal order of the above graph is starting from vertex 0 so we push the vertex 0 inside the queue and mark that index as visited.

 

Step 2

Pop the front element 0 from the queue and print it. Push the adjacent vertices 1 and 2 inside the queue and then mark them as visited.

Step 3

Pop the front element 1 from the queue and print it. Push the adjacent vertices 2 and 3 inside the queue but 2 is already visited so push only 3 and then mark them as visited.

Step 4

Pop the front element 2 from the queue and print it. Push the adjacent vertices 3 inside the queue but 3 is already visited so nothing to push.

Step 5

Pop the front element 3 from the queue and print it. Push the adjacent vertices if any and mark them as visited. We can observe that we have visited all the vertices of the given graph. Stop the process once the queue is empty.

C++ Code for BFS Traversal Using Queue.

Here is an example of BFS implementation in C++ for an undirected graph represented as an adjacency list:

//C++ Code for BFS Traversal of Undirected Graph
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

//breadth first search of traversal
void bfs(int V, vector<int> adj_list[], int start) {
    vector<bool> visited(V, false);
    queue<int> q;
    visited[start] = true;
    q.push(start);
    while (!q.empty()) {
        int current_vertex = q.front();
        q.pop();
        cout << current_vertex << " ";
        for (auto neighbor : adj_list[current_vertex]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                q.push(neighbor);
            }
        }
    }
}

int main() {
    int V = 4;
    vector<int> adj_list[V];
    adj_list[0] = {1, 2};
    adj_list[1] = {0, 2, 3};
    adj_list[2] = {0, 1, 3};
    adj_list[3] = {1, 2};

    bfs(V, adj_list, 0);

    return 0;
}

Output:

0 1 2 3

• Time Complexity: O(V + E) where V is the number of vertices and E is the number of edges.

• Space Complexity: O(V) where one visited array of size V is used to mark visited vertices and one queue to store adjacent vertices while traversing.

BFS Traversal for Disconnected Graph.

The above code for BFS Traversal will not work if the given graph is disconnected. To understand this concept we first have to understand what is disconnected graph.

Disconnected Graph.

A disconnected graph is a graph in which there is no path between at least two vertices. In other words, a disconnected graph can be split into two or more connected components, where each component contains a group of vertices that are connected to each other but not connected to the vertices in other components.

Example: 

Disconnected Graph

We can traverse the disconnected graph by modifying the above BFS code. Below is the C++ code implementation for the BFS traversal of the disconnected graph.

//C++ Code for BFS Traversal of disconnected graph
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

//breadth first search of traversal
void bfs(int V, vector<int> adj_list[], int start, vector<bool> &visited) {
    
    queue<int> q;
    visited[start] = true;
    q.push(start);
    while (!q.empty()) {
        int current_vertex = q.front();
        q.pop();
        cout << current_vertex << " ";
        for (auto neighbor : adj_list[current_vertex]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                q.push(neighbor);
            }
        }
    }
}

int main() {
    int V = 7;
    vector<int> adj_list[V];
    adj_list[0] = {1, 2};
    adj_list[1] = {0, 2, 3};
    adj_list[2] = {0, 1, 3};
    adj_list[3] = {1, 2};
    adj_list[4] = {5, 6};
    adj_list[5] = {4};
    adj_list[6] = {4};

    vector<bool> visited(V, false);
    //for disconnected graph
    for(int i = 0; i < V; i++){
        if(!visited[i]){
            bfs(V, adj_list, i, visited);
        }
    }

    return 0;
}

Output:

0 1 2 3 4 5 6

• Time Complexity: O(V + E) where V is the number of vertices and E is the number of edges.

• Space Complexity: O(V) because we are using a visited array of size V and a queue data structure to store adjacent vertices and it is taken at max V size.

(getButton) #text=(Depth First Search for Graph) #icon=(link) #color=(#2339bd)

Adjacency List Implementation in C++.

In the previous posts, we covered the basics of graph data structure and how we use an adjacency matrix for its representation. Here we are going to learn how to represent graph data structure using Adjacency List.

Adjacency List.

An adjacency list is a way of representing a graph as an array of linked lists, where each vertex has a linked list of its adjacent vertices. In this representation, we create an array of sizes V (V is the number of vertices). Each index of the array will carry a different list which will contain the list of vertices connected to that particular index.

Adjacency List for an Undirected Graph.

In an undirected graph, each edge is bidirectional, meaning that if there's an edge from vertex u to vertex v, there's also an edge from v to u. Therefore, in the adjacency list representation of an undirected graph, we add both u to the adjacency list of v and v to the adjacency list of u.

Example: 

Adjacency List for Undirected Graph

C++ code Implementation of Adjacency List for the above-undirected graph:

//C++ Code for Printing Adjacency List of Undirected Graph
#include <iostream>
#include <vector>
using namespace std;

//Add edges to undirected graph
void addEdge(vector<int> adj[], int u, int v) {
    adj[u].push_back(v);
    adj[v].push_back(u);
}

//printing the adjacency list
void printGraph(vector<int> adj[], int V) {
    for (int v = 0; v < V; ++v) {
        cout << "Adjacency list of vertex " << v << "->";
        for (auto u : adj[v])
            cout << u << " ";
        cout << endl;
    }
}

int main() {
    int V = 4;
    vector<int> adj[V];
    addEdge(adj, 0, 1);
    addEdge(adj, 0, 2);
    addEdge(adj, 1, 2);
    addEdge(adj, 1, 3);
    addEdge(adj, 2, 3);
    printGraph(adj, V);
    return 0;
}

Output:

Adjacency list of vertex 0->1 2
Adjacency list of vertex 1->0 2 3
Adjacency list of vertex 2->0 1 3
Adjacency list of vertex 3->1 2

Adjacency List for a Directed Graph.

In a directed graph, each edge is unidirectional, meaning that there's an edge from vertex u to vertex v, but not necessarily from v to u. Therefore, in the adjacency list representation of a directed graph, we only add v to the adjacency list of u.

Example:

Adjacency List for Directed Graph

C++ code Implementation of Adjacency List for the above-directed graph:

//C++ Code for Printing Adjacency List of Directed Graph
#include <iostream>
#include <vector>
using namespace std;

//Add edges to directed graph
void addEdge(vector<int> adj[], int u, int v) {
    adj[u].push_back(v);
}

//printing the adjacency list
void printGraph(vector<int> adj[], int V) {
    for (int v = 0; v < V; ++v) {
        cout << "Adjacency list of vertex " << v << "->";
        for (auto u : adj[v])
            cout << u << " ";
        cout << endl;
    }
}

int main() {
    int V = 4;
    vector<int> adj[V];
    addEdge(adj, 0, 1);
    addEdge(adj, 0, 2);
    addEdge(adj, 1, 2);
    addEdge(adj, 2, 3);
    addEdge(adj, 3, 1);
    printGraph(adj, V);
    return 0;
}

Output:

Adjacency list of vertex 0->1 2
Adjacency list of vertex 1->2
Adjacency list of vertex 2->3
Adjacency list of vertex 3->1

The Adjacency list is an efficient way to represent the graph when the graph is less dense but when the graph is dense we use the Adjacency matrix to represent a graph.

Adjacency Matrix Implementation in C++

We have covered Graph data structure in our previous post and in there, we have learned that graphs can be represented in two different ways, one is Adjacency Matrix and another is Adjacency List. In this post, we are going to learn about the Adjacency Matrix and its implementation for different types of graphs.

Adjacency Matrix.

An adjacency matrix is a way of representing a graph as a matrix of size n x n filled with 0s and 1s, where n is the number of vertices in the graph. The entry in the ith row and jth column of the matrix indicates whether there is an edge from vertex i to vertex j. 

Adjacency Matrix implementation is different for directed and undirected graphs. Let's learn the implementation one by one.

Adjacency Matrix for Undirected Graph.

For a simple undirected graph, the matrix is symmetric around its diagonal, since the edges are bidirectional. It means if there is an edge between vertex A to vertex B then there must be an edge from vertex B to vertex A. 

Note: The diagonal entries in the matrix are always 0 in an undirected graph since there are no self-loops. Also, the matrix is symmetric about its diagonal, so the entry in row i and column j is the same as the entry in row j and column i. (alert-passed)

Example:

Adjacency Matrix for Undirected Graph

Below is the C++ code implementation for the Adjacency matrix of an undirected graph.

//C++ code for printing adjacency matrix of undirected graph
#include <iostream>
using namespace std;

const int MAX_SIZE = 100;
int adj_matrix[MAX_SIZE][MAX_SIZE];

int main() {
    // n: number of vertices, m: number of edges
    int n, m;
    cout<<"Enter number of vertices: ";
    cin >> n;
    cout<<"Enter number of edges: ";
    cin >> m;
    
    // initialize adjacency matrix
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            adj_matrix[i][j] = 0;
        }
    }
    
    cout<< "Add edges to the graph:\n";
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        // since the graph is undirected
        adj_matrix[u][v] = 1;
        adj_matrix[v][u] = 1;
    }
    
    // print adjacency matrix
    cout << "Adjacency matrix:\n";
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cout << adj_matrix[i][j] << " ";
        }
        cout << "\n";
    }
    
    return 0;
}

Output:

Enter number of vertices: 4
Enter number of edges: 5
Add edges to the graph:
0 1
0 2
1 2
1 3
2 3
Adjacency matrix:
0 1 1 0
1 0 1 1
1 1 0 1
0 1 1 0

Adjacency Matrix for Directed Graph.

For a directed graph, the matrix is not necessarily symmetric, since the edges are not bidirectional. 

Example:

Adjacency Matrix for Directed Graph

Below is the C++ code implementation for the Adjacency matrix of a directed graph.

//C++ code for printing adjacency matrix of directed graph
#include <iostream>
using namespace std;

const int MAX_SIZE = 100;
int adj_matrix[MAX_SIZE][MAX_SIZE];

int main() {
    // n: number of vertices, m: number of edges
    int n, m;
    cout<<"Enter number of vertices: ";
    cin >> n;
    cout<<"Enter number of edges: ";
    cin >> m;
    
    // initialize adjacency matrix
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            adj_matrix[i][j] = 0;
        }
    }
    
    cout<< "Add edges to the graph:\n";
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        // since the graph is directed
        adj_matrix[u][v] = 1;
    }
    
    // print adjacency matrix
    cout << "Adjacency matrix:\n";
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cout << adj_matrix[i][j] << " ";
        }
        cout << "\n";
    }
    
    return 0;
}

Output:

Enter number of vertices: 4
Enter number of edges: 5
Add edges to the graph:
0 1
0 2
1 2
2 3
3 1
Adjacency matrix:
0 1 1 0
0 0 1 0
0 0 0 1
0 1 0 0

Adjacency Matrix is a simple and efficient way to represent a dense graph but we have another method of representation like the Adjacency list when the graph is not dense.