Graph Implementation in C++ using Adjacency List and Matrix

Graph is the most fundamental concept in data science and in this blog we will be covering Graph implementation in C++ using both adjacency matrix and adjacency list. In Graph every node is connected with each other through edges that maintains the relationship between each other.

Graph is a hierarchical model that maintains network between nodes in a direct and undirected manner. There are different types of graphs in data structures. So let’s begin to understanding the introduction and types of graph representation.

What is a Graph?

Graphs are the important concept in computer science domain because it is worked on a hierarchical model. In Graph data structure there are two components that are nodes and edges and the nodes are connected with each other through edges.

There are different types of graph in data structure which includes directed graph, undirected graph, weighted graph, cyclic graph, acyclic graph, complete graph, connected and disconnected graph.

Let’s understand graph easily through the visual representation which is given below in diagram. In this diagram A, B, C and D all are nodes connected through the edges and this is the example of undirected graph (consists of no direction).

Types of Graphs Representation

There are two ways we can represent graphs :

1. Adjacency Matrix
2. Adjacency List

Let’s better understand the graph representation in C++ using both Adjacency Matrix and List in the next section.

Graph Implementation in C++ using Adjacency Matrix

A graph can be represented in different ways. One of the simplest methods is using an adjacency matrix. This method is easy to understand and is ideal for dense graphs.

In an adjacency matrix we use a 2D array where each cell shows whether there is a connection between two nodes. If there is an edge from node i to node j the matrix entry adj[i][j] is set to 1. If there is no edge it stays 0.

Here is a basic graph implementation in C++ using an adjacency matrix:

#include <iostream>
using namespace std;

class Graph {
private:
    int numVertices;
    int** adjMatrix;

public:
    Graph(int vertices) {
        numVertices = vertices;
        adjMatrix = new int*[numVertices];
        for (int i = 0; i < numVertices; i++) {
            adjMatrix[i] = new int[numVertices];
            for (int j = 0; j < numVertices; j++)
                adjMatrix[i][j] = 0;
        }
    }

    void addEdge(int i, int j) {
        adjMatrix[i][j] = 1;
        adjMatrix[j][i] = 1;
    }

    void removeEdge(int i, int j) {
        adjMatrix[i][j] = 0;
        adjMatrix[j][i] = 0;
    }

    void display() {
        for (int i = 0; i < numVertices; i++) {
            for (int j = 0; j < numVertices; j++) {
                cout << adjMatrix[i][j] << " ";
            }
            cout << endl;
        }
    }

    ~Graph() {
        for (int i = 0; i < numVertices; i++)
            delete[] adjMatrix[i];
        delete[] adjMatrix;
    }
};

int main() {
    Graph g(5);
    g.addEdge(0, 1);
    g.addEdge(0, 4);
    g.addEdge(1, 2);
    g.addEdge(1, 3);
    g.addEdge(1, 4);
    g.addEdge(2, 3);
    g.addEdge(3, 4);

    cout << "Adjacency Matrix:" << endl;
    g.display();

    return 0;
}

This program creates a graph with 5 nodes and adds connections between them. The display function prints the adjacency matrix so you can easily see which nodes are connected.

Graph Implementation in C++ using Adjacency List

Another popular way to represent a graph is using an adjacency list. This method is more memory-efficient than an adjacency matrix especially when the graph is sparse.

In an adjacency list each node stores a list of all the nodes it is connected to. This saves space because we only store edges that actually exist.

Here is a simple graph implementation in C++ using an adjacency list:

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

class Graph {
private:
    int numVertices;
    vector<vector<int>> adjList;

public:
    Graph(int vertices) {
        numVertices = vertices;
        adjList.resize(numVertices);
    }

    void addEdge(int u, int v) {
        adjList[u].push_back(v);
        adjList[v].push_back(u);
    }

    void display() {
        for (int i = 0; i < numVertices; i++) {
            cout << i << ": ";
            for (int neighbor : adjList[i]) {
                cout << neighbor << " ";
            }
            cout << endl;
        }
    }
};

int main() {
    Graph g(5);
    g.addEdge(0, 1);
    g.addEdge(0, 4);
    g.addEdge(1, 2);
    g.addEdge(1, 3);
    g.addEdge(1, 4);
    g.addEdge(2, 3);
    g.addEdge(3, 4);

    cout << "Adjacency List:" << endl;
    g.display();

    return 0;
}

FAQs

What is the difference between adjacency matrix and adjacency list?

An adjacency matrix uses a 2D array to show all possible connections between nodes. An adjacency list uses linked lists or vectors to store only the existing edges. The list saves more memory when the graph has fewer edges.

Which is better for a large graph adjacency matrix or adjacency list?

For large graphs with fewer edges an adjacency list is better because it uses less memory.

Can I use the same code for directed graphs?

Yes you can use the same code for the directed graphs.