Graph Terminology Vertices Edges Directed Undirected Weighted in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of adjacency list for directed weighted graph

What is the printed adjacency list representation of the directed weighted graph after adding edges?

DSA C#

using System;
using System.Collections.Generic;

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

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

    public void PrintGraph() {
        foreach (var vertex in adjList) {
            Console.Write(vertex.Key + " -> ");
            foreach (var edge in vertex.Value) {
                Console.Write($"({edge.Item1}, {edge.Item2}) ");
            }
            Console.WriteLine();
        }
    }
}

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

A

1 -> (3, 10) (2, 5) 
2 -> (3, 2) 

B

1 -> (2, 5) (3, 10) 
2 -> (3, 2) 

C

1 -> (2, 5) (3, 2) 
2 -> (3, 10) 

D

1 -> (2, 5) 
2 -> (3, 2) (1, 10) 

💡 Hint

Check the order and weights of edges added from vertex 1 and 2.

The graph is directed and weighted. Edges added from 1 to 2 with weight 5, from 1 to 3 with weight 10, and from 2 to 3 with weight 2. The adjacency list prints edges in the order they were added.

❓ Predict Output

intermediate

Output of adjacency matrix for undirected unweighted graph

What is the printed adjacency matrix after adding edges to the undirected graph?

DSA C#

using System;

class Graph {
    private int[,] matrix;
    private int size;

    public Graph(int n) {
        size = n;
        matrix = new int[n, n];
    }

    public void AddEdge(int u, int v) {
        matrix[u, v] = 1;
        matrix[v, u] = 1;
    }

    public void PrintMatrix() {
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                Console.Write(matrix[i, j] + " ");
            }
            Console.WriteLine();
        }
    }
}

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

A

0 0 1 0 
0 0 0 1 
1 0 0 0 
0 1 0 0 

B

0 1 0 0 
1 0 1 1 
0 1 0 0 
0 1 0 0 

C

0 1 1 0 
1 0 0 0 
1 0 0 1 
0 0 1 0 

D

0 1 1 0 
1 0 0 1 
1 0 0 0 
0 1 0 0 

💡 Hint

Remember undirected means symmetric matrix entries.

Edges added between 0-1, 0-2, and 1-3. Matrix is symmetric with 1s at these positions and 0s elsewhere.

🧠 Conceptual

advanced

Identify graph type from description

Which graph type is described as having edges with directions and weights representing distances?

A Undirected weighted graph

B Undirected unweighted graph

C Directed weighted graph

D Directed unweighted graph

💡 Hint

Edges have directions and weights.

Directed weighted graph has edges with direction and weights like distances.

❓ Predict Output

advanced

Output of BFS traversal on undirected graph

What is the order of vertices visited in BFS starting from vertex 0?

DSA C#

using System;
using System.Collections.Generic;

class Graph {
    private 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>();
        if (!adjList.ContainsKey(v)) adjList[v] = new List<int>();
        adjList[u].Add(v);
        adjList[v].Add(u);
    }

    public List<int> BFS(int start) {
        List<int> visitedOrder = new List<int>();
        Queue<int> queue = new Queue<int>();
        HashSet<int> visited = new HashSet<int>();

        queue.Enqueue(start);
        visited.Add(start);

        while (queue.Count > 0) {
            int current = queue.Dequeue();
            visitedOrder.Add(current);
            foreach (int neighbor in adjList[current]) {
                if (!visited.Contains(neighbor)) {
                    visited.Add(neighbor);
                    queue.Enqueue(neighbor);
                }
            }
        }
        return visitedOrder;
    }
}

class Program {
    static void Main() {
        Graph g = new Graph();
        g.AddEdge(0, 1);
        g.AddEdge(0, 2);
        g.AddEdge(1, 3);
        g.AddEdge(2, 3);
        var order = g.BFS(0);
        Console.WriteLine(string.Join(", ", order));
    }
}

A 0, 1, 2, 3

B 0, 2, 1, 3

C 0, 3, 1, 2

D 1, 0, 2, 3

