Adjacency List Representation in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of adjacency list after adding edges

What is the printed adjacency list after running the following C# code?

DSA C#

using System;
using System.Collections.Generic;

class Graph {
    public Dictionary<int, List<int>> adjList = new Dictionary<int, List<int>>();

    public void AddEdge(int u, int v) {
        if (!adjList.ContainsKey(u)) adjList[u] = new List<int>();
        adjList[u].Add(v);
    }

    public void PrintGraph() {
        foreach (var node in adjList) {
            Console.Write(node.Key + " -> ");
            foreach (var neighbor in node.Value) {
                Console.Write(neighbor + " -> ");
            }
            Console.WriteLine("null");
        }
    }
}

class Program {
    static void Main() {
        Graph g = new Graph();
        g.AddEdge(1, 2);
        g.AddEdge(1, 3);
        g.AddEdge(2, 4);
        g.AddEdge(3, 4);
        g.PrintGraph();
    }
}

A {"1": "2 -> 3 -> null", "2": "4 -> null", "3": "null"}

B {"1": "2 -> 3 -> null", "2": "4 -> null", "3": "4 -> null"}

C {"1": "2 -> 3 -> null", "2": "null", "3": "4 -> null"}

D {"1": "3 -> 2 -> null", "2": "4 -> null", "3": "4 -> null"}

💡 Hint

Check the order in which edges are added to each node's adjacency list.

The adjacency list stores neighbors in the order edges are added. Node 1 has neighbors 2 and 3, node 2 has neighbor 4, and node 3 has neighbor 4.

❓ Predict Output

intermediate

Adjacency list after adding undirected edges

What is the output adjacency list after running this C# code that adds undirected edges?

DSA C#

using System;
using System.Collections.Generic;

class Graph {
    public Dictionary<int, List<int>> adjList = new Dictionary<int, List<int>>();

    public void AddUndirectedEdge(int u, int v) {
        if (!adjList.ContainsKey(u)) adjList[u] = new List<int>();
        if (!adjList.ContainsKey(v)) adjList[v] = new List<int>();
        adjList[u].Add(v);
        adjList[v].Add(u);
    }

    public void PrintGraph() {
        foreach (var node in adjList) {
            Console.Write(node.Key + " -> ");
            foreach (var neighbor in node.Value) {
                Console.Write(neighbor + " -> ");
            }
            Console.WriteLine("null");
        }
    }
}

class Program {
    static void Main() {
        Graph g = new Graph();
        g.AddUndirectedEdge(1, 2);
        g.AddUndirectedEdge(1, 3);
        g.AddUndirectedEdge(2, 4);
        g.PrintGraph();
    }
}

A {"1": "2 -> 3 -> null", "2": "4 -> null", "3": "1 -> null", "4": "2 -> null"}

B {"1": "3 -> 2 -> null", "2": "4 -> 1 -> null", "3": "1 -> null", "4": "2 -> null"}

C {"1": "2 -> 3 -> null", "2": "1 -> 4 -> null", "3": "1 -> null", "4": "2 -> null"}

D {"1": "2 -> 3 -> null", "2": "1 -> null", "3": "1 -> null", "4": "2 -> null"}

💡 Hint

Remember undirected edges add neighbors both ways.

Each undirected edge adds neighbors to both nodes. Node 1 connects to 2 and 3, node 2 connects to 1 and 4, etc.

🔧 Debug

advanced

Identify the error in adjacency list insertion

What error will this C# code produce when adding edges to the adjacency list?

DSA C#

using System;
using System.Collections.Generic;

class Graph {
    public Dictionary<int, List<int>> adjList = new Dictionary<int, List<int>>();

    public void AddEdge(int u, int v) {
        adjList[u].Add(v);
    }
}

class Program {
    static void Main() {
        Graph g = new Graph();
        g.AddEdge(1, 2);
    }
}

A InvalidOperationException because List<int> is empty

B NullReferenceException because adjList is null

C No error, adjacency list updated correctly

D KeyNotFoundException because key 1 does not exist in adjList

💡 Hint

Check if the dictionary contains the key before adding to the list.

The code tries to add to a list at key 1 without initializing the list first, causing a KeyNotFoundException.

❓ Predict Output

advanced

Adjacency list after removing an edge

What is the adjacency list output after removing edge 1->3 from this graph?

DSA C#

using System;
using System.Collections.Generic;

class Graph {
    public Dictionary<int, List<int>> adjList = new Dictionary<int, List<int>>();

    public void AddEdge(int u, int v) {
        if (!adjList.ContainsKey(u)) adjList[u] = new List<int>();
        adjList[u].Add(v);
    }

    public void RemoveEdge(int u, int v) {
        if (adjList.ContainsKey(u)) {
            adjList[u].Remove(v);
        }
    }

    public void PrintGraph() {
        foreach (var node in adjList) {
            Console.Write(node.Key + " -> ");
            foreach (var neighbor in node.Value) {
                Console.Write(neighbor + " -> ");
            }
            Console.WriteLine("null");
        }
    }
}

class Program {
    static void Main() {
        Graph g = new Graph();
        g.AddEdge(1, 2);
        g.AddEdge(1, 3);
        g.AddEdge(2, 4);
        g.RemoveEdge(1, 3);
        g.PrintGraph();
    }
}

A {"1": "2 -> null", "2": "4 -> null"}

B {"1": "3 -> 2 -> null", "2": "4 -> null"}

C {"1": "2 -> 3 -> null", "2": "4 -> null"}

D {"1": "null", "2": "4 -> null"}

💡 Hint

Removing edge 1->3 deletes 3 from node 1's neighbors.

After removal, node 1's adjacency list no longer contains 3, only 2 remains.

❓ Predict Output

expert

Output after BFS traversal using adjacency list

What is the order of nodes printed by this BFS traversal starting from node 1?

DSA C#

using System;
using System.Collections.Generic;

class Graph {
    public Dictionary<int, List<int>> adjList = new Dictionary<int, List<int>>();

    public void AddEdge(int u, int v) {
        if (!adjList.ContainsKey(u)) adjList[u] = new List<int>();
        adjList[u].Add(v);
    }

    public void BFS(int start) {
        Queue<int> queue = new Queue<int>();
        HashSet<int> visited = new HashSet<int>();
        queue.Enqueue(start);
        visited.Add(start);

        while (queue.Count > 0) {
            int node = queue.Dequeue();
            Console.Write(node + " ");
            if (adjList.ContainsKey(node)) {
                foreach (var neighbor in adjList[node]) {
                    if (!visited.Contains(neighbor)) {
                        queue.Enqueue(neighbor);
                        visited.Add(neighbor);
                    }
                }
            }
        }
    }
}

class Program {
    static void Main() {
        Graph g = new Graph();
        g.AddEdge(1, 2);
        g.AddEdge(1, 3);
        g.AddEdge(2, 4);
        g.AddEdge(3, 5);
        g.AddEdge(4, 6);
        g.BFS(1);
    }
}

A "1 2 3 4 5 6 "

B "1 3 2 5 4 6 "

C "1 2 3 5 4 6 "

D "1 2 3 4 6 5 "

💡 Hint

BFS visits neighbors level by level in the order they appear in adjacency list.

BFS starts at 1, visits neighbors 2 and 3, then their neighbors 4, 5, and finally 6.

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