Adjacency List Representation in DSA C# - Execution Trace

Concept Flow - Adjacency List Representation

Start

↓

Create empty adjacency list

↓

For each edge (u,v)

↓

Add v to u's list

↓

Add u to v's list (if undirected)

↓

Repeat for all edges

↓

Adjacency list ready

Build adjacency list by adding each edge's nodes to each other's lists for undirected graphs.

Execution Sample

DSA C#

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

Creates adjacency list for graph with edges 1-2 and 1-3.

Execution Table

Step	Operation	Edge Processed	Adjacency List State	Visual State
1	Initialize empty adjacency list	None	{}	{}
2	Add edge 1-2	(1,2)	{1: [2], 2: [1]}	1 -> 2 2 -> 1
3	Add edge 1-3	(1,3)	{1: [2, 3], 2: [1], 3: [1]}	1 -> 2 -> 3 2 -> 1 3 -> 1
4	No more edges	None	{1: [2, 3], 2: [1], 3: [1]}	1 -> 2 -> 3 2 -> 1 3 -> 1

💡 All edges processed, adjacency list complete.

Variable Tracker

Variable	Start	After Step 2	After Step 3	Final
graph	{}	{1: [2], 2: [1]}	{1: [2, 3], 2: [1], 3: [1]}	{1: [2, 3], 2: [1], 3: [1]}

Key Moments - 3 Insights

Why do we add node 2 to node 1's list and also node 1 to node 2's list?

Because the graph is undirected, each edge connects two nodes both ways. See execution_table rows 2 and 3 where both directions are added.

What happens if we forget to initialize a node's list before adding neighbors?

The code will fail because you can't add to a list that doesn't exist. In the execution_table, step 2 shows initialization happens when adding first edge.

How does the adjacency list visually represent connections?

Each node points to a list of connected nodes. The Visual State column shows arrows from each node to its neighbors, like '1 -> 2 -> 3'.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what nodes are connected to node 1?

A [1, 3]

B [2, 3]

C [2]

D [3]

💡 Hint

Check the 'Adjacency List State' column at step 3.

At which step does node 3 first appear in the adjacency list?

A Step 3

B Step 2

C Step 1

D Step 4

💡 Hint

Look for when '3' is added as a key in the adjacency list in execution_table.

If the graph was directed from 1 to 2 only, how would the adjacency list change at step 2?

A {1: [2], 2: [1]}

B {1: [], 2: [1]}

C {1: [2], 2: []}

D {1: [], 2: []}

💡 Hint

Directed means only one direction edge, check adjacency list after step 2.

Concept Snapshot

Adjacency List Representation:
- Use a dictionary/map: node -> list of neighbors
- For each edge (u,v), add v to u's list
- For undirected graphs, add u to v's list too
- Efficient for sparse graphs
- Visual: each node points to connected nodes

Full Transcript

Adjacency List Representation stores graph connections by mapping each node to a list of its neighbors. We start with an empty dictionary. For each edge, we add the connected nodes to each other's lists if the graph is undirected. This builds a structure where each node points to its connected nodes. The execution table shows step-by-step how edges are added and how the adjacency list grows. Key points include adding both directions for undirected graphs and initializing lists before adding neighbors. The visual state shows arrows from nodes to their neighbors, helping understand the graph structure.

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