Adjacency Matrix Representation in DSA C++ - Build from Scratch

Adjacency Matrix Representation

📖 Scenario: You are working on a simple social network where each person can be friends with others. We want to represent these friendships using a matrix where rows and columns represent people, and the value at each position shows if two people are friends.

🎯 Goal: Build an adjacency matrix to represent friendships between 4 people. Then, check if two specific people are friends.

📋 What You'll Learn

Create a 4x4 adjacency matrix with exact friendship connections

Add a variable to store the number of people

Write code to check if person 1 and person 3 are friends

Print the result as 1 (friends) or 0 (not friends)

💡 Why This Matters

🌍 Real World

Adjacency matrices are used in social networks, maps, and computer networks to represent connections clearly and quickly.

💼 Career

Understanding adjacency matrices helps in roles involving graph algorithms, network analysis, and data structure optimization.

1

Create the adjacency matrix

Create a 2D integer array called adjMatrix with 4 rows and 4 columns. Initialize it with these exact values: row 0: {0, 1, 0, 0}, row 1: {1, 0, 1, 1}, row 2: {0, 1, 0, 0}, row 3: {0, 1, 0, 0}.

DSA C++

// Your code here

Hint

Use a 2D array with 4 rows and 4 columns. Each row is enclosed in curly braces with commas separating values.

2

Add the number of people variable

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

DSA C++

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

Hint

Just create a simple integer variable and assign 4 to it.

3

Check friendship between person 1 and person 3

Create an integer variable called areFriends and set it to the value in adjMatrix[1][3].

DSA C++

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

int numPeople = 4;
// Your code here

Hint

Access the matrix at row 1 and column 3 to get the friendship value.

4

Print the friendship result

Write a std::cout statement to print the value of areFriends.

DSA C++

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

int numPeople = 4;

int areFriends = adjMatrix[1][3];
// Your code here

Hint

Use std::cout << areFriends << std::endl; to print the result.

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