Why Graphs Exist and What Trees Cannot Model in DSA C# - Challenge Your Understanding

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Graph Representation with Cycles

Consider the following C# code that creates a graph with cycles. What will be the printed adjacency list after adding all edges?

DSA C#

using System;
using System.Collections.Generic;

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

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

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

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

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

B {"1": [2], "2": [3], "3": [4]}

C {"1": [2], "2": [3], "3": [1, 4]}

D {"1": [2], "2": [3], "3": [1, 2, 4]}

💡 Hint

Look carefully at all edges added, especially the one creating a cycle.

The graph has edges 1->2, 2->3, 3->1 (cycle), and 3->4. So node 3 has neighbors 1 and 4.

🧠 Conceptual

intermediate

Why Trees Cannot Model Cyclic Relationships

Which of the following statements best explains why trees cannot represent cyclic relationships?

A Trees have a hierarchical structure with no cycles, so they cannot represent nodes connected in a loop.

B Trees allow multiple parents for a node, which prevents cycles.

C Trees store data in arrays, which cannot represent cycles.

D Trees use hash tables internally, which do not support cycles.

💡 Hint

Think about the definition of a tree and what a cycle means.

By definition, trees are acyclic connected graphs. Cycles violate the tree property.

🔧 Debug

advanced

Identifying the Error in Tree vs Graph Modeling

Given the following code snippet intended to model a graph with cycles, what error will occur if we try to use a TreeNode class designed for trees?

DSA C#

class TreeNode {
    public int val;
    public List<TreeNode> children = new List<TreeNode>();
    public TreeNode(int v) { val = v; }
}

// Attempt to create a cycle
TreeNode a = new TreeNode(1);
TreeNode b = new TreeNode(2);
a.children.Add(b);
b.children.Add(a); // creates cycle

A No error; cycles are allowed in this structure.

B StackOverflowException during traversal due to infinite recursion.

C Compile-time error because List<TreeNode> cannot contain parent nodes.

D NullReferenceException because of missing initialization.

💡 Hint

Think about what happens if you traverse this structure recursively.

The cycle causes infinite recursion during traversal, leading to stack overflow.

🚀 Application

advanced

Choosing Data Structure for Social Network Modeling

You want to model a social network where users can follow each other, including mutual follows (cycles). Which data structure is best suited for this?

A Graph, because it can represent cycles and multiple connections.

B Tree, because it naturally models parent-child relationships.

C Array, because it stores elements sequentially.

D Stack, because it manages last-in-first-out order.

💡 Hint

Consider if cycles and multiple connections are possible in the network.

Graphs can represent complex relationships including cycles and multiple edges, unlike trees.

❓ Predict Output

expert

Output of Graph Traversal Showing Cycle Detection

What will be the output of the following C# code that performs DFS on a graph with a cycle and detects it?

DSA C#

using System;
using System.Collections.Generic;

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

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

    public bool DFS(int node, HashSet<int> visited, HashSet<int> recStack) {
        if (recStack.Contains(node)) {
            Console.WriteLine("Cycle detected at node " + node);
            return true;
        }
        if (visited.Contains(node)) return false;

        visited.Add(node);
        recStack.Add(node);

        if (adj.ContainsKey(node)) {
            foreach (var neighbor in adj[node]) {
                if (DFS(neighbor, visited, recStack)) return true;
            }
        }

        recStack.Remove(node);
        return false;
    }
}

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

        bool hasCycle = g.DFS(1, new HashSet<int>(), new HashSet<int>());
        if (!hasCycle) Console.WriteLine("No cycle detected");
    }
}

A No cycle detected

B Cycle detected at node 4

C Cycle detected at node 3

D Cycle detected at node 2

💡 Hint

Look at where the recursion stack detects a repeated node first.

The cycle is detected when node 2 is revisited in the recursion stack.

Practice

1. Why do we need graphs when we already have trees in data structures?

easy

A. Because graphs can model relationships where nodes have multiple connections, unlike trees.

B. Because trees are faster to traverse than graphs.

C. Because graphs use less memory than trees.

D. Because trees cannot store any data.

