Graph Terminology Vertices Edges Directed Undirected Weighted in DSA Python

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 places are points and roads are lines connecting them. 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

Legend:
-> : directed edge
↔ : undirected edge
Numbers on edges represent weights if any

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 Python

class Graph:
    def __init__(self):
        self.vertices = set()
        self.edges = dict()  # key: vertex, value: list of (neighbor, directed, weight)

    def add_vertex(self, v):
        self.vertices.add(v)
        if v not in self.edges:
            self.edges[v] = []

    def add_directed_edge(self, from_v, to_v, weight=1):
        self.add_vertex(from_v)
        self.add_vertex(to_v)
        self.edges[from_v].append((to_v, True, weight))

    def add_undirected_edge(self, v1, v2, weight=1):
        self.add_vertex(v1)
        self.add_vertex(v2)
        self.edges[v1].append((v2, False, weight))
        self.edges[v2].append((v1, False, weight))

    def print_graph(self):
        for v in sorted(self.vertices):
            connections = []
            for (nbr, directed, weight) in self.edges[v]:
                arrow = '->' if directed else '↔'
                if weight != 1:
                    connections.append(f"{arrow} {nbr} (weight {weight})")
                else:
                    connections.append(f"{arrow} {nbr}")
            print(f"{v}: {' '.join(connections)}")

# Driver code
G = Graph()
G.add_directed_edge('A', 'B')
G.add_undirected_edge('B', 'C')
G.add_directed_edge('C', 'D', weight=5)
G.print_graph()

self.edges[from_v].append((to_v, True, weight))

Add directed edge from from_v to to_v with weight

self.edges[v1].append((v2, False, weight)) self.edges[v2].append((v1, False, weight))

Add undirected edge by adding connections both ways

for (nbr, directed, weight) in self.edges[v]:

Iterate neighbors to print edges with direction and weight

Output

A: -> B

B: ↔ C

C: -> D (weight 5)

D: 

Complexity Analysis

Time: O(V + E) because adding vertices and edges takes constant time per operation, and printing visits all vertices and edges once

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 here is more efficient for sparse graphs

Edge Cases

Empty graph with no vertices or edges

Prints nothing or empty lines, no errors

DSA Python

for v in sorted(self.vertices):

Adding edge where vertices do not exist yet

Vertices are automatically added before adding edges

DSA Python

self.add_vertex(from_v)
self.add_vertex(to_v)

Adding undirected edge between same vertex (self-loop)

Edge added twice to same vertex's adjacency list

DSA Python

self.edges[v1].append((v2, False, weight))
self.edges[v2].append((v1, False, weight))

When to Use This Pattern

When you see problems involving connections between points with possible directions and costs, think of graph terminology to model vertices and edges with direction and weights.

Common Mistakes

Mistake: Confusing directed and undirected edges by adding only one direction for undirected edges
Fix: Add edges in both directions for undirected edges

Mistake: Forgetting to add vertices before adding edges
Fix: Always add vertices to the graph before connecting edges

Summary

Graphs connect points called vertices with lines called edges that can have directions and weights.

Use graph terminology to model relationships where direction and cost matter, like maps or networks.

Remember edges can be one-way (directed) or two-way (undirected), and weights show cost or distance.

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 vertices and connections called edges.

2. Step 2: Identify the term for points

   The points or nodes where edges meet are called vertices.

3. Final Answer:

   Vertices -> Option A

4. Quick Check:

   Points in graph = Vertices [OK]

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

Common Mistakes:

• Confusing edges with vertices
• Thinking weights are points
• Mixing paths with vertices

2. Which of the following is the correct way to represent a weighted edge from vertex A to vertex B with weight 5 in Python using a tuple?

easy

A. (5, A, B)

B. [A, B, 5]

C. {'A': 'B', 'weight': 5}

D. (A, B, 5)

Solution

1. Step 1: Understand tuple representation

   A weighted edge is often represented as a tuple (start_vertex, end_vertex, weight).

2. Step 2: Match the correct tuple format

   The tuple (A, B, 5) correctly shows an edge from A to B with weight 5.

3. Final Answer:

   (A, B, 5) -> Option D

4. Quick Check:

   Weighted edge tuple = (start, end, weight) [OK]

Hint: Weighted edges use (start, end, weight) tuple format [OK]

Common Mistakes:

• Using list instead of tuple
• Putting weight first
• Using dictionary instead of tuple

3. What will be the output of the following Python code snippet?

graph = { 'A': ['B', 'C'], 'B': ['C'], 'C': ['A'] }
print(len(graph['A']))

medium

A. 2

B. 1

C. 3

D. 0

Solution

1. Step 1: Analyze the graph dictionary

   Key 'A' has a list of neighbors ['B', 'C'], so graph['A'] is ['B', 'C'].

2. Step 2: Calculate length of neighbors list

   len(graph['A']) counts the number of neighbors, which is 2.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Neighbors of A = 2 [OK]

Hint: Count neighbors in adjacency list for vertex [OK]

Common Mistakes:

• Counting total keys instead of neighbors
• Confusing keys with values
• Off-by-one counting errors

4. Identify the error in the following Python code that tries to create an undirected graph using adjacency lists:

graph = { 'A': ['B'], 'B': ['C'], 'C': [] }
graph['C'].append('A')

medium

A. The code is correct for undirected graph

B. Appending 'A' to 'C' creates a cycle

C. The graph is directed, not undirected

D. Missing edge from 'B' to 'A'

Solution

1. Step 1: Understand undirected graph representation

   In an undirected graph, edges go both ways, so adjacency lists must be symmetric.

2. Step 2: Check the adjacency lists

   Initially, 'A' connects to 'B', but 'B' does not connect back to 'A', so it's directed.

3. Final Answer:

   The graph is directed, not undirected -> Option C

4. Quick Check:

   Undirected graph needs two-way edges [OK]

Hint: Undirected graphs have symmetric edges in adjacency lists [OK]

Common Mistakes:

• Assuming one-way edges are undirected
• Ignoring symmetry in adjacency lists
• Confusing cycles with direction

5. You have a weighted undirected graph represented as an adjacency list:

graph = {
  'A': [('B', 3), ('C', 5)],
  'B': [('A', 3), ('C', 1)],
  'C': [('A', 5), ('B', 1)]
}

What is the total weight of all edges in this graph?

hard

A. 18

B. 9

C. 6

D. 3

Solution

1. Step 1: List all edges with weights

   Edges: A-B(3), A-C(5), B-C(1). Each edge appears twice because graph is undirected.

2. Step 2: Sum weights and divide by 2

   Total sum counting duplicates = 3+5+3+1+5+1 = 18. Divide by 2 to avoid double counting: 18 / 2 = 9.

3. Final Answer:

   9 -> Option B

4. Quick Check:

   Sum weights once for undirected edges [OK]

Hint: Sum all weights then halve for undirected graphs [OK]

Common Mistakes:

• Counting edges twice
• Forgetting to divide by 2
• Ignoring weights in tuples