Graph Terminology Vertices Edges Directed Undirected Weighted in DSA C#

Mental Model

A graph is a way to connect points (vertices) with lines (edges) that can have directions and weights.

Analogy: Think of a city map where intersections are points (vertices) and roads are lines (edges). Some roads go one way (directed), some both ways (undirected), and some roads have distances (weights).

Vertices: A, B, C, D
Edges:
A -> B (directed)
B ↔ C (undirected)
C -> D (directed, weight 5)

A -> B -> C ↔ D
Weights shown on edges where applicable

Dry Run Walkthrough

Input: Graph with vertices A, B, C, D; edges: A->B (directed), B↔C (undirected), C->D (directed, weight 5)

Goal: Understand how vertices and edges connect, and how direction and weight affect the graph

Step 1: Identify vertices as points A, B, C, D

Vertices: [A] [B] [C] [D]

Why: Vertices are the main points or nodes in the graph

Step 2: Add directed edge from A to B

A -> B
Vertices: [A] [B] [C] [D]

Why: Directed edge means connection goes only from A to B

Step 3: Add undirected edge between B and C

A -> B ↔ C
Vertices: [A] [B] [C] [D]

Why: Undirected edge means connection goes both ways between B and C

Step 4: Add directed weighted edge from C to D with weight 5

A -> B ↔ C -> D (weight 5)
Vertices: [A] [B] [C] [D]

Why: Weight shows cost or distance on the edge from C to D

Result:

Graph:
A -> B ↔ C -> D (weight 5)
Vertices: [A] [B] [C] [D]

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

class Graph
{
    public HashSet<string> Vertices = new HashSet<string>();
    public List<(string from, string to, bool directed, int weight)> Edges = new List<(string, string, bool, int)>();

    public void AddVertex(string v)
    {
        Vertices.Add(v);
    }

    public void AddEdge(string from, string to, bool directed, int weight = 0)
    {
        Edges.Add((from, to, directed, weight));
        if (!directed)
        {
            Edges.Add((to, from, directed, weight)); // add reverse edge for undirected
        }
    }

    public void PrintGraph()
    {
        Console.WriteLine("Vertices: " + string.Join(", ", Vertices));
        Console.WriteLine("Edges:");
        foreach (var e in Edges)
        {
            string dir = e.directed ? "->" : "↔";
            string w = e.weight > 0 ? $" (weight {e.weight})" : "";
            Console.WriteLine($"{e.from} {dir} {e.to}{w}");
        }
    }
}

class Program
{
    static void Main()
    {
        Graph g = new Graph();
        g.AddVertex("A");
        g.AddVertex("B");
        g.AddVertex("C");
        g.AddVertex("D");

        g.AddEdge("A", "B", true); // directed edge A->B
        g.AddEdge("B", "C", false); // undirected edge B<->C
        g.AddEdge("C", "D", true, 5); // directed weighted edge C->D weight 5

        g.PrintGraph();
    }
}

Edges.Add((from, to, directed, weight));

Add edge from source to destination with direction and weight

if (!directed) { Edges.Add((to, from, directed, weight)); // add reverse edge for undirected }

For undirected edges, add reverse edge to represent two-way connection

foreach (var e in Edges) { string dir = e.directed ? "->" : "↔"; string w = e.weight > 0 ? $" (weight {e.weight})" : ""; Console.WriteLine($"{e.from} {dir} {e.to}{w}"); }

Print all edges showing direction and weight if present

Output

Vertices: A, B, C, D

Edges:

A -> B

B ↔ C

C ↔ B

C -> D (weight 5)

Complexity Analysis

Time: O(V + E) because we store and print all vertices and edges once

Space: O(V + E) because we keep all vertices and edges in memory

vs Alternative: Compared to adjacency matrix (O(V^2) space), this edge list uses less space for sparse graphs

Edge Cases

Empty graph with no vertices or edges

Prints empty vertices and edges lists without error

DSA C#

Vertices.Add(v);

Graph with single vertex and no edges

Prints single vertex and no edges

DSA C#

Vertices.Add(v);

Undirected edge adds two entries in edge list

Both directions appear in edges to represent two-way connection

DSA C#

if (!directed)
{
    Edges.Add((to, from, directed, weight));

When to Use This Pattern

When a problem involves connecting points with lines that may have directions or costs, recognize it as a graph problem and use graph terminology to model it.

Common Mistakes

Mistake: Forgetting to add the reverse edge for undirected edges
Fix: Add the reverse edge explicitly in the code to represent two-way connection

Mistake: Confusing directed edges as undirected or vice versa
Fix: Always check the direction flag and treat edges accordingly

Summary

Graphs connect points called vertices with lines called edges that can be directed or undirected and may have weights.

Use graphs to model relationships where direction and cost between points matter, like maps or networks.

Remember edges can go one way (directed) or both ways (undirected), and weights add extra info like distance or cost.

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