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 graph, set matrix[v

↓

Matrix ready to represent graph

↓

Use matrix for graph operations

↓

End

Create a square matrix with size equal to number of nodes, fill with zeros, then mark edges by setting 1s at corresponding positions.

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;

This code creates a 4-node graph and marks edges between nodes using an adjacency matrix.

Execution Table

Step	Operation	Matrix State	Pointer Changes	Visual State
1	Initialize 4x4 matrix with zeros	[[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]]	None	0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2	Add edge 0->1	[[0,1,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]]	graph[0][1] set to 1	0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3	Add edge 1->2	[[0,1,0,0],[0,0,1,0],[0,0,0,0],[0,0,0,0]]	graph[1][2] set to 1	0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0
4	Add edge 2->3	[[0,1,0,0],[0,0,1,0],[0,0,0,1],[0,0,0,0]]	graph[2][3] set to 1	0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0
5	Add edge 3->0	[[0,1,0,0],[0,0,1,0],[0,0,0,1],[1,0,0,0]]	graph[3][0] set to 1	0 1 0 0 0 0 1 0 0 0 0 1 1 0 0 0
6	End of edge additions	[[0,1,0,0],[0,0,1,0],[0,0,0,1],[1,0,0,0]]	None	Final matrix represents graph edges

💡 All edges added, matrix fully represents the 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 entire matrix with zeros before adding edges?

Because the matrix must start with no connections; zeros mean no edges. This is shown in Step 1 of the execution_table where the matrix is all zeros before edges are added.

Why do we set graph[u][v] = 1 to represent an edge?

Setting graph[u][v] = 1 marks that there is a direct edge from node u to node v. This is shown in Steps 2 to 5 where each edge updates one cell to 1.

How does the matrix represent direction in the graph?

The row index is the start node and the column index is the end node. So graph[u][v] = 1 means edge from u to v. For example, Step 2 sets graph[0][1] = 1 meaning edge from node 0 to node 1.

Visual Quiz - 3 Questions

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

A 1

B 2

C 0

D Undefined

💡 Hint

Check the 'Matrix State' column at Step 3 in the execution_table

At which step does the matrix first show an edge from node 3 to node 0?

A Step 3

B Step 5

C Step 2

D Step 4

💡 Hint

Look for graph[3][0] = 1 in the 'Matrix State' column in execution_table

If we add an edge from node 1 to node 0 in this matrix, what will change?

A graph[0][1] will become 0

B graph[1][2] will become 0

C graph[1][0] will become 1

D No change in matrix

💡 Hint

Adding edge 1->0 means setting graph[1][0] = 1, check variable_tracker for similar updates

Concept Snapshot

Adjacency Matrix Representation:
- Use NxN matrix for N nodes
- Initialize all cells to 0 (no edges)
- For edge u->v, set matrix[u][v] = 1
- For undirected graphs, also set matrix[v][u] = 1
- Easy to check if edge exists by matrix[u][v]
- Uses O(N^2) space regardless of edges

Full Transcript

Adjacency matrix representation uses a square matrix to show connections between nodes. We start by creating an NxN matrix filled with zeros, meaning no edges. Then for each edge from node u to node v, we set matrix[u][v] to 1. This marks the presence of that edge. The matrix rows represent start nodes and columns represent end nodes, so direction is clear. The execution table shows step-by-step how edges are added and how the matrix changes. This method uses more space but makes checking edges very fast.

Practice

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

easy

A. A 2D array showing connections between nodes

B. A list of nodes in the graph

C. A sequence of edges in order

D. A tree structure of nodes

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 an edge exists between two nodes (1 for connected, 0 for not).

3. Final Answer:

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

4. Quick Check:

   Adjacency matrix = 2D array [OK]

Hint: Adjacency matrix is always a 2D grid of node connections [OK]

Common Mistakes:

• Confusing adjacency matrix with adjacency list
• Thinking it stores node values instead of edges
• Assuming it is a sequence or tree

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

easy

A. int matrix[4];

B. int matrix[4][4];

C. int matrix[];

D. int matrix[4,4];

Solution

1. Step 1: Recall C array declaration syntax

   In C, a 2D array is declared as type name[rows][columns].

2. Step 2: Match syntax for 4x4 matrix

   For 4 rows and 4 columns, it is int matrix[4][4];

3. Final Answer:

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

4. Quick Check:

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

Hint: Use int matrix[rows][columns] for 2D arrays in C [OK]

Common Mistakes:

• Using single dimension array for matrix
• Using comma inside brackets (invalid syntax)
• Not specifying both dimensions

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

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

Which nodes are directly connected to node 1 (index 1)?

medium

A. [1, 2]

B. [0, 1]

C. [0, 2]

D. [2]

Solution

1. Step 1: Identify row for node 1

   Node 1 corresponds to index 1, so look at matrix[1]: {1, 0, 1}.

2. Step 2: Find indices with value 1

   Positions 0 and 2 have 1, meaning node 1 connects to nodes 0 and 2.

3. Final Answer:

   [0, 2] -> Option C

4. Quick Check:

   matrix[1][0] and matrix[1][2] = 1 [OK]

Hint: Check the row of the node for 1s to find connections [OK]

Common Mistakes:

• Confusing row and column indices
• Including the node itself as connected
• Reading zeros as connections

4. Consider this code snippet to initialize a 3x3 adjacency matrix in C:

int matrix[3][3];
for (int i = 0; i < 3; i++) {
  for (int j = 0; j < 3; j++) {
    matrix[i][j] = 0;
  }
}
matrix[1][3] = 1;

What is the error in this code?

medium

A. Accessing out-of-bounds index matrix[1][3]

B. Missing semicolon after for loop

C. Incorrect initialization of matrix elements

D. Using wrong data type for matrix

Solution

1. Step 1: Check loop ranges and matrix size

   Matrix is 3x3, so valid indices are 0 to 2 for both rows and columns.

2. Step 2: Identify invalid index usage

   matrix[1][3] tries to access column index 3, which is out of bounds.

3. Final Answer:

   Accessing out-of-bounds index matrix[1][3] -> Option A

4. Quick Check:

   Index 3 invalid for size 3 array [OK]

Hint: Array indices go from 0 to size-1; check carefully [OK]

Common Mistakes:

• Ignoring array bounds and using invalid indices
• Assuming loops fix out-of-range errors
• Confusing row and column indices

5. You have a directed graph with 4 nodes. The adjacency matrix is:

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

Which nodes have no incoming edges?

hard

A. [0]

B. [0, 3]

C. [1, 3]

D. [3]

Solution

1. Step 1: Understand incoming edges in adjacency matrix

   Incoming edges to a node are shown by 1s in that node's column.

2. Step 2: Check each column for 1s

   Column 0 has 1 at row 2 (node 2 -> node 0).
   Column 1 has 1 at row 0 (node 0 -> node 1).
   Column 2 has 1 at row 1 (node 1 -> node 2).
   Column 3 has no 1s (all 0s).

3. Step 3: Identify nodes with no incoming edges

   Nodes 1 and 3 have no incoming edges because column 1 has 1 at row 0 (so node 1 has incoming edge), so this is incorrect. Actually, column 1 has 1 at row 0, so node 1 has incoming edge. Column 3 has no 1s, so node 3 has no incoming edges. Node 0 has incoming edge from node 2. Node 2 has incoming edge from node 1. So only node 3 has no incoming edges.

4. Final Answer:

   [3] -> Option D

5. Quick Check:

   Column 3 all 0s [OK]

Hint: Look down columns to find incoming edges for each node [OK]

Common Mistakes:

• Checking rows instead of columns for incoming edges
• Confusing directed and undirected edges
• Missing edges from nodes to themselves