Graph Terminology Vertices Edges Directed Undirected Weighted in DSA C# - Execution Trace

Concept Flow - Graph Terminology Vertices Edges Directed Undirected Weighted

Start: Define Graph

↓

Identify Vertices (Nodes)

↓

Identify Edges (Connections)

↓

Check Edge Type

↓

Directed

↓

Check Weight

↓

Weighted

↓

Graph Complete

This flow shows how a graph is built by defining nodes (vertices), connecting them with edges, deciding if edges have direction, and if edges have weights.

Execution Sample

DSA C#

Graph G = new Graph();
G.AddVertex("A");
G.AddVertex("B");
G.AddEdge("A", "B", directed: true, weight: 5);

This code creates a graph with two vertices A and B, and adds a directed edge from A to B with weight 5.

Execution Table

Step	Operation	Vertices in Graph	Edges in Graph	Edge Details	Visual State
1	Create empty graph	[]	[]	None	Graph: (empty)
2	Add vertex 'A'	[A]	[]	None	Graph: A
3	Add vertex 'B'	[A, B]	[]	None	Graph: A B
4	Add directed edge A->B with weight 5	[A, B]	[A->B]	Directed, Weight=5	Graph: A --5--> B
5	Check if edge is directed	N/A	N/A	Yes	Edge A->B is directed
6	Check if edge is weighted	N/A	N/A	Yes	Edge A->B has weight 5
7	End of operations	[A, B]	[A->B]	Directed, Weight=5	Graph complete

💡 All vertices and edges added, graph fully defined.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	Final
Vertices	[]	[A]	[A, B]	[A, B]	[A, B]
Edges	[]	[]	[]	[A->B (directed, weight=5)]	[A->B (directed, weight=5)]

Key Moments - 3 Insights

Why do we represent edges as directed or undirected?

Because directed edges show one-way connections (see Step 5 in execution_table), while undirected edges show two-way connections. This affects how we traverse or interpret the graph.

What does it mean for an edge to be weighted?

A weighted edge has a value or cost (like distance or time). Step 6 shows the edge has weight 5, meaning the connection from A to B has a cost of 5.

Why do we list vertices separately from edges?

Vertices are the points or nodes in the graph (Steps 2 and 3), while edges are the connections between them (Step 4). Both are needed to fully describe the graph.

Visual Quiz - 3 Questions

Look at the execution_table at Step 4, what type of edge is added between A and B?

A Undirected and unweighted

B Directed and weighted

C Directed and unweighted

D Undirected and weighted

💡 Hint

Check the 'Edge Details' column at Step 4 in the execution_table.

At which step are vertices 'A' and 'B' both present in the graph?

A Step 2

B Step 4

C Step 3

D Step 1

💡 Hint

Look at the 'Vertices in Graph' column in the execution_table.

If the edge was undirected, how would the visual state at Step 4 change?

A Graph: A <--5--> B

B Graph: A --5--> B

C Graph: A --5-- B

D Graph: A --- B

💡 Hint

Directed edges have arrows one way; undirected edges have arrows both ways or no arrows.

Concept Snapshot

Graph = set of vertices (nodes) and edges (connections).
Edges can be directed (one-way) or undirected (two-way).
Edges may have weights representing cost or distance.
Vertices and edges together define the graph structure.
Directed weighted edges show direction and cost.
Undirected unweighted edges show simple two-way links.

Full Transcript

A graph is made of vertices and edges. Vertices are points or nodes. Edges connect vertices. Edges can be directed, meaning they go one way, or undirected, meaning they go both ways. Edges can also have weights, which are numbers showing cost or distance. In the example, we create a graph, add vertices A and B, then add a directed edge from A to B with weight 5. The execution table shows each step and how the graph changes. Understanding if edges are directed or weighted helps us know how to use the graph in problems.

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