Adjacency Matrix Representation in DSA C - Build from Scratch

Adjacency Matrix Representation

📖 Scenario: You are working on a simple program to represent a small network of cities connected by roads. Each city is a node, and roads are connections between them. You will use an adjacency matrix to show which cities are directly connected.

🎯 Goal: Build a program that creates an adjacency matrix for 4 cities, sets up connections between them, and then prints the matrix to show the connections.

📋 What You'll Learn

Create a 4x4 integer matrix called adjMatrix initialized with zeros

Create an integer variable numCities and set it to 4

Set specific connections between cities by updating adjMatrix

Print the adjacency matrix in a readable format

💡 Why This Matters

🌍 Real World

Adjacency matrices are used in computer networks, social networks, and maps to represent direct connections between points.

💼 Career

Understanding adjacency matrices helps in roles involving graph algorithms, network analysis, and software development for mapping and routing.

1

Create the adjacency matrix

Create a 4x4 integer matrix called adjMatrix initialized with zeros.

DSA C

# Your code here

Hint

Use nested braces to initialize all elements to zero.

2

Add the number of cities

Create an integer variable called numCities and set it to 4.

DSA C

int adjMatrix[4][4] = { {0, 0, 0, 0},
                      {0, 0, 0, 0},
                      {0, 0, 0, 0},
                      {0, 0, 0, 0} };
# Your code here

Hint

Just create a simple integer variable with the value 4.

3

Set connections between cities

Set the following connections in adjMatrix: city 0 connected to city 1 and city 2, city 1 connected to city 2, and city 2 connected to city 3. Use adjMatrix[row][column] = 1; to mark connections.

DSA C

int adjMatrix[4][4] = { {0, 0, 0, 0},
                      {0, 0, 0, 0},
                      {0, 0, 0, 0},
                      {0, 0, 0, 0} };
int numCities = 4;
# Your code here

Hint

Assign 1 to the correct positions in the matrix to show connections.

4

Print the adjacency matrix

Use nested for loops with variables i and j to print the adjMatrix in matrix form. Print each element followed by a space, and print a new line after each row.

DSA C

int adjMatrix[4][4] = { {0, 0, 0, 0},
                      {0, 0, 0, 0},
                      {0, 0, 0, 0},
                      {0, 0, 0, 0} };
int numCities = 4;
adjMatrix[0][1] = 1;
adjMatrix[0][2] = 1;
adjMatrix[1][2] = 1;
adjMatrix[2][3] = 1;
// Your code here

Hint

Use two loops to go through rows and columns, printing each value with a space, then a new line after each row.

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