💡 Hint

BFS visits neighbors level by level.

Starting at 0, neighbors 1 and 2 are visited first, then their neighbor 3.

🧠 Conceptual

expert

Edge count in complete undirected graph

How many edges are there in a complete undirected graph with 7 vertices?

A 21

B 14

C 42

D 49

💡 Hint

Use formula n*(n-1)/2 for edges in complete undirected graph.

Complete undirected graph edges count is n*(n-1)/2 = 7*6/2 = 21.

Practice

1. In a graph, what do we call the points or nodes where edges meet?

easy

A. Vertices

B. Edges

C. Weights

D. Paths

Solution

1. Step 1: Understand graph components

   A graph consists of points called nodes and connections called edges.

2. Step 2: Identify the term for nodes

   The points or nodes where edges meet are called vertices.

3. Final Answer:

   Vertices -> Option A

4. Quick Check:

   Nodes = Vertices [OK]

Hint: Remember: nodes = vertices, connections = edges [OK]

Common Mistakes:

• Confusing edges with vertices
• Thinking weights are nodes
• Mixing paths with vertices

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

easy

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

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

C. Dictionary graph = new Dictionary();

D. Dictionary graph = new Dictionary();

Solution

1. Step 1: Understand adjacency list representation

   An adjacency list uses a dictionary mapping each vertex to a list of connected vertices.

2. Step 2: Check the correct C# syntax

   Dictionary correctly represents a graph where each int key has a list of connected nodes.

3. Final Answer:

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

4. Quick Check:

   Adjacency list = Dictionary with List values [OK]

Hint: Adjacency list uses Dictionary with List for edges [OK]

Common Mistakes:

• Using List<int> alone
• Using array instead of dictionary
• Using Dictionary which stores single values

3. Consider the following C# code snippet for an undirected weighted graph:

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

// What is the weight of the edge between vertex 2 and vertex 3?

medium

A. 8

B. 5

C. 10

D. 3

Solution

1. Step 1: Locate edge from vertex 2 to 3

   In graph[2], the list contains (1,5) and (3,3). The tuple (3,3) means vertex 3 with weight 3.

2. Step 2: Identify the weight value

   The weight of the edge between 2 and 3 is 3.

3. Final Answer:

   3 -> Option D

4. Quick Check:

   Edge (2,3) weight = 3 [OK]

Hint: Check the tuple with target vertex for weight [OK]

Common Mistakes:

• Confusing vertex numbers
• Picking weight from wrong tuple
• Adding weights incorrectly

4. The following C# code tries to add an edge to an undirected graph but causes a runtime error:

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

What is the cause of the error?

medium

A. graph[2] is not initialized before adding

B. Cannot add edges in undirected graphs

C. List<int> cannot be used for graph edges

D. Syntax error in dictionary declaration

Solution

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

   graph[2] is not assigned any list before calling Add, so it is null.

2. Step 2: Understand why Add causes error

   Calling Add on null causes a NullReferenceException at runtime.

3. Final Answer:

   graph[2] is not initialized before adding -> Option A

4. Quick Check:

   Null list causes error [OK]

Hint: Always initialize lists before adding elements [OK]

Common Mistakes:

• Assuming dictionary auto-initializes lists
• Thinking undirected graphs disallow adding edges
• Confusing syntax error with runtime error

5. You have a weighted directed graph represented as:

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

// What is the total weight of the path 1 -> 3 -> 4?

hard

A. 10

B. 8

C. 7

D. 3

Solution

1. Step 1: Find weight from 1 to 3

   From graph[1], edge to 3 has weight 1.

2. Step 2: Find weight from 3 to 4

   From graph[3], edge to 4 has weight 7.

3. Step 3: Calculate total path weight

   Total weight = 1 + 7 = 8.

4. Final Answer:

   8 -> Option B

5. Quick Check:

   1->3=1 + 3->4=7 = 8 [OK]

Hint: Sum weights along the path edges [OK]

Common Mistakes:

• Adding wrong edges
• Ignoring direction of edges
• Using wrong weights from graph