Graph Terminology Vertices Edges Directed Undirected Weighted in DSA C# - Time & Space Complexity

Time Complexity: Graph Terminology Vertices Edges Directed Undirected Weighted

O(E)

Understanding Time Complexity

Graphs are made of points and connections. We want to understand how the work grows when we look at these points and connections.

How does the time to check or use these parts change as the graph gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Simple graph representation
class Graph {
  int vertices;
  List<Tuple<int, int>> edges = new List<Tuple<int, int>>();

  public Graph(int v) {
    vertices = v;
  }

  public void AddEdge(int from, int to) {
    edges.Add(Tuple.Create(from, to));
  }
}
    

This code creates a graph with a set number of points (vertices) and stores connections (edges) between them.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Adding edges to the list one by one.
• How many times: Once per edge added, total edges count is E.

How Execution Grows With Input

As we add more edges, the work to store them grows directly with the number of edges.

Input Size (Edges E)	Approx. Operations
10	10 adds
100	100 adds
1000	1000 adds

Pattern observation: The work grows in a straight line with the number of edges.

Final Time Complexity

Time Complexity: O(E)

This means the time to add edges grows directly with how many edges we have.

Common Mistake

[X] Wrong: "Adding edges depends on the number of vertices, so it is O(V)."

[OK] Correct: Adding edges depends on how many edges we add, not just vertices. Vertices count alone doesn't tell us how many connections exist.

Interview Connect

Understanding how graph size affects work helps you explain and choose the right methods when working with graphs in real problems.

Self-Check

"What if the graph was directed versus undirected? How would that affect the number of edges and time complexity?"

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