Adjacency List vs Matrix When to Choose Which in DSA C# - Build Both Approaches

Adjacency List vs Matrix When to Choose Which

📖 Scenario: You are working on a simple social network app where users can be friends with each other. You want to represent the friendship connections between users using graphs.There are two common ways to represent these connections: adjacency list and adjacency matrix. Each has its own advantages depending on the number of users and connections.

🎯 Goal: Build two graph representations for the same set of users and their friendships: an adjacency list and an adjacency matrix. Learn when to use each representation by comparing their structures.

📋 What You'll Learn

Create an adjacency list for 4 users with given friendships

Create an adjacency matrix for the same 4 users

Use a variable to store the number of users

Print both the adjacency list and adjacency matrix to see their structure

💡 Why This Matters

🌍 Real World

Graphs are used in social networks, maps, and recommendation systems to represent connections between entities.

💼 Career

Understanding graph representations helps in roles like software development, data science, and network engineering where efficient data structures are key.

1

Create the adjacency list for 4 users

Create a dictionary called adjacencyList where keys are integers 0 to 3 representing users, and values are lists of integers representing friends. Use these exact friendships: user 0 is friends with 1 and 2, user 1 is friends with 0 and 3, user 2 is friends with 0, user 3 is friends with 1.

DSA C#

# Create the adjacency list dictionary with the given friendships
# Your code here

Hint

Use a Dictionary<int, List<int>> to represent the adjacency list. Each key is a user number, and the value is a list of friends.

2

Create a variable for the number of users

Create an integer variable called numUsers and set it to 4 to represent the total number of users.

DSA C#

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        Dictionary> adjacencyList = new Dictionary>
        {
            {0, new List {1, 2}},
            {1, new List {0, 3}},
            {2, new List {0}},
            {3, new List {1}}
        };

        // Create the numUsers variable
        // Your code here
    }
}

Hint

Just create an integer variable numUsers and assign it the value 4.

3

Create the adjacency matrix for the same users

Create a 2D integer array called adjacencyMatrix of size numUsers by numUsers. Fill it with 0s and 1s to represent the same friendships: 1 means friends, 0 means no friendship. Use these exact connections: user 0 friends with 1 and 2, user 1 friends with 0 and 3, user 2 friends with 0, user 3 friends with 1.

DSA C#

        int[,] adjacencyMatrix = new int[numUsers, numUsers]
            {0, 1, 1, 0},
            {1, 0, 0, 1},
            {1, 0, 0, 0},
            {0, 1, 0, 0}
        // Print adjacency list and matrix

Hint

Use a 2D array int[,] adjacencyMatrix with rows and columns equal to numUsers. Fill rows with 0s and 1s to show friendships.

4

Print both adjacency list and adjacency matrix

Print the adjacency list by iterating over adjacencyList and printing each user and their friends. Then print the adjacency matrix row by row. Use Console.WriteLine for output.

DSA C#

Hint

Use a foreach loop to print the adjacency list. Use nested for loops to print the adjacency matrix rows.

Practice

1. Which data structure is generally better for representing a graph with many nodes but very few edges?

easy

A. Adjacency List

B. Adjacency Matrix

C. Array

D. Stack

Solution

1. Step 1: Understand graph density

   A graph with many nodes but few edges is called a sparse graph.

2. Step 2: Choose data structure for sparse graph

   Adjacency List stores only existing edges, saving space for sparse graphs.

3. Final Answer:

   Adjacency List -> Option A

4. Quick Check:

   Sparse graph = Adjacency List [OK]

Hint: Sparse graph? Use adjacency list for space efficiency [OK]

Common Mistakes:

• Choosing adjacency matrix for sparse graphs wastes space
• Confusing sparse with dense graphs
• Thinking arrays or stacks represent graphs directly

2. Which of the following is the correct way to declare an adjacency matrix for a graph with 4 nodes in C#?

easy

A. int[][] adjacencyMatrix = new int[4][]; for(int i=0; i<4; i++) adjacencyMatrix[i] = new int[4];

B. int adjacencyMatrix = new int[4];

C. List<int>[] adjacencyMatrix = new List<int>[4];

D. int[,] adjacencyMatrix = new int[4,4];

Solution

1. Step 1: Identify adjacency matrix type

   An adjacency matrix is a 2D array representing edges between nodes.

2. Step 2: Check C# syntax for 2D arrays

   In C#, 2D arrays use syntax like int[,] array = new int[rows, columns];

3. Final Answer:

   int[,] adjacencyMatrix = new int[4,4]; -> Option D

4. Quick Check:

   2D array syntax = int[,] [OK]

Hint: Adjacency matrix uses 2D array syntax int[,] [OK]

Common Mistakes:

• Using jagged arrays instead of 2D arrays for matrix
• Declaring adjacencyMatrix as a single int
• Using List<int>[] which is adjacency list, not matrix

3. Given the following adjacency list representation of a graph in C#:

var graph = new List<int>[] {
  new List<int>{1, 2},
  new List<int>{2},
  new List<int>{0}
};
Console.WriteLine(graph[0][1]);

What will be the output?

medium

A. 0

B. 1

C. 2

D. IndexOutOfRangeException

Solution

1. Step 1: Understand the adjacency list structure

   graph[0] = List<int>{1, 2}, so graph[0][1] accesses the second element which is 2.

2. Step 2: Identify the output of Console.WriteLine(graph[0][1])

   It prints the value 2 from the list at index 1 of graph[0].

3. Final Answer:

   2 -> Option C

4. Quick Check:

   graph[0][1] = 2 [OK]

Hint: Indexing starts at 0; graph[0][1] is second element in first list [OK]

Common Mistakes:

• Confusing indices and printing 1 instead of 2
• Expecting an error due to nested lists
• Thinking graph[0][1] accesses graph[1]

4. Consider this adjacency matrix code snippet in C#:

int[,] matrix = new int[3,3];
matrix[0,1] = 1;
matrix[1,2] = 1;
matrix[2,0] = 1;
Console.WriteLine(matrix[1,0]);

What is the output and why?

medium

A. 1 because matrix is symmetric

B. 0 because matrix[1,0] was never set

C. Runtime error due to invalid index

D. 1 because of default initialization

Solution

1. Step 1: Analyze matrix assignments

   Only matrix[0,1], matrix[1,2], and matrix[2,0] are set to 1; matrix[1,0] remains 0.

2. Step 2: Understand default values in int[] arrays

   Unassigned int elements default to 0 in C#.

3. Final Answer:

   0 because matrix[1,0] was never set -> Option B

4. Quick Check:

   Unset matrix elements = 0 [OK]

Hint: Unset matrix cells default to 0, not symmetric [OK]

Common Mistakes:

• Assuming adjacency matrix is symmetric by default
• Expecting runtime error for valid indices
• Confusing default values with assigned values

5. You need to represent a social network graph with 10,000 users where each user has on average 10 friends. Which representation is best and why? Choose between adjacency list and adjacency matrix.

hard

A. Adjacency list, because it uses less memory for sparse graphs

B. Adjacency matrix, because it allows quick edge checks

C. Adjacency matrix, because it is simpler to implement

D. Adjacency list, because it stores all possible edges

Solution

1. Step 1: Calculate graph density

   10,000 users with 10 friends each means about 100,000 edges, which is sparse compared to 100 million possible edges.

2. Step 2: Choose data structure for sparse graph

   Adjacency list stores only existing edges, saving huge memory compared to adjacency matrix.

3. Final Answer:

   Adjacency list, because it uses less memory for sparse graphs -> Option A

4. Quick Check:

   Sparse large graph = adjacency list [OK]

Hint: Large sparse graph? Use adjacency list for memory efficiency [OK]

Common Mistakes:

• Choosing adjacency matrix despite huge memory waste
• Thinking adjacency matrix is always simpler
• Misunderstanding adjacency list stores only existing edges