Graph Representation in C++ | Two Ways to Represent

Understanding how to store and represent a graph in computer memory is the fundamental first step before applying any graph algorithm (such as Breadth-First Search, Depth-First Search, or shortest path algorithms). This chapter explores the two primary ways to represent graphs in C++ (Adjacency Matrix and Adjacency List), handling both undirected and directed graphs, as well as extending these concepts to weighted graphs.

1. Understanding Graph Input Formats

Before writing code to store a graph, we must understand how graph data is typically supplied in algorithmic problems and competitive programming.

When dealing with graph problems, the input standard almost always follows a predictable pattern:

• First Line (n, m): The program receives two integers, where n represents the total number of nodes (vertices) and m represents the total number of edges.
• Subsequent Lines (m lines): Each of the next m lines contains a pair of integers (u, v) indicating an edge connecting node u and node v.

Note: Nodes can be either 0-based indexing (ranging from 0 to n-1) or 1-based indexing (ranging from 1 to n). The example above uses 1-based indexing, where nodes are labeled 1 through 5.

2. Approach 1: The Adjacency Matrix

The most intuitive way to store a graph is by using a 2D array or matrix, commonly known as an Adjacency Matrix.

Core Mental Model & Strategy

Imagine a grid where both rows and columns represent the nodes of the graph. If there are n nodes, we create a matrix of size (n + 1) x (n + 1) (to accommodate 1-based indexing comfortably).

• If an edge exists between node u and node v, we mark matrix[u][v] = 1.
• For an undirected graph, the edge goes both ways, so we also mark matrix[v][u] = 1.
• All other cells with no direct connections remain 0.

Visualizing the Adjacency Matrix

For a graph with nodes 1 to 5, our matrix layout looks like this:

C++ Implementation: Adjacency Matrix

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    // Declare adjacency matrix of size (n + 1) x (n + 1) initialized to 0
    vector<vector<int>> adj(n + 1, vector<int>(n + 1, 0));

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        
        // Mark the connection for undirected graph
        adj[u][v] = 1;
        adj[v][u] = 1; // Remove this line if the graph is directed
    }

    return 0;
}

Limitations of Adjacency Matrix

• Space Complexity: Requires $O(n^2)$ space because of the 2D grid. If a graph has 10,000 nodes, it demands $10^8$ integer allocations regardless of how few edges exist.
• Wasted Memory: For sparse graphs (where the number of edges m is much smaller than $n^2$), most of the matrix cells store 0, leading to severe memory inefficiency.

3. Approach 2: The Adjacency List

To overcome the massive memory waste of matrices, we use an Adjacency List. Instead of reserving a slot for every possible node pair, we only store actual connections.

Core Mental Model & Strategy

Think of each node as a person with an address book. Person 4 only writes down the names of people they are directly friends with.

• We create an array of lists (implemented in C++ as vector<int> adj[n + 1]).
• Index 4 of this array will hold a dynamic vector containing its immediate neighbors (e.g., {2, 5, 3}).

C++ Implementation: Adjacency List (Undirected Graph)

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    // Create an array of vectors of size n + 1
    vector<int> adj[n + 1];

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;

        // Since it's undirected, push v into u's list, and u into v's list
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    return 0;
}

4. Undirected vs. Directed Graphs in Adjacency Lists

The way we populate our adjacency list depends entirely on whether travel is bidirectional (undirected) or one-way (directed).

Real-World Production Rule: In professional software engineering and competitive programming, Adjacency Lists are overwhelmingly preferred over Adjacency Matrices due to their optimal space complexity of $O(v + 2e)$ or $O(v + e)$.

5. Handling Weighted Graphs

So far, we assumed all edges have an equal weight of 1. But what happens when edges carry weights (e.g., road distances, network latency, ticket prices)?

How Matrix Changes for Weights

Instead of putting a binary 1 at adj[u][v], we store the actual weight value:

int wt;
cin >> u >> v >> wt;
adj[u][v] = wt;
adj[v][u] = wt;

How List Changes for Weights (Using Pairs)

In an adjacency list, a simple vector of integers (vector<int>) is no longer enough because we need to store both the neighboring node and the edge weight. We solve this in C++ by storing pairs (pair<int, int>): (neighbor_node, weight).

C++ Implementation: Weighted Adjacency List

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    // Array of vectors holding pairs: vector<pair<int, int>> adj[n + 1]
    // Pair structure: {neighbor_node, weight}
    vector<pair<int, int>> adj[n + 1];

    for (int i = 0; i < m; i++) {
        int u, v, wt;
        cin >> u >> v >> wt;

        // Store neighbor and weight for undirected weighted graph
        adj[u].push_back({v, wt});
        adj[v].push_back({u, wt});
    }

    return 0;
}

6. Summary and Key Takeaways

• Input Structure: Graph inputs always start with total nodes n and edges m, followed by m lines defining edge pairs (u, v).
• Node Indexing: Pay close attention to whether the problem uses 0-based (0 to n-1) or 1-based (1 to n) node indexing to size your data structures correctly (n vs n + 1).
• Adjacency Matrix: A 2D grid vector<vector<int>> taking $O(n^2)$ space, useful for dense graphs or rapid edge-lookup checks (O(1) time), but wasteful for sparse graphs.
• Adjacency List: An array of dynamic vectors vector<int> adj[n + 1] taking $O(2e)$ space for undirected graphs and $O(e)$ for directed graphs.
• Directed Graph Storage: Only insert the destination into the source's list (adj[u].push_back(v)) without the reciprocal insertion.
• Weighted Graphs: Extend adjacency lists by storing pairs (pair<int, int>) containing both the target node and the edge weight.
• Industry Standard: Adjacency lists are the default choice for graph algorithms in real-world applications due to their exceptional memory efficiency.