Graph Terminology Vertices Edges Directed Undirected Weighted in DSA Rust

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 are longer or shorter (weighted).

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

  A -> B
      ↘
       C ↔ D

Weights shown as numbers on edges if present.

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
B ↔ C
C -> D (weight 5)
Vertices: [A] [B] [C] [D]

Annotated Code

DSA Rust

use std::collections::HashMap;

#[derive(Debug)]
struct Graph {
    vertices: Vec<char>,
    edges: HashMap<(char, char), Option<u32>>, // (from, to) -> weight or None
    directed: bool,
}

impl Graph {
    fn new(directed: bool) -> Self {
        Self {
            vertices: Vec::new(),
            edges: HashMap::new(),
            directed,
        }
    }

    fn add_vertex(&mut self, v: char) {
        if !self.vertices.contains(&v) {
            self.vertices.push(v);
        }
    }

    fn add_edge(&mut self, from: char, to: char, weight: Option<u32>) {
        self.add_vertex(from);
        self.add_vertex(to);
        self.edges.insert((from, to), weight);
        if !self.directed {
            self.edges.insert((to, from), weight); // add reverse edge for undirected
        }
    }

    fn print_graph(&self) {
        println!("Vertices: {:?}", self.vertices);
        println!("Edges:");
        for ((from, to), weight) in &self.edges {
            match weight {
                Some(w) => println!("{} -> {} (weight {})", from, to, w),
                None => println!("{} -> {}", from, to),
            }
        }
    }
}

fn main() {
    let mut graph = Graph::new(true); // directed graph
    graph.add_edge('A', 'B', None); // A -> B
    graph.directed = false; // switch to undirected for next edge
    graph.add_edge('B', 'C', None); // B <-> C
    graph.directed = true; // back to directed
    graph.add_edge('C', 'D', Some(5)); // C -> D with weight 5
    graph.print_graph();
}

self.edges.insert((from, to), weight);

Add edge from 'from' to 'to' with optional weight

if !self.directed { self.edges.insert((to, from), weight); // add reverse edge for undirected }

If graph is undirected, add reverse edge to simulate two-way connection

graph.add_edge('A', 'B', None);

Add directed edge A -> B

graph.directed = false;

Switch graph to undirected mode

graph.add_edge('B', 'C', None);

Add undirected edge B <-> C

graph.directed = true;

Switch graph back to directed mode

graph.add_edge('C', 'D', Some(5));

Add directed weighted edge C -> D with weight 5

Output

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

Edges:

A -> B

B -> C

C -> B

C -> D (weight 5)

Complexity Analysis

Time: O(1) for adding a vertex or edge because we use hash maps for edges and vectors for vertices

Space: O(V + E) because we store all vertices and edges explicitly

vs Alternative: Compared to adjacency matrix which uses O(V^2) space, adjacency list (hash map) is more efficient for sparse graphs

Edge Cases

Adding an edge where vertices do not exist yet

Vertices are automatically added before adding the edge

DSA Rust

self.add_vertex(from);

Adding duplicate vertices

Duplicate vertices are ignored to keep unique vertex list

DSA Rust

if !self.vertices.contains(&v) { self.vertices.push(v); }

Adding undirected edge in directed mode

Only one direction edge is added, no reverse edge

DSA Rust

if !self.directed { self.edges.insert((to, from), 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 reverse edge for undirected graphs
Fix: Always add the reverse edge when the graph is undirected to represent two-way connections

Summary

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

Use graphs when you need to model relationships or paths between items with possible directions and costs.

Remember that undirected edges mean two-way connections and weights represent costs or distances on edges.

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