Graphs are essential data structures in computer science, used to model relationships between objects. Efficiently representing a graph is crucial for performing various graph algorithms such as traversal, shortest path finding, and cycle detection. The two most common ways to represent a graph are using an Adjacency List and an Adjacency Matrix. This article provides a comprehensive C++ program that demonstrates both representations, complete with detailed explanations and documentation.

Program Structure

The C++ program to represent a graph using both adjacency list and adjacency matrix is organized into the following key components:

• Graph Class: Encapsulates both adjacency list and adjacency matrix representations.
• Graph Construction: Methods to add edges to the graph.
• Display Functions: Methods to display the adjacency list and adjacency matrix.
• Main Function: Handles user input, constructs the graph, and invokes display functions.

Code Implementation

The following C++ program implements graph representation using both adjacency list and adjacency matrix:

// Graph Representation in C++
// This program demonstrates how to represent a graph using both
// Adjacency List and Adjacency Matrix.

#include <iostream>
#include <vector>
#include <list&gt>
#include <iomanip> // for setw

using namespace std;

// Graph Class
class Graph {
    int V; // Number of vertices
    bool directed; // Flag to indicate if the graph is directed
    vector<list> adjList; // Adjacency List
    vector<vector> adjMatrix; // Adjacency Matrix

public:
    // Constructor
    Graph(int V, bool directed = false);

    // Function to add an edge to the graph
    void addEdge(int src, int dest);

    // Function to display the adjacency list
    void displayAdjList();

    // Function to display the adjacency matrix
    void displayAdjMatrix();
};

// Constructor Implementation
Graph::Graph(int V, bool directed) {
    this->V = V;
    this->directed = directed;
    adjList.resize(V, list());
    adjMatrix.resize(V, vector(V, 0));
}

// addEdge Implementation
void Graph::addEdge(int src, int dest) {
    // Add edge to adjacency list
    adjList[src].push_back(dest);
    if (!directed) {
        adjList[dest].push_back(src);
    }

    // Add edge to adjacency matrix
    adjMatrix[src][dest] = 1;
    if (!directed) {
        adjMatrix[dest][src] = 1;
    }
}

// displayAdjList Implementation
void Graph::displayAdjList() {
    cout << "\nAdjacency List Representation:\n";
    for(int i = 0; i < V; i++) {
        cout << "Vertex " << i << ": ";
        for(auto &vertex : adjList[i]) {
            cout << vertex << " ";
        }
        cout << endl;
    }
}

// displayAdjMatrix Implementation
void Graph::displayAdjMatrix() {
    cout << "\nAdjacency Matrix Representation:\n";
    // Print column headers
    cout << "  ";
    for(int i = 0; i < V; i++) {
        cout << i << " ";
    }
    cout << endl;

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

int main() {
    int V, E, choice;
    bool directed;

    cout << "Graph Representation using Adjacency List and Adjacency Matrix in C++\n";
    cout << "--------------------------------------------------------------\n";
    cout << "Is the graph Directed or Undirected?\n";
    cout << "1. Directed\n";
    cout << "2. Undirected\n";
    cout << "Enter your choice (1 or 2): ";
    cin >> choice;

    if(choice == 1)
        directed = true;
    else if(choice == 2)
        directed = false;
    else {
        cout << "Invalid choice! Exiting.\n";
        return 1;
    }

    cout << "Enter the number of vertices: ";
    cin >> V;
    cout << "Enter the number of edges: ";
    cin >> E;

    Graph g(V, directed);

    cout << "Enter the edges in the format (source destination):\n";
    for(int i = 0; i < E; i++) {
        int src, dest;
        cin >> src >> dest;
        if(src < 0 || src >= V || dest < 0 || dest >= V) {
            cout << "Invalid edge! Vertices should be between 0 and " << V-1 << ".\n";
            i--; // Decrement to retry this edge
            continue;
        }
        g.addEdge(src, dest);
    }

    g.displayAdjList();
    g.displayAdjMatrix();

    return 0;
}
            

Program Explanation

The program encapsulates both adjacency list and adjacency matrix representations within a single Graph class. Users can choose whether to represent a directed or undirected graph and input the edges accordingly. Below is a detailed breakdown of the program’s components:

1. Graph Class

The Graph class manages the graph’s representation using both adjacency list and adjacency matrix. It provides methods to add edges and display both representations.

• Members:
  • int V; – Number of vertices in the graph.
  • bool directed; – Flag indicating if the graph is directed.
  • vector<list<int>> adjList; – Adjacency list representation.
  • vector<vector<int>> adjMatrix; – Adjacency matrix representation.
• Functions:
  • Graph(int V, bool directed = false); – Constructor to initialize the graph.
  • void addEdge(int src, int dest); – Adds an edge to both representations.
  • void displayAdjList(); – Displays the adjacency list.
  • void displayAdjMatrix(); – Displays the adjacency matrix.

2. Constructor

The constructor initializes the number of vertices, determines if the graph is directed, and initializes the adjacency list and adjacency matrix with appropriate sizes.

// Constructor Implementation
Graph::Graph(int V, bool directed) {
    this->V = V;
    this->directed = directed;
    adjList.resize(V, list());
    adjMatrix.resize(V, vector(V, 0));
}
        

3. addEdge Function

The addEdge function adds an edge from src to dest. If the graph is undirected, it also adds an edge from dest to src. The function updates both the adjacency list and the adjacency matrix accordingly.

// addEdge Implementation
void Graph::addEdge(int src, int dest) {
    // Add edge to adjacency list
    adjList[src].push_back(dest);
    if (!directed) {
        adjList[dest].push_back(src);
    }

    // Add edge to adjacency matrix
    adjMatrix[src][dest] = 1;
    if (!directed) {
        adjMatrix[dest][src] = 1;
    }
}
        

4. displayAdjList Function

The displayAdjList function iterates through each vertex’s adjacency list and prints the connected vertices.

// displayAdjList Implementation
void Graph::displayAdjList() {
    cout << "\nAdjacency List Representation:\n";
    for(int i = 0; i < V; i++) {
        cout << "Vertex " << i << ": ";
        for(auto &vertex : adjList[i]) {
            cout << vertex << " ";
        }
        cout << endl;
    }
}
        

5. displayAdjMatrix Function

The displayAdjMatrix function prints the adjacency matrix with proper formatting, displaying a 1 if an edge exists between two vertices and 0 otherwise.

// displayAdjMatrix Implementation
void Graph::displayAdjMatrix() {
    cout << "\nAdjacency Matrix Representation:\n";
    // Print column headers
    cout << "  ";
    for(int i = 0; i < V; i++) {
        cout << i << " ";
    }
    cout << endl;

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

6. Main Function

The main function handles user interaction, including selecting the graph type (directed or undirected), inputting the number of vertices and edges, adding edges to the graph, and displaying both representations.

int main() {
    int V, E, choice;
    bool directed;

    cout << "Graph Representation using Adjacency List and Adjacency Matrix in C++\n";
    cout << "--------------------------------------------------------------\n";
    cout << "Is the graph Directed or Undirected?\n";
    cout << "1. Directed\n";
    cout << "2. Undirected\n";
    cout << "Enter your choice (1 or 2): ";
    cin >> choice;

    if(choice == 1)
        directed = true;
    else if(choice == 2)
        directed = false;
    else {
        cout << "Invalid choice! Exiting.\n";
        return 1;
    }

    cout << "Enter the number of vertices: ";
    cin >> V;
    cout << "Enter the number of edges: ";
    cin >> E;

    Graph g(V, directed);

    cout << "Enter the edges in the format (source destination):\n";
    for(int i = 0; i < E; i++) {
        int src, dest;
        cin >> src >> dest;
        if(src < 0 || src >= V || dest < 0 || dest >= V) {
            cout << "Invalid edge! Vertices should be between 0 and " << V-1 << ".\n";
            i--; // Decrement to retry this edge
            continue;
        }
        g.addEdge(src, dest);
    }

    g.displayAdjList();
    g.displayAdjMatrix();

    return 0;
}
        

Program Documentation

Detailed documentation for each component of the program:

Class: Graph

• Purpose: Represents a graph using both adjacency list and adjacency matrix representations.
• Members:
  • int V; – Number of vertices in the graph.
  • bool directed; – Flag indicating whether the graph is directed.
  • vector<list<int>> adjList; – Adjacency list representation of the graph.
  • vector<vector<int>> adjMatrix; – Adjacency matrix representation of the graph.
• Functions:
  • Graph(int V, bool directed = false); – Constructor to initialize the graph with V vertices and specify if it’s directed.
  • void addEdge(int src, int dest); – Adds an edge between vertices src and dest.
  • void displayAdjList(); – Displays the adjacency list of the graph.
  • void displayAdjMatrix(); – Displays the adjacency matrix of the graph.

Function: addEdge

• Purpose: Adds an edge between two vertices in both adjacency list and adjacency matrix representations.
• Parameters:
  • int src – The source vertex.
  • int dest – The destination vertex.
• Returns: None.
• Logic:
  1. Adds dest to the adjacency list of src.
  2. If the graph is undirected, adds src to the adjacency list of dest.
  3. Sets the corresponding entries in the adjacency matrix to 1 to indicate the presence of an edge.
  4. If the graph is undirected, sets both [src][dest] and [dest][src] to 1.

Function: displayAdjList

• Purpose: Displays the adjacency list representation of the graph.
• Parameters: None.
• Returns: None. Prints the adjacency list to the console.
• Logic:
  1. Iterates through each vertex.
  2. For each vertex, iterates through its adjacency list and prints connected vertices.

Function: displayAdjMatrix

• Purpose: Displays the adjacency matrix representation of the graph.
• Parameters: None.
• Returns: None. Prints the adjacency matrix to the console.
• Logic:
  1. Prints column headers for clarity.
  2. Iterates through each row of the adjacency matrix.
  3. For each row, prints the row index followed by the binary indicators of edge presence.

Constructor: Graph(int V, bool directed = false)

• Purpose: Initializes the graph with a specified number of vertices and sets whether it is directed.
• Parameters:
  • int V – Number of vertices in the graph.
  • bool directed – Flag indicating if the graph is directed (default is undirected).
• Returns: None.
• Logic:
  1. Sets the number of vertices and the directed flag.
  2. Resizes the adjacency list to accommodate all vertices.
  3. Initializes the adjacency matrix with zeros, indicating no edges initially.

How the Program Works

1. User Input: The program begins by prompting the user to specify whether the graph is directed or undirected. It then asks for the number of vertices and edges.
2. Graph Construction: Based on the number of vertices and edges, the program reads each edge’s source and destination vertices. It validates the vertex indices to ensure they are within the valid range. Each edge is added to both the adjacency list and adjacency matrix representations.
3. Displaying Representations: After constructing the graph, the program displays both the adjacency list and adjacency matrix, providing two different perspectives of the same graph.

Example Execution

Consider the following example input and output:

Example 1: Undirected Graph

Graph Representation using Adjacency List and Adjacency Matrix in C++
--------------------------------------------------------------
Is the graph Directed or Undirected?
1. Directed
2. Undirected
Enter your choice (1 or 2): 2
Enter the number of vertices: 4
Enter the number of edges: 4
Enter the edges in the format (source destination):
0 1
0 2
1 2
2 3

Adjacency List Representation:
Vertex 0: 1 2 
Vertex 1: 0 2 
Vertex 2: 0 1 3 
Vertex 3: 2 

Adjacency Matrix Representation:
  0 1 2 3 
0 0 1 1 0 
1 1 0 1 0 
2 1 1 0 1 
3 0 0 1 0 
        

Explanation: The user chooses an undirected graph with 4 vertices and 4 edges. The edges added are between vertices (0-1), (0-2), (1-2), and (2-3). The adjacency list and adjacency matrix accurately reflect these connections.

Example 2: Directed Graph

Graph Representation using Adjacency List and Adjacency Matrix in C++
--------------------------------------------------------------
Is the graph Directed or Undirected?
1. Directed
2. Undirected
Enter your choice (1 or 2): 1
Enter the number of vertices: 3
Enter the number of edges: 3
Enter the edges in the format (source destination):
0 1
1 2
2 0

Adjacency List Representation:
Vertex 0: 1 
Vertex 1: 2 
Vertex 2: 0 

Adjacency Matrix Representation:
  0 1 2 
0 0 1 0 
1 0 0 1 
2 1 0 0 
        

Explanation: The user chooses a directed graph with 3 vertices and 3 edges. The edges added are from vertex 0 to 1, vertex 1 to 2, and vertex 2 to 0. The adjacency list and adjacency matrix accurately reflect these directed connections.

Conclusion

Representing graphs efficiently is crucial for the performance of various graph algorithms. This C++ program demonstrates both adjacency list and adjacency matrix representations, highlighting their differences and use-cases. Adjacency lists are more space-efficient for sparse graphs, while adjacency matrices provide faster access for dense graphs. Understanding these representations enables developers to choose the most appropriate one based on the specific requirements of their applications.