Adjacency Matrix Representation in DSA C++ - Execution Trace

Concept Flow - Adjacency Matrix Representation

Start

↓

Create NxN matrix

↓

Initialize all cells to 0

↓

For each edge (u,v)

↓

Set matrix[u

↓

If undirected, set matrix[v

↓

Repeat for all edges

↓

Adjacency matrix ready

Build a square matrix with size equal to number of nodes, fill zeros, then mark 1 where edges exist.

Execution Sample

DSA C++

int graph[4][4] = {0};
graph[0][1] = 1;
graph[1][2] = 1;
graph[2][3] = 1;
graph[3][0] = 1;

Create a 4-node graph adjacency matrix and add edges between nodes.

Execution Table

Step	Operation	Matrix State	Explanation
1	Initialize 4x4 matrix with zeros	[[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]]	All nodes start with no edges
2	Add edge 0->1	[[0,1,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]]	Mark 1 at row 0, column 1
3	Add edge 1->2	[[0,1,0,0],[0,0,1,0],[0,0,0,0],[0,0,0,0]]	Mark 1 at row 1, column 2
4	Add edge 2->3	[[0,1,0,0],[0,0,1,0],[0,0,0,1],[0,0,0,0]]	Mark 1 at row 2, column 3
5	Add edge 3->0	[[0,1,0,0],[0,0,1,0],[0,0,0,1],[1,0,0,0]]	Mark 1 at row 3, column 0
6	End	[[0,1,0,0],[0,0,1,0],[0,0,0,1],[1,0,0,0]]	All edges added, matrix complete

💡 All edges processed, adjacency matrix fully represents graph

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	Final
graph	[[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]]	[[0,1,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]]	[[0,1,0,0],[0,0,1,0],[0,0,0,0],[0,0,0,0]]	[[0,1,0,0],[0,0,1,0],[0,0,0,1],[0,0,0,0]]	[[0,1,0,0],[0,0,1,0],[0,0,0,1],[1,0,0,0]]	[[0,1,0,0],[0,0,1,0],[0,0,0,1],[1,0,0,0]]

Key Moments - 3 Insights

Why do we initialize the matrix with zeros before adding edges?

Because zeros mean no connection between nodes. The execution_table step 1 shows the matrix with all zeros before edges are added.

Why do we set matrix[u][v] = 1 for each edge?

Setting matrix[u][v] = 1 marks that there is an edge from node u to node v. See execution_table steps 2-5 where each edge updates one cell to 1.

How do we represent an undirected edge in the matrix?

For undirected edges, we set both matrix[u][v] and matrix[v][u] to 1. This is not shown in this example but is explained in concept_flow.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the value of graph[1][2]?

A 1

B 0

C 2

D -1

💡 Hint

Check the matrix state column at step 3 in execution_table

At which step does the edge from node 3 to node 0 get added?

A Step 2

B Step 5

C Step 4

D Step 6

💡 Hint

Look at the Operation column in execution_table for edge 3->0

If the graph was undirected, what additional change would happen at step 2?

A Set graph[2][1] = 1

B Set graph[0][0] = 1

C Set graph[1][0] = 1

D No change

💡 Hint

Refer to concept_flow where undirected edges set both matrix[u][v] and matrix[v][u]

Concept Snapshot

Adjacency Matrix Representation:
- Use NxN matrix for N nodes
- Initialize all cells to 0 (no edges)
- For each edge u->v, set matrix[u][v] = 1
- For undirected graphs, also set matrix[v][u] = 1
- Matrix shows direct connections between nodes

Full Transcript

Adjacency matrix representation uses a square matrix to show connections between nodes in a graph. We start by creating an NxN matrix filled with zeros, meaning no edges. Then for each edge from node u to node v, we mark matrix[u][v] as 1 to show a connection. If the graph is undirected, we also mark matrix[v][u] as 1. This way, the matrix visually and numerically represents all edges in the graph. The example shows a 4-node graph with edges added step-by-step, updating the matrix cells accordingly.

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