Solution

1. Step 1: Understand tree structure limitations

   Trees have a strict hierarchy where each node has only one parent, so they cannot represent multiple connections between nodes.

2. Step 2: Understand graph capabilities

   Graphs allow nodes to connect to multiple other nodes without hierarchy, modeling complex relationships like social networks or maps.

3. Final Answer:

   Because graphs can model relationships where nodes have multiple connections, unlike trees. -> Option A

4. Quick Check:

   Graphs model multiple connections [OK]

Hint: Graphs allow many connections per node; trees do not. [OK]

Common Mistakes:

• Thinking trees can have multiple parents per node
• Confusing memory use between trees and graphs
• Assuming trees cannot store data

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

easy

A. Dictionary graph = new Dictionary();

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

C. int[] graph = new int[10];

D. Dictionary graph = new Dictionary();

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 is suitable.

2. Step 2: Check other options

   List<int> alone cannot map nodes to neighbors; int[] is a fixed array, not a map; Dictionary maps to single int, not list.

3. Final Answer:

   Dictionary graph = new Dictionary(); -> Option D

4. Quick Check:

   Adjacency list = Dictionary with List values [OK]

Hint: Adjacency list uses Dictionary with List values. [OK]

Common Mistakes:

• Using List<int> without mapping keys
• Using Dictionary instead of List<int>
• Using fixed-size arrays for adjacency

3. What will be the output of the following C# code snippet modeling a graph?

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

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: 4
4: 3

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

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

D. 1: 2 3
2: 3
3: 1 4
4: 3

Solution

1. Step 1: Understand graph dictionary entries

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

2. Step 2: Trace the output loop

   For each node, print key and neighbors exactly as stored, matching 1: 2 3 2: 1 3: 1 4 4: 3 's output.

3. Final Answer:

   1: 2 3 2: 1 3: 1 4 4: 3 -> Option C

4. Quick Check:

   Print adjacency list as stored [OK]

Hint: Print dictionary keys and their neighbor lists exactly. [OK]

Common Mistakes:

• Mixing neighbors between nodes
• Printing extra or missing neighbors
• Confusing order of neighbors

4. Identify the error in this C# code snippet that tries to add edges to a graph:

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

medium

A. graph[2] should be initialized before adding elements.

B. graph[1] is used before initializing its list, causing a runtime error.

C. Dictionary keys must be strings, not integers.

D. List<int> cannot be used as dictionary values.

Solution

1. Step 1: Check initialization of graph[1]

   graph[1] is accessed to add an element before assigning a List<int>, causing a NullReferenceException.

2. Step 2: Verify other lines

   graph[2] is correctly initialized before use; dictionary keys can be int; List<int> is valid value type.

3. Final Answer:

   graph[1] is used before initializing its list, causing a runtime error. -> Option B

4. Quick Check:

   Accessing uninitialized dictionary entry [OK]

Hint: Initialize list before adding to dictionary key. [OK]

Common Mistakes:

• Assuming dictionary keys must be strings
• Ignoring null initialization errors
• Confusing dictionary value types

5. You want to model a city map where intersections connect to multiple roads, including loops and two-way streets. Which data structure best models this, and why can't a tree be used here?

hard

A. Use a graph because it supports cycles and multiple connections; trees cannot model loops.

B. Use a tree because it is simpler and supports multiple parents per node.

C. Use an array because it stores all intersections linearly.

D. Use a linked list because it models one-way streets well.

Solution

1. Step 1: Analyze city map requirements

   City intersections connect to multiple roads, including loops and two-way streets, needing multiple connections and cycles.

2. Step 2: Compare tree and graph capabilities

   Trees cannot represent cycles or multiple parents; graphs support cycles and multiple edges between nodes.

3. Final Answer:

   Use a graph because it supports cycles and multiple connections; trees cannot model loops. -> Option A

4. Quick Check:

   City map needs cycles = graph [OK]

Hint: Graphs model cycles and multiple connections; trees do not. [OK]

Common Mistakes:

• Thinking trees allow cycles
• Choosing linear structures for complex maps
• Confusing linked lists with graphs