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

Concept Flow - Graph Terminology Vertices Edges Directed Undirected Weighted

Start: Define Graph

↓

Identify Vertices

↓

Identify Edges

↓

Check Edge Type

↓

Directed

↓

Check Weight

↓

Weighted

↓

Graph Complete

This flow shows how a graph is built by defining vertices, edges, then classifying edges as directed or undirected, and weighted or unweighted.

Execution Sample

DSA Rust

struct Graph {
    vertices: Vec<char>,
    edges: Vec<(char, char, Option<u32>)>,
}

// Example: vertices = ['A', 'B'], edges = [('A', 'B', Some(5))]

Defines a graph with vertices and edges, where edges can have optional weights.

Execution Table

Step	Operation	Vertices	Edges	Edge Type	Weighted?	Visual State
1	Initialize graph	[]	[]	-	-	Graph is empty
2	Add vertex 'A'	['A']	[]	-	-	A
3	Add vertex 'B'	['A', 'B']	[]	-	-	A B
4	Add edge from 'A' to 'B'	['A', 'B']	[('A', 'B', None)]	Directed or Undirected?	No	A -> B
5	Classify edge as Directed	['A', 'B']	[('A', 'B', None)]	Directed	No	A -> B
6	Add weighted edge from 'B' to 'A' with weight 3	['A', 'B']	[('A', 'B', None), ('B', 'A', Some(3))]	Directed	Yes	A -> B, B -3-> A
7	Add undirected edge between 'A' and 'B' with weight 5	['A', 'B']	[('A', 'B', Some(5)), ('B', 'A', Some(5))]	Undirected	Yes	A <-> B (weight 5)
8	Graph construction complete	['A', 'B']	[('A', 'B', Some(5)), ('B', 'A', Some(5))]	Undirected	Yes	A <-> B (weight 5)

💡 All vertices and edges added, graph classified by edge direction and weight.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 6	After Step 7	Final
vertices	[]	['A']	['A', 'B']	['A', 'B']	['A', 'B']	['A', 'B']	['A', 'B']
edges	[]	[]	[]	[('A', 'B', None)]	[('A', 'B', None), ('B', 'A', Some(3))]	[('A', 'B', Some(5)), ('B', 'A', Some(5))]	[('A', 'B', Some(5)), ('B', 'A', Some(5))]
edge_type	-	-	-	Directed	Directed	Undirected	Undirected
weighted	-	-	-	No	Yes	Yes	Yes

Key Moments - 3 Insights

Why do we sometimes add two edges for one undirected edge?

Because undirected edges connect both ways, we represent them as two directed edges in opposite directions, as shown in steps 7 and 8 in the execution_table.

What does it mean when an edge has 'Some(weight)' vs 'None'?

'Some(weight)' means the edge has a weight (like cost or distance), while 'None' means the edge is unweighted. See steps 4 and 6 for examples.

How do we know if an edge is directed or undirected?

Directed edges go one way only, undirected edges go both ways. The execution_table steps 5 and 7 show how edges are classified.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the edge type and weight of the edge added?

A Undirected, weighted

B Directed, weighted

C Directed, unweighted

D Undirected, unweighted

💡 Hint

Check the 'Edge Type' and 'Weighted?' columns at step 4 in execution_table.

At which step does the graph first include a weighted edge?

A Step 4

B Step 6

C Step 5

D Step 7

💡 Hint

Look at the 'Weighted?' column in execution_table to find when 'Yes' appears first.

If we remove the edge from 'B' to 'A' at step 6, what would be the edge type at step 7?

A Undirected

B Directed

C Weighted

D Unweighted

💡 Hint

Step 7 shows undirected edges represented by two directed edges; removing one still means undirected if both directions exist.

Concept Snapshot

Graph = vertices + edges
Vertices = points/nodes
Edges = connections between vertices
Edges can be Directed (one-way) or Undirected (two-way)
Edges can be Weighted (have a value) or Unweighted
Undirected edges stored as two directed edges in opposite directions

Full Transcript

A graph is made of vertices (points) and edges (connections). Vertices are like places, edges are paths between them. Edges can be directed, meaning one-way, or undirected, meaning two-way. Edges can also have weights, like distances or costs. In code, vertices are stored in a list, edges as pairs of vertices with optional weights. Undirected edges are stored as two directed edges going both ways. This helps us understand and build graphs clearly.

Practice

1. In graph terminology, what is a vertex?

easy

A. A point or node in the graph where edges meet

B. A line connecting two points in the graph

C. A graph that has no edges

D. A graph with weighted edges

Solution

1. Step 1: Understand the definition of vertex

   A vertex is a fundamental unit in a graph representing a point or node.

