Graph Terminology Vertices Edges Directed Undirected Weighted in DSA C# - Build from Scratch

Understanding Graph Terminology: Vertices, Edges, Directed, Undirected, Weighted

📖 Scenario: Imagine you are organizing a small social network where people are connected by friendships or followings. You want to represent these connections using a graph to understand how people relate to each other.

🎯 Goal: You will create a simple graph using a dictionary to represent vertices (people) and edges (connections). You will then add information about whether connections are directed or undirected and if they have weights (like strength of friendship).

📋 What You'll Learn

Create a dictionary called graph with specific vertices and edges

Add a boolean variable called isDirected to specify if the graph is directed

Create a dictionary called weights to store edge weights

Print the graph connections in a readable format

💡 Why This Matters

🌍 Real World

Graphs are used to model social networks, maps, and many relationships where connections matter.

💼 Career

Understanding graph basics is important for roles in software development, data science, and network engineering.

1

Create the graph vertices and edges

Create a dictionary called graph where keys are strings representing people: "Alice", "Bob", and "Charlie". The values are lists of strings representing their connections: "Alice" connects to "Bob" and "Charlie", "Bob" connects to "Charlie", and "Charlie" has no connections.

DSA C#

# Create the graph dictionary with vertices and edges
# Your code here

Hint

Use a Dictionary<string, List<string>> to represent the graph. Each key is a person, and the value is a list of people they connect to.

2

Add a variable to specify if the graph is directed

Add a boolean variable called isDirected and set it to true to indicate that the connections have a direction (like following someone).

DSA C#

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        Dictionary> graph = new Dictionary>
        {
            { "Alice", new List { "Bob", "Charlie" } },
            { "Bob", new List { "Charlie" } },
            { "Charlie", new List() }
        };

        // Add isDirected variable here
        # Your code here
    }
}

Hint

Use bool isDirected = true; to indicate the graph is directed.

3

Add weights to the edges

Create a dictionary called weights where keys are tuples of two strings representing edges (from, to), and values are integers representing the weight of the connection. Add these weights: ("Alice", "Bob") = 5, ("Alice", "Charlie") = 3, ("Bob", "Charlie") = 2.

DSA C#

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        Dictionary> graph = new Dictionary>
        {
            { "Alice", new List { "Bob", "Charlie" } },
            { "Bob", new List { "Charlie" } },
            { "Charlie", new List() }
        };

        bool isDirected = true;

        // Create weights dictionary here
        # Your code here
    }
}

Hint

Use a Dictionary<(string, string), int> to store weights for each edge.

4

Print the graph connections with weights

Use a foreach loop to go through each vertex and its connections in graph. For each connection, print a line in this format: "Alice -> Bob (weight 5)". Use the weights dictionary to get the weight for each edge.

DSA C#

Hint

Use nested foreach loops to print each edge and its weight using string interpolation.

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