Directed vs undirected graphs in Data Structures Theory - Visual Side-by-Side Comparison

Concept Flow - Directed vs undirected graphs

Start with nodes

↓

Add edges

↓

Directed: edges have direction

↓

Edge from A to B only

↓

Undirected: edges no direction

↓

Edge between A and B both ways

Graphs start with nodes, then edges are added. Edges can be directed (one-way) or undirected (two-way).

Execution Sample

Data Structures Theory

Nodes = {A, B}
Edges Directed = {(A->B)}
Edges Undirected = {(A-B)}

Shows two nodes with one directed edge from A to B and one undirected edge between A and B.

Analysis Table

Step	Operation	Graph Type	Edge Added	Effect on Connections	Visual State
1	Create nodes A and B	Directed & Undirected	None	Nodes A, B exist	Nodes: A, B; No edges
2	Add edge A->B	Directed	A->B	Connection from A to B only	A -> B
3	Add edge A-B	Undirected	A-B	Connection both ways between A and B	A <-> B
4	Check edge B->A in Directed	Directed	None	No edge from B to A	A -> B
5	Check edge B->A in Undirected	Undirected	None	Edge exists from B to A (same as A to B)	A <-> B

💡 All nodes and edges added; differences in directionality shown

State Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5
Nodes	{}	{A, B}	{A, B}	{A, B}	{A, B}	{A, B}
Directed Edges	{}	{}	{(A->B)}	{(A->B)}	{(A->B)}	{(A->B)}
Undirected Edges	{}	{}	{}	{(A-B)}	{(A-B)}	{(A-B)}

Key Insights - 3 Insights

Why does the directed graph only show connection from A to B but not from B to A?

Because directed edges have a direction, so an edge A->B means only from A to B. Step 4 in execution_table shows no edge B->A.

Why does the undirected graph show connection both ways between A and B?

Undirected edges have no direction, so edge A-B means connection both ways. Step 5 in execution_table confirms B to A connection exists.

Are nodes affected differently in directed vs undirected graphs?

No, nodes remain the same; only edges differ in directionality as shown in variable_tracker and execution_table.

Visual Quiz - 3 Questions

Look at the execution_table at Step 2. What edge is added in the directed graph?

A Edge from B to A

B Edge from A to B

C Edge between A and B with no direction

D No edge added

💡 Hint

Check the 'Edge Added' column at Step 2 in execution_table

At which step does the undirected graph show a two-way connection between nodes?

A Step 2

B Step 4

C Step 3

D Step 5

💡 Hint

Look at the 'Effect on Connections' column for undirected graph edges

If we add an edge B->A in the directed graph, how would the variable 'Directed Edges' change after Step 4?

A It would include {(A->B), (B->A)}

B It would remain {(A->B)}

C It would become empty

D It would include {(A-B)}

💡 Hint

Consider how directed edges store direction; see variable_tracker for Directed Edges

Concept Snapshot

Graphs have nodes connected by edges.
Directed graphs have edges with direction (A->B).
Undirected graphs have edges without direction (A-B).
Directed edges connect one way; undirected connect both ways.
Nodes stay the same; edges define connection type.
Understanding edge direction is key to graph behavior.

Full Transcript

This visual execution trace shows the difference between directed and undirected graphs. We start by creating two nodes, A and B. Then, we add a directed edge from A to B, which means the connection goes only one way. Next, we add an undirected edge between A and B, which connects both nodes in both directions. The execution table tracks each step, showing how edges affect connections. The variable tracker records the state of nodes and edges after each step. Key moments clarify common confusions about edge direction and node roles. The quiz tests understanding by referencing specific steps and variable states. Overall, directed graphs have one-way edges, while undirected graphs have two-way edges, affecting how nodes connect.

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