2. Step 2: Differentiate vertex from edges and graph types

   Edges connect vertices; graphs can be weighted or unweighted, directed or undirected, but vertices are the points themselves.

3. Final Answer:

   A point or node in the graph where edges meet -> Option A

4. Quick Check:

   Vertex = point/node [OK]

Hint: Vertices are points, edges are lines connecting them [OK]

Common Mistakes:

• Confusing vertices with edges
• Thinking vertex means weighted edge
• Mixing vertex with graph type

2. Which of the following is the correct Rust syntax to declare an undirected edge between vertices 1 and 2 using a tuple?

easy

A. let edge = {1, 2};

B. let edge = (1, 2);

C. let edge = [1, 2];

D. let edge = <1, 2>;

Solution

1. Step 1: Recall Rust tuple syntax

   Tuples in Rust are declared with parentheses and comma-separated values, e.g., (1, 2).

2. Step 2: Check other options for correctness

   Square brackets [] are for arrays, curly braces {} are for blocks or sets (not in Rust), angle brackets <> are not used for tuples.

3. Final Answer:

   let edge = (1, 2); -> Option B

4. Quick Check:

   Tuple syntax uses parentheses ( ) [OK]

Hint: Tuples use parentheses ( ), arrays use brackets [ ] [OK]

Common Mistakes:

• Using square brackets for tuples
• Using curly braces instead of parentheses
• Confusing angle brackets with tuple syntax

3. What is the output of the following Rust code that creates a weighted directed edge and prints its components?

struct Edge {
    from: usize,
    to: usize,
    weight: i32,
}

fn main() {
    let e = Edge { from: 3, to: 5, weight: 10 };
    println!("{} -> {} with weight {}", e.from, e.to, e.weight);
}

medium

A. 3 -> 5 with weight 0

B. 5 -> 3 with weight 10

C. 3 -> 5 with weight 10

D. Compilation error due to missing semicolon

Solution

1. Step 1: Understand struct initialization

   The struct Edge is initialized with from=3, to=5, weight=10 correctly.

2. Step 2: Analyze the println! macro output

   The print statement outputs the from, to, and weight fields in order: "3 -> 5 with weight 10".

3. Final Answer:

   3 -> 5 with weight 10 -> Option C

4. Quick Check:

   Prints from-to-weight as given [OK]

Hint: Struct fields print as assigned, watch order in println! [OK]

Common Mistakes:

• Swapping from and to values
• Assuming default weight 0
• Thinking missing semicolon causes error here

4. Identify the error in this Rust code snippet that tries to create an undirected weighted edge:

struct Edge {
    vertex1: usize,
    vertex2: usize,
    weight: i32,
}

fn main() {
    let e = Edge { vertex1: 1, vertex2: 2 };
    println!("Edge between {} and {} with weight {}", e.vertex1, e.vertex2, e.weight);
}

medium

A. Missing weight field initialization causes a compile error

B. vertex1 and vertex2 should be swapped

C. println! macro syntax is incorrect

D. Edge struct should not have weight for undirected edges

Solution

1. Step 1: Check struct initialization

   The Edge struct requires vertex1, vertex2, and weight fields. Weight is missing in initialization.

2. Step 2: Understand Rust's strict initialization rules

   Rust requires all fields to be initialized; missing weight causes compile-time error.

3. Final Answer:

   Missing weight field initialization causes a compile error -> Option A

4. Quick Check:

   All struct fields must be initialized [OK]

Hint: All struct fields must be given values when creating instance [OK]

Common Mistakes:

• Assuming missing fields default to zero
• Thinking vertex order matters for undirected edges
• Believing println! syntax is wrong here

5. You want to represent a weighted undirected graph in Rust using an adjacency list. Which data structure is the best choice to store edges with weights efficiently?

hard

A. HashMap storing only vertex connections without weights

B. Vec storing neighbors only, ignoring weights

C. Vec<(usize, usize, i32)> storing all edges as tuples without adjacency

D. Vec> where each inner Vec holds (neighbor_vertex, weight)

Solution

1. Step 1: Understand adjacency list for weighted graphs

   Weighted graphs need to store neighbors and weights; a Vec of Vec of tuples (neighbor, weight) fits well.

2. Step 2: Evaluate other options

   HashMap without weights loses weight info; flat Vec of tuples lacks adjacency structure; Vec of usize ignores weights.

3. Final Answer:

   Vec> where each inner Vec holds (neighbor_vertex, weight) -> Option D

4. Quick Check:

   Adjacency list with (neighbor, weight) tuples is best [OK]

Hint: Use adjacency list with (neighbor, weight) tuples for weighted graphs [OK]

Common Mistakes:

• Ignoring weights in adjacency list
• Using flat edge list without adjacency
• Using HashMap without weight info