Graph Representation

Graph Representation

The first hurdle while solving any graph problem is how to represent the graphs in programming languages. The two most commonly used representations for graphs are:

1. Adjacency Matrix
2. Adjacency Lists

Adjacency Matrix

An adjacency matrix of a graph is a two-dimensional array of size n x n, where n is the number of nodes in the graph, with the property that a[i][j] = 1 if the edge (vᵢ, vⱼ) is in the set of edges, and a[i][j] = 0 if there is no such edge.

Consider the following input:

5 6
1 2
1 3
2 4
3 4
3 5
4 5

Here, the number of nodes n = 5 and the number of edges m = 6. The next m lines represent the edges.

The first thing to identify is the indexing used for nodes — 0-based or 1-based. In this case, the nodes follow one-based indexing as the last node is 5 and the total number of nodes is also 5. Define an adjacency matrix of size (n+1) x (n+1), i.e., adj[n+1][n+1].

If there is an edge between 1 and 2, mark 1 at positions (1,2) and (2,1) since the graph is undirected. The resulting matrix for the above example:

This matrix tells if there is an edge between two particular nodes. For example, there is an edge between 5 and 3 as 1 is at position (5,3), but no edge between 5 and 1 as the value is 0 at position (5,1).

#include <bits/stdc++.h>
using namespace std;

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

    // Adjacency matrix to store the graph
    int adj[n+1][n+1];

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

        adj[u][v] = 1;
        adj[v][u] = 1;  // Remove this line for directed graphs
    }
    return 0;
}

Space Complexity: O(N²) — It is costly for large graphs. Preferred for dense graphs where the number of edges is high.

Adjacency List

This is a node-based representation. Each node is associated with a list of its adjacent nodes. An array of size n+1 stores a list (vector) for each node.

For the same undirected graph above, the adjacency list looks like:

1 → [2, 3]
2 → [1, 4]
3 → [1, 4, 5]
4 → [2, 3, 5]
5 → [3, 4]

Each edge appears twice in an undirected graph — for example, nodes 1 and 2 are adjacent so 2 appears in the list of 1, and 1 appears in the list of 2.

#include <bits/stdc++.h>
using namespace std;

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

    // Adjacency list for undirected graph
    vector<int> adj[n+1];

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

        adj[u].push_back(v);
        adj[v].push_back(u);  // Remove this line for directed graphs
    }
    return 0;
}

Space Complexity: O(2 × E) for undirected graphs. Much more efficient than adjacency matrix for sparse graphs (fewer edges), since the matrix wastes N² locations with mostly zeros.

Weighted Graph Representation

For weighted graphs, the edge weight needs to be stored alongside the connection:

• Adjacency Matrix: Store the weight at a[u][v] instead of just 1.
• Adjacency List: Store a list of pairs {adjacent node, edge weight} instead of just integers.

// Weighted adjacency list
vector<pair<int, int>> adj[n+1];  // {neighbor, weight}

// Adding a weighted edge
adj[u].push_back({v, weight});
adj[v].push_back({u, weight});  // Remove for directed graphs