Adjacency List Representation in DSA C# - Build from Scratch

Adjacency List Representation

📖 Scenario: Imagine you are building a simple map of cities connected by roads. Each city can have roads to other cities. We want to store this map in a way that shows which cities connect to which.

🎯 Goal: Create an adjacency list to represent the connections between cities. Then, display the connections clearly.

📋 What You'll Learn

Create a dictionary called graph where keys are city names (strings) and values are lists of connected city names (strings).

Add a configuration variable called startCity to select a city to explore.

Write code to get the list of cities connected to startCity from the graph dictionary.

Print the connections from startCity in the format: CityA -> CityB, CityC, CityD.

💡 Why This Matters

🌍 Real World

Adjacency lists are used to represent networks like maps, social connections, or computer networks efficiently.

💼 Career

Understanding adjacency lists is important for roles involving graph algorithms, network analysis, and data structure optimization.

1

Create the adjacency list dictionary

Create a dictionary called graph with these exact entries: "A" connected to ["B", "C"], "B" connected to ["A", "D"], and "C" connected to ["A", "D"].

DSA C#

# Create the graph dictionary with city connections
# Your code here

Hint

Use Dictionary<string, List<string>> and initialize it with the given city connections.

2

Add a start city variable

Add a string variable called startCity and set it to "A".

DSA C#

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        Dictionary> graph = new Dictionary>
        {
            { "A", new List { "B", "C" } },
            { "B", new List { "A", "D" } },
            { "C", new List { "A", "D" } }
        };

        // Add the startCity variable here
        # Your code here
    }
}

Hint

Declare startCity as a string and assign it the value "A".

3

Get connected cities for the start city

Create a variable called connectedCities and set it to the list of cities connected to startCity from the graph dictionary.

DSA C#

        List connectedCities = graph[startCity];
        // Print the connections

Hint

Use graph[startCity] to get the list of connected cities.

4

Print the connections from the start city

Print the connections from startCity in the format: A -> B, C using Console.WriteLine.

DSA C#

Hint

Use Console.WriteLine with string interpolation and string.Join to format the output.

Practice

1. What does an adjacency list represent in graph data structures?

easy

A. A list of all nodes without connections

B. A list where each node stores its connected neighbors

C. A matrix showing distances between nodes

D. A queue used for graph traversal

Solution

1. Step 1: Understand adjacency list concept

   An adjacency list stores each node with a list of its neighbors, showing direct connections.

2. Step 2: Compare with other options

   Other options describe different structures: matrix, isolated nodes, or traversal tools, not adjacency lists.

3. Final Answer:

   A list where each node stores its connected neighbors -> Option B

4. Quick Check:

   Adjacency list = neighbors list [OK]

Hint: Adjacency list always links nodes to their neighbors [OK]

Common Mistakes:

• Confusing adjacency list with adjacency matrix
• Thinking adjacency list stores distances
• Mixing adjacency list with traversal queues

2. Which C# syntax correctly declares an adjacency list for a graph with integer nodes?

easy

A. Dictionary adjacencyList = new Dictionary();

B. List<int> adjacencyList = new List<int>();

C. Dictionary adjacencyList = new Dictionary();

D. int[][] adjacencyList = new int[5][];

Solution

1. Step 1: Identify adjacency list structure

   An adjacency list maps each node (int) to a list of connected nodes (List<int>), so Dictionary fits.

2. Step 2: Check other options

   List<int> adjacencyList = new List<int>(); is a simple list, not mapping nodes to neighbors. int[][] adjacencyList = new int[5][]; is an array of arrays, possible but less flexible. Dictionary adjacencyList = new Dictionary(); maps int to int, not to a list.

3. Final Answer:

   Dictionary<int, List<int>> adjacencyList = new Dictionary<int, List<int>>(); -> Option C

4. Quick Check:

   Use Dictionary with List for adjacency list [OK]

Hint: Use Dictionary for adjacency lists in C# [OK]

Common Mistakes:

• Using List<int> alone without mapping nodes
• Using Dictionary instead of list of neighbors
• Confusing jagged arrays with adjacency lists

3. Given the following C# code, what is the output?

var graph = new Dictionary();
graph[1] = new List<int> {2, 3};
graph[2] = new List<int> {1};
graph[3] = new List<int> {1};

foreach(var node in graph)
{
    Console.Write(node.Key + ": ");
    foreach(var neighbor in node.Value)
    {
        Console.Write(neighbor + " ");
    }
    Console.WriteLine();
}

medium

A. 1: 2 3
2: 1
3: 1

B. 1: 1 2 3
2: 1
3: 1

C. 1: 2 3
2: 2
3: 3

D. 1:
2:
3:

Solution

1. Step 1: Analyze graph initialization

   Node 1 connects to 2 and 3; node 2 connects to 1; node 3 connects to 1.

2. Step 2: Trace output loop

   For each node, print key and neighbors separated by spaces. So output lines are: "1: 2 3 " "2: 1 " "3: 1 "

3. Final Answer:

   1: 2 3 2: 1 3: 1 -> Option A

4. Quick Check:

   Print node keys with their neighbors [OK]

Hint: Print keys with their neighbor lists exactly as stored [OK]

Common Mistakes:

• Printing node itself as neighbor
• Missing spaces between neighbors
• Printing empty neighbor lists

4. Identify the error in this adjacency list code snippet and select the fix:

var graph = new Dictionary();
graph[1].Add(2);
graph[1].Add(3);

medium

A. Initialize graph[1] with a new List<int> before adding neighbors

B. Change Dictionary to Dictionary

C. Use graph.Add(1, 2) instead of graph[1].Add(2)

D. Remove the Add calls; just declare graph

Solution

1. Step 1: Understand dictionary initialization

   graph[1] is not initialized with a list, so calling Add on null causes error.

2. Step 2: Fix by initializing list

   Assign graph[1] = new List<int>() before adding neighbors fixes the null reference error.

3. Final Answer:

   Initialize graph[1] with a new List<int> before adding neighbors -> Option A

4. Quick Check:

   Initialize list before adding elements [OK]

Hint: Always create list before adding neighbors [OK]

Common Mistakes:

• Trying to add to null list
• Changing dictionary type incorrectly
• Using Add method wrongly on dictionary

5. You have a graph represented by an adjacency list: Dictionary. How would you add an undirected edge between nodes 4 and 5?

hard

A. Add a new dictionary entry with key 4 and value 5

B. Add 5 to node 4's list only

C. Add 4 to node 5's list only

D. Add 5 to node 4's list and 4 to node 5's list

Solution

1. Step 1: Understand undirected edge meaning

   Undirected edge means both nodes connect to each other, so both lists must include the other node.

2. Step 2: Add neighbors to both nodes

   Add 5 to node 4's neighbor list and 4 to node 5's neighbor list to represent the edge correctly.

3. Final Answer:

   Add 5 to node 4's list and 4 to node 5's list -> Option D

4. Quick Check:

   Undirected edge = mutual neighbor entries [OK]

Hint: Add neighbors both ways for undirected edges [OK]

Common Mistakes:

• Adding edge only one way
• Adding wrong node to list
• Using dictionary entry incorrectly