Adjacency Matrix Representation in DSA C++

Mental Model

Use a square grid to show which nodes connect directly to which others by marking cells with 1 or 0.

Analogy: Imagine a city map with intersections as nodes and roads as connections; the matrix is like a table where each row and column shows if a road exists between two intersections.

  0 1 2
0 0 1 0
1 1 0 1
2 0 0 0

Rows and columns represent nodes; 1 means connected, 0 means no connection.

Dry Run Walkthrough

Input: Graph with 3 nodes (0, 1, 2) and edges: 0->1, 1->0, 1->2

Goal: Build the adjacency matrix showing connections between nodes

Step 1: Initialize a 3x3 matrix filled with 0s

  0 1 2
0 0 0 0
1 0 0 0
2 0 0 0

Why: Start with no connections marked

Step 2: Mark edge from node 0 to node 1 by setting matrix[0][1] = 1

  0 1 2
0 0 1 0
1 0 0 0
2 0 0 0

Why: Show that node 0 connects to node 1

Step 3: Mark edge from node 1 to node 0 by setting matrix[1][0] = 1

  0 1 2
0 0 1 0
1 1 0 0
2 0 0 0

Why: Show that node 1 connects back to node 0

Step 4: Mark edge from node 1 to node 2 by setting matrix[1][2] = 1

  0 1 2
0 0 1 0
1 1 0 1
2 0 0 0

Why: Show that node 1 connects to node 2

Result:

  0 1 2
0 0 1 0
1 1 0 1
2 0 0 0
Adjacency matrix correctly represents all edges.

Annotated Code

DSA C++

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

class Graph {
public:
    int n;
    vector<vector<int>> adjMatrix;

    Graph(int nodes) {
        n = nodes;
        adjMatrix = vector<vector<int>>(n, vector<int>(n, 0));
    }

    void addEdge(int from, int to) {
        adjMatrix[from][to] = 1; // mark connection from 'from' to 'to'
    }

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

int main() {
    Graph g(3); // 3 nodes: 0,1,2
    g.addEdge(0, 1); // edge 0->1
    g.addEdge(1, 0); // edge 1->0
    g.addEdge(1, 2); // edge 1->2

    g.printMatrix();
    return 0;
}

adjMatrix = vector<vector<int>>(n, vector<int>(n, 0));

Initialize n x n matrix with zeros to represent no edges

adjMatrix[from][to] = 1; // mark connection from 'from' to 'to'

Set matrix cell to 1 to show an edge from 'from' node to 'to' node

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

Print the adjacency matrix row by row

Output

0 1 0 

1 0 1 

0 0 0 

Complexity Analysis

Time: O(n^2) because we create and print an n by n matrix regardless of edges

Space: O(n^2) because the matrix stores n squared elements for all possible node pairs

vs Alternative: Compared to adjacency lists which use O(n + e) space, adjacency matrix uses more space but allows faster edge checks

Edge Cases

Empty graph with zero nodes

Matrix is empty; no edges to represent

DSA C++

Graph g(0); // handles zero nodes gracefully by creating empty matrix

Graph with no edges

Matrix remains all zeros showing no connections

DSA C++

adjMatrix initialized with zeros and no addEdge calls

Self-loop edge (node connects to itself)

Matrix cell at [node][node] is set to 1

DSA C++

adjMatrix[from][to] = 1; // works even if from == to

When to Use This Pattern

When you need to quickly check if two nodes are connected in constant time and the graph is small or dense, use adjacency matrix representation.

Common Mistakes

Mistake: Confusing row and column indices when marking edges
Fix: Remember matrix[from][to] means edge from 'from' node to 'to' node

Mistake: Not initializing the matrix with zeros before adding edges
Fix: Always initialize the matrix with zeros to represent no edges initially

Summary

Represents graph connections using a 2D grid where each cell shows if an edge exists between two nodes.

Use when you want fast edge lookup and the graph size is manageable.

The key is that rows represent source nodes and columns represent destination nodes in the matrix.

Practice

1. What does an adjacency matrix represent in graph theory?

easy

A. A sequence of visited nodes

B. A list of nodes in the graph

C. A 2D array showing connections between nodes

D. A stack used for graph traversal

Solution

1. Step 1: Understand adjacency matrix concept

   An adjacency matrix is a 2D array where rows and columns represent nodes.

2. Step 2: Identify what the matrix stores

   Each cell shows if there is a connection (edge) between two nodes.

3. Final Answer:

   A 2D array showing connections between nodes -> Option C

4. Quick Check:

   Adjacency matrix = 2D array of connections [OK]

Hint: Adjacency matrix = grid showing edges between nodes [OK]

Common Mistakes:

• Confusing adjacency matrix with adjacency list
• Thinking it stores node values instead of edges
• Mixing it up with traversal order

2. Which of the following is the correct way to declare a 4x4 adjacency matrix in C++?

easy

A. int matrix(4,4);

B. int matrix[][] = new int[4][4];

C. int matrix[4];

D. int matrix[4][4];

Solution

1. Step 1: Recall C++ array declaration syntax

   In C++, a 2D array is declared as type name[size1][size2].

2. Step 2: Check each option

   int matrix[4][4]; uses correct syntax: int matrix[4][4]; int matrix(4,4); is invalid syntax, C is 1D array, D is invalid in C++.

3. Final Answer:

   int matrix[4][4]; -> Option D

4. Quick Check:

   2D array declaration = int matrix[4][4]; [OK]

Hint: Use int name[rows][cols] for 2D arrays in C++ [OK]

Common Mistakes:

• Using parentheses instead of brackets
• Declaring only one dimension
• Trying Java-style new keyword in C++

3. Given the following adjacency matrix for a graph with 3 nodes:

int graph[3][3] = {
  {0, 1, 0},
  {1, 0, 1},
  {0, 1, 0}
};

What is the output of this code snippet?

for (int i = 0; i < 3; i++) {
  for (int j = 0; j < 3; j++) {
    if (graph[i][j] == 1) {
      std::cout << i << "->" << j << " ";
    }
  }
}

medium

A. 0->1 1->0 1->2 2->1

B. 0->0 1->1 2->2

C. 1->0 2->1

D. 0->2 2->0

Solution

1. Step 1: Analyze the adjacency matrix values

   Matrix shows edges: 0 connected to 1, 1 connected to 0 and 2, 2 connected to 1.

2. Step 2: Trace the nested loops and print statements

   For each i,j where graph[i][j] == 1, print i->j. This matches edges 0->1, 1->0, 1->2, 2->1.

3. Final Answer:

   0->1 1->0 1->2 2->1 -> Option A

4. Quick Check:

   Edges printed = 0->1 1->0 1->2 2->1 [OK]

Hint: Print edges where matrix cell is 1 [OK]

Common Mistakes:

• Ignoring symmetric edges in undirected graph
• Printing zeros as edges
• Mixing row and column indices

4. Identify the error in this adjacency matrix initialization code for a graph with 2 nodes:

int graph[2][2] = {
  {0, 1},
  {1}
};

medium

A. Second row has missing element

B. Matrix size is incorrect

C. Values should be boolean, not int

D. Initialization syntax is correct

Solution

1. Step 1: Check each row's initialization length

   First row has 2 elements: {0,1}. Second row has only 1 element: {1}.

2. Step 2: Understand 2D array initialization rules

   Each row must have exactly 2 elements to match declared size. Missing element causes error.

3. Final Answer:

   Second row has missing element -> Option A

4. Quick Check:

   Each row must match declared column size [OK]

Hint: Each row must have same number of elements as columns [OK]

Common Mistakes:

• Assuming partial row initialization is allowed
• Confusing matrix size with data type
• Ignoring compiler error messages

5. You have a directed graph with 4 nodes represented by this adjacency matrix:

int graph[4][4] = {
  {0, 1, 0, 0},
  {0, 0, 1, 0},
  {0, 0, 0, 1},
  {1, 0, 0, 0}
};

Write a function in C++ that returns true if there is an edge from node u to node v, false otherwise. Which of these is correct?

hard

A. bool hasEdge(int u, int v) { return graph[v][u] == 1; }

B. bool hasEdge(int u, int v) { return graph[u][v] == 1; }

C. bool hasEdge(int u, int v) { return graph[u][v] == 0; }

D. bool hasEdge(int u, int v) { return graph[u] == graph[v]; }

Solution

1. Step 1: Understand adjacency matrix indexing for edges

   graph[u][v] == 1 means edge from node u to node v exists.

2. Step 2: Check each function option

   bool hasEdge(int u, int v) { return graph[u][v] == 1; } correctly returns true if edge exists. bool hasEdge(int u, int v) { return graph[v][u] == 1; } reverses indices, C checks for no edge, D compares rows incorrectly.

3. Final Answer:

   bool hasEdge(int u, int v) { return graph[u][v] == 1; } -> Option B

4. Quick Check:

   Check graph[u][v] == 1 for edge presence [OK]

Hint: Check graph[u][v] == 1 for edge from u to v [OK]

Common Mistakes:

• Swapping u and v indices
• Checking for zero instead of one
• Comparing entire rows instead of single cell