CPP Program to Implement a Graph Using Adjacency Matrix

by

Graphs are essential data structures used to model relationships between entities. In this article you will learn to write a C++ program to Implement a Graph Using Adjacency Matrix. Graphs are widely used in various applications, including computer networks, social networks, transportation systems, and more.

Prerequisites

Before we dive into the examples, it’s important to understand the following concepts:

  • Graph: A collection of nodes (vertices) and edges connecting some or all of them.
  • Adjacency Matrix: A 2D array where each element at row i and column j represents the presence (and sometimes the weight) of an edge between vertex i and vertex j.
  • Directed and Undirected Graphs: In a directed graph, edges have a direction, while in an undirected graph, edges do not.

Familiarity with C++ programming, including standard libraries like <iostream> and basic array operations, will be beneficial.

Implementing a Graph Using Adjacency Matrix

To represent a graph using an adjacency matrix in C++, we typically use a 2D array (or a vector of vectors). Each element in the matrix indicates whether an edge exists between two vertices and can also store the weight of the edge.

Pseudocode for Graph Representation

  1. Define a class for the graph.
  2. Initialize a 2D array (or vector of vectors).
  3. Implement methods to add edges and display the graph.

Examples

Example 1: Simple Undirected Graph

Graph Representation

Consider a simple undirected graph with four vertices:

C++
    (A)---(B)
     |     |
    (C)---(D)

C++ Program

C++
#include <iostream>
#include <vector>

using namespace std;

class Graph {
    int V; // Number of vertices
    vector<vector<int>> adjMatrix;

public:
    Graph(int V);
    void addEdge(int v, int w);
    void printGraph();
};

Graph::Graph(int V) {
    this->V = V;
    adjMatrix.resize(V, vector<int>(V, 0));
}

void Graph::addEdge(int v, int w) {
    adjMatrix[v][w] = 1;
    adjMatrix[w][v] = 1; // For undirected graph
}

void Graph::printGraph() {
    for (int i = 0; i < V; ++i) {
        for (int j = 0; j < V; ++j) {
            cout << adjMatrix[i][j] << " ";
        }
        cout << endl;
    }
}

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

    g.printGraph();

    return 0;
}

Output

C++
0 1 1 0 
1 0 0 1 
1 0 0 1 
0 1 1 0

Example 2: Directed Graph

Graph Representation

Consider a directed graph with four vertices:

C++
    (A)---->(B)
     ^      /|
     |     / |
    (C)<--/  |
         \   v
          ->(D)

C++ Program

C++
#include <iostream>
#include <vector>

using namespace std;

class Graph {
    int V;
    vector<vector<int>> adjMatrix;

public:
    Graph(int V);
    void addEdge(int v, int w);
    void printGraph();
};

Graph::Graph(int V) {
    this->V = V;
    adjMatrix.resize(V, vector<int>(V, 0));
}

void Graph::addEdge(int v, int w) {
    adjMatrix[v][w] = 1;
}

void Graph::printGraph() {
    for (int i = 0; i < V; ++i) {
        for (int j = 0; j < V; ++j) {
            cout << adjMatrix[i][j] << " ";
        }
        cout << endl;
    }
}

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

    g.printGraph();

    return 0;
}

Output

C++
0 1 0 0 
0 0 1 1 
1 0 0 0 
0 0 1 0

Example 3: Graph with Weighted Edges

Graph Representation

Consider a graph with weighted edges:

C++
    (A)--2--(B)
     |      /|
    4|     3 |
     |    /  |
    (C)--5--(D)

C++ Program

C++
#include <iostream>
#include <vector>

using namespace std;

class Graph {
    int V;
    vector<vector<int>> adjMatrix;

public:
    Graph(int V);
    void addEdge(int v, int w, int weight);
    void printGraph();
};

Graph::Graph(int V) {
    this->V = V;
    adjMatrix.resize(V, vector<int>(V, 0));
}

void Graph::addEdge(int v, int w, int weight) {
    adjMatrix[v][w] = weight;
    adjMatrix[w][v] = weight;
}

void Graph::printGraph() {
    for (int i = 0; i < V; ++i) {
        for (int j = 0; j < V; ++j) {
            cout << adjMatrix[i][j] << " ";
        }
        cout << endl;
    }
}

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

    g.printGraph();

    return 0;
}

Output

C++
0 2 4 0 
2 0 0 3 
4 0 0 5 
0 3 5 0

Conclusion

Implementing a graph using an adjacency matrix in C++ is a straightforward and efficient way to represent and manipulate graphs, especially when the graph is dense