What is Implementation of Graph in C++?

In this article, we will learn Implementation of Graph in C++,This free C++ tutorial for complete beginners will help you learn C++ from scratch.

Implementation of Graph in C++

Observations on graph

In C++, graphs are non-linear data structures that are used to represent the relationships between various objects. A graph is defined as a collection of vertices and edges. In this article, we will learn how to implement the graph data structure in C++.

Implementation of Graph Data Structure in C++

There are two primary ways to implement or represent graph data structures in C++:

Using Adjacency Matrix
Using Adjacency List

Let us consider the following undirected graph:

Adjacency Matrix Representation of Graph in C++

An adjacency matrix is a square matrix (2D vector in C++) used to represent a finite graph. It provides a straightforward way to describe the relationships between nodes (vertices) in a graph.

Rules to Create Adjacency Matrix of a Graph

Create an n x n 2d vector named matrix, where n is the number of vertices, with all entries initialized to 0.
For an undirected graph, set both matrix[i][j] and matrix[j][i] to 1 if there is an edge between vertices i and j.
For a directed graph, set matrix[i][j] to 1 if there is an edge from vertex i to vertex j.
For a weighted graph, set matrix[i][j] to the weight of the edge between vertices i and j.
If there is a self-loop on vertex i, set matrix[i][i] to 1 (or the weight if weighted).

From the above rules, we can create the adjacency matrix:

C++ Program to Implement a Graph Using Adjacency Matrix

The following program illustrates how we can implement a graph using an adjacency matrix in C++:

C++

// C++ Program to Implement a Graph Using Adjacency Matrix
#include <iostream>
#include <vector>
using namespace std;

class Graph {
    // Adjacency matrix to store graph edges
    vector<vector<int> > adj_matrix;

public:
    // Constructor to initialize the graph with 'n' vertices
    Graph(int n)
    {
        adj_matrix
            = vector<vector<int> >(n, vector<int>(n, 0));
    }

    // Function to add an edge between vertices 'u' and 'v'
    // of the graph
    void add_edge(int u, int v)
    {
        // Set edge from u to v
        adj_matrix[u][v] = 1;
        // Set edge from v to u (for undirected graph)
        adj_matrix[v][u] = 1;
    }

    // Function to print the adjacency matrix representation
    // of the graph
    void print()
    {
        // Get the number of vertices
        cout << "Adjacency Matrix for the Graph: " << endl;
        int n = adj_matrix.size();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cout << adj_matrix[i][j] << " ";
            }
            cout << endl;
        }
    }
};

int main()
{
    // Number of vertices
    int n = 4;
    // Create a graph with 4 vertices
    Graph g(n);

    // Adding the specified edges in the graph
    g.add_edge(0, 1);
    g.add_edge(0, 2);
    g.add_edge(1, 3);
    g.add_edge(2, 3);

    // Print the adjacency matrix representation of the
    // graph
    g.print();
    return 0;
}

Output

Adjacency Matrix for the Graph: 
0 1 1 0 
1 0 0 1 
1 0 0 1 
0 1 1 0

Time Complexity: O(V^2), where V is the number of vertices in the graph.
Auxiliary Space: O(V^2)

Adjacency List Representation of Graph in C++

An Adjacency List is a common way to represent a graph in computer science. Specifically, it’s a way of representing a graph as a map from vertices to lists of edges. The adjacency list representation of a graph is linked to the degree of the vertices, and hence is quite space efficient. It only uses space proportional to the number of edges, which can be much less than the square of the number of vertices (which is the space complexity of the adjacency matrix representation).

Rules to Create Adjacency List of a Graph

Create a list of n elements, where n is the number of vertices.
For an undirected graph, add vertex j to the list of vertex i and add vertex i to the list of vertex j if there is an edge between i and j.
For a directed graph, add vertex j to the list of vertex i if there is an edge from vertex i to vertex j.
For a weighted graph, add a tuple (j, weight) to the list of vertex i to represent an edge from i to j with the given weight.
If there is a self-loop on vertex i, add i to the list of vertex i (or (i, weight) if weighted).

Following these rules, we can create the adjacency list:

C++ Program to Implement a Graph Using Adjacency List

Approach

Create a Graph class with a map of list named adjList that will be the adjacency list for the graph.
The adjList will be of the type <int, list<int>>.
The first data member of the adjList will represent a node and the second data member will be a linked list that will represent the list of nodes that have connection with the node.
Implement an addEdge(u,v) method to add edges between the u and v vertex of the graph. If u and v are valid:
Add vertex v to the adjacency list of vertex u.
Add vertex u to the adjacency list of vertex v as this is an undirected graph.
Implement a method print() to iterate through the adjacency list and print each vertex along with it’s connected vertices.

The following program illustrates how we can implement a graph using adjacency list in C++:

C++

// C++ Program to Implement a Graph Using Adjacency List
#include <iostream>
#include <list>
#include <map>
using namespace std;

class Graph {
    map<int, list<int> >
        adjList; // Adjacency list to store the graph

public:
    // Function to add an edge between vertices u and v of
    // the graph
    void add_edge(int u, int v)
    {
        // Add edge from u to v
        adjList[u].push_back(v);
        // Add edge from v to u because the graph is
        // undirected
        adjList[v].push_back(u);
    }

    // Function to print the adjacency list representation
    // of the graph
    void print()
    {
        cout << "Adjacency list for the Graph: " << endl;
        // Iterate over each vertex
        for (auto i : adjList) {
            // Print the vertex
            cout << i.first << " -> ";
            // Iterate over the connected vertices
            for (auto j : i.second) {
                // Print the connected vertex
                cout << j << " ";
            }
            cout << endl;
        }
    }
};

int main()
{
    // Create a graph object
    Graph g;

    // Add edges to create the graph
    g.add_edge(1, 0);
    g.add_edge(2, 0);
    g.add_edge(1, 2);

    // Print the adjacency list representation of the graph
    g.print();
    return 0;
}

Output

Adjacency list for the Graph: 
1 -> 2 3 
2 -> 1 4 6 4 6 
3 -> 1 5 5 
4 -> 2 2 
5 -> 3 3 
6 -> 2 2

Time Complexity: O(V+E), where V is the number of vertices in the graph and E is the number of edges in the graph.
Auxiliary Space: O(V+E)

Difference Between the Adjacency Matrix and Adjacency List

Aspect	Adjacency Matrix	Adjacency List
Memory Usage	Requires O(V^2) space	Requires O(V + E) space
Edge Existence Query	Quick O(1) check	O(degree(v)) check for adjacency of v
Space Efficiency	Inefficient for sparse graphs	Efficient for sparse graphs
Adding/Removing Edges	O(1) for adding/removing edges	Depends on data structure, typically O(1)
Iterating Over Edges	Inefficient, potentially O(V^2) for traversal	Efficient, O(V + E) for traversal
Suitability	Suitable for dense graphs	Suitable for sparse graphs

You can also go through the following articles to improve your understanding about the graph data structure:

Tags:

#CPP Examples #CPP-DSA #C++ #CPP