Directed vs undirected graphs in Data Structures Theory - Hands-On Comparison

Understanding Directed vs Undirected Graphs

📖 Scenario: You are helping a friend understand how different types of graphs work by creating simple examples of directed and undirected graphs. These graphs represent connections between places in a small town.

🎯 Goal: Build two simple graph examples: one directed and one undirected. This will help visualize how connections differ when direction matters versus when it does not.

📋 What You'll Learn

Create a dictionary called undirected_graph representing an undirected graph with exact nodes and edges

Create a dictionary called directed_graph representing a directed graph with exact nodes and edges

Add a variable called node_count that counts the total number of nodes in the graphs

Add a variable called edge_count that counts the total number of edges in the directed graph

💡 Why This Matters

🌍 Real World

Graphs are used to model networks like roads, social connections, and computer networks where direction of connection matters or not.

💼 Career

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

1

Create an undirected graph

Create a dictionary called undirected_graph with these exact connections: 'A': ['B', 'C'], 'B': ['A', 'D'], 'C': ['A'], and 'D': ['B']. This represents an undirected graph where edges go both ways.

Data Structures Theory

# Create the undirected graph dictionary
# Your code here

Hint

Think of each key as a place and the list as places directly connected to it without direction.

2

Create a directed graph

Add a dictionary called directed_graph with these exact connections: 'A': ['B', 'C'], 'B': ['D'], 'C': [], and 'D': ['A']. This represents a directed graph where edges have direction from the key to the nodes in the list.

Data Structures Theory

undirected_graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A'],
    'D': ['B']
}
# Create the directed graph dictionary
# Your code here

Hint

Remember, in a directed graph, connections only go one way from the key to the listed nodes.

3

Count the total nodes

Create a variable called node_count that stores the total number of unique nodes in the graphs. Use the keys of the undirected_graph dictionary to count nodes.

Data Structures Theory

undirected_graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A'],
    'D': ['B']
}
directed_graph = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': [],
    'D': ['A']
}
# Count the total nodes
# Your code here

Hint

Use the len() function on the keys of the undirected graph dictionary.

4

Count the total edges in the directed graph

Create a variable called edge_count that stores the total number of edges in the directed_graph. Calculate this by summing the lengths of all adjacency lists in directed_graph.

Data Structures Theory

undirected_graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A'],
    'D': ['B']
}
directed_graph = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': [],
    'D': ['A']
}
node_count = len(undirected_graph.keys())
# Calculate total edges in directed_graph
# Your code here

Hint

Use a generator expression inside sum() to add up the lengths of all adjacency lists.

Practice

1. Which of the following best describes a directed graph?

easy

A. Edges have a direction from one vertex to another

B. Edges connect vertices without any direction

C. Edges are weighted but have no direction

D. Edges connect only vertices of the same type

Solution

1. Step 1: Understand edge direction in graphs

   Directed graphs have edges that point from one vertex to another, showing direction.

2. Step 2: Compare with undirected graphs

   Undirected graphs have edges without direction, connecting vertices both ways equally.

3. Final Answer:

   Edges have a direction from one vertex to another -> Option A

4. Quick Check:

   Directed graph = edges with direction [OK]

Hint: Directed means edges point one way only [OK]

Common Mistakes:

• Confusing directed with weighted edges
• Thinking undirected edges have direction
• Assuming all graphs have directions

2. Which of the following is the correct way to represent an undirected edge between vertices A and B?

easy

A. (A → B) only

B. (A, B) only

C. (B, A) only

D. (A, B) and (B, A) both included

Solution

1. Step 1: Understand undirected edge representation

   Undirected edges connect two vertices both ways, so both (A, B) and (B, A) are included.

2. Step 2: Compare with directed edge representation

   Directed edges include only one direction, like (A → B), not both.

3. Final Answer:

   (A, B) and (B, A) both included -> Option D

4. Quick Check:

   Undirected edge = both directions stored [OK]

Hint: Undirected edges need both directions listed [OK]

Common Mistakes:

• Listing only one direction for undirected edges
• Confusing directed arrow notation with undirected
• Assuming undirected edges are stored once only

3. Given the directed graph edges: [(1, 2), (2, 3), (3, 1)], what is the result of checking if there is a path from vertex 3 to vertex 2?

medium

A. Only if the graph is undirected

B. Yes, there is a path

C. No, there is no path

D. Cannot determine without weights

Solution

1. Step 1: Analyze edges for path from 3 to 2

   Edges are (1 → 2), (2 → 3), (3 → 1). From 3, you can go to 1 only.

2. Step 2: Check if path leads to 2

   From 3 to 1, then from 1 to 2 is possible, so path exists: 3 → 1 → 2.

3. Final Answer:

   Yes, there is a path -> Option B

4. Quick Check:

   Path 3->1->2 exists [OK]

Hint: Follow edges direction step-by-step [OK]

Common Mistakes:

• Ignoring indirect paths
• Assuming no path if direct edge missing
• Confusing directed with undirected paths

4. Identify the error in this undirected graph edge list representation: edges = [(1, 2), (2, 3), (3, 1)] used as is for an undirected graph.

medium

A. Edges should be duplicated in reverse order

B. Edges must be tuples of length 3

C. Edges cannot connect vertex 3 to 1

D. No error, this is correct

Solution

1. Step 1: Understand undirected edge storage

   Undirected edges require both (u, v) and (v, u) to represent two-way connection.

2. Step 2: Check given edge list

   Edges are only listed one way, missing reverse edges like (2, 1), (3, 2), (1, 3).

3. Final Answer:

   Edges should be duplicated in reverse order -> Option A

4. Quick Check:

   Undirected edges need both directions [OK]

Hint: Undirected edges must appear both ways [OK]

Common Mistakes:

• Assuming one direction is enough
• Thinking tuples need 3 elements
• Believing given list is complete

5. You want to model a social network where friendships are mutual. Which graph type should you use and why?

hard

A. Directed graph, to track who follows whom

B. Directed graph, because friendships have direction

C. Undirected graph, because friendships go both ways

D. Weighted graph, to show friendship strength

Solution

1. Step 1: Understand the nature of friendships

   Mutual friendships mean if A is friend with B, then B is friend with A.

2. Step 2: Choose graph type matching mutual connections

   Undirected graphs represent mutual connections naturally, with edges having no direction.

3. Final Answer:

   Undirected graph, because friendships go both ways -> Option C

4. Quick Check:

   Mutual relations = undirected graph [OK]

Hint: Mutual means undirected edges [OK]

Common Mistakes:

• Choosing directed graph for mutual relations
• Confusing following with friendship
• Ignoring edge direction meaning