Directed vs undirected graphs in Data Structures Theory - When to Use Which

The Big Idea

What if your map treats one-way streets like two-way and sends you the wrong way?

The Scenario

Imagine you are trying to map out all the roads in your city by drawing lines between places on paper. Some roads allow cars to go both ways, while others are one-way streets. Without marking which roads are one-way and which are two-way, your map can be confusing and misleading.

The Problem

Trying to represent connections without distinguishing direction means you might treat one-way streets as two-way. This causes errors when planning routes or understanding traffic flow. Manually tracking direction for each connection is slow and easy to forget, leading to wrong conclusions.

The Solution

Using directed and undirected graphs lets you clearly show whether connections go one way or both ways. Directed graphs use arrows to show direction, while undirected graphs use simple lines. This clear representation helps computers and people understand relationships accurately and quickly.

Before vs After

✗ Before

roads = [('A', 'B'), ('B', 'A'), ('B', 'C')]  # no direction info

✓ After

directed_roads = [('A', 'B'), ('B', 'C')]  # arrows show one-way
undirected_roads = [('A', 'B'), ('B', 'C')]  # lines show two-way

What It Enables

It enables precise modeling of real-world connections, like traffic routes or social networks, where direction matters or does not.

Real Life Example

When using a GPS app, directed graphs help the app know which streets are one-way so it can give correct driving directions.

Key Takeaways

Directed graphs show one-way connections with arrows.

Undirected graphs show two-way connections with simple lines.

Choosing the right type helps accurately represent and solve real problems.

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