Directed vs undirected graphs in Data Structures Theory - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the sentence to describe a directed graph.

Data Structures Theory

In a directed graph, edges have a [1] indicating the direction from one vertex to another.

Drag options to blanks, or click blank then click option'

Aweight

Blength

Ccolor

Ddirection

Attempts:

3 left

💡 Hint

Common Mistakes

Confusing edge weight with direction.

Thinking edges in directed graphs are undirected.

Directed graphs have edges with a direction, showing the path from one vertex to another.

2fill in blank

medium

Complete the sentence to describe an undirected graph.

Data Structures Theory

In an undirected graph, edges [1] have a direction and connect vertices symmetrically.

Drag options to blanks, or click blank then click option'

Anever

Boptionally

Csometimes

Dalways

Attempts:

3 left

💡 Hint

Common Mistakes

Assuming undirected edges have direction.

Confusing undirected with directed graphs.

Undirected graphs have edges without direction, meaning the connection is mutual between vertices.

3fill in blank

hard

Fix the error in the statement about edges in directed graphs.

Data Structures Theory

Edges in a directed graph are [1] and can be traversed in both directions.

Drag options to blanks, or click blank then click option'

Aweighted

Bundirected

Cdirected

Dcyclic

Attempts:

3 left

💡 Hint

Common Mistakes

Confusing directed edges with undirected edges.

Thinking edges in directed graphs are always weighted.

Edges in directed graphs have a direction and cannot be traversed both ways unless there is a reverse edge.

4fill in blank

hard

Fill both blanks to complete the definition of adjacency in graphs.

Data Structures Theory

In an undirected graph, two vertices are adjacent if they are connected by an [1]. In a directed graph, vertex A is adjacent to vertex B if there is an [2] from A to B.

Drag options to blanks, or click blank then click option'

Aedge

Barc

Cvertex

Dpath

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'vertex' instead of 'edge' or 'arc'.

Confusing 'path' with 'edge' or 'arc'.

In undirected graphs, adjacency means connected by an edge. In directed graphs, adjacency means there is an arc (directed edge) from one vertex to another.

5fill in blank

hard

Fill all three blanks to complete the description of graph types and edge properties.

Data Structures Theory

A [1] graph has edges with a [2] showing direction, while an [3] graph has edges without direction.

Drag options to blanks, or click blank then click option'

Adirected

Bdirection

Cundirected

Dlength

Attempts:

3 left

💡 Hint

Common Mistakes

Mixing up directed and undirected graph definitions.

Confusing direction with weight.

A directed graph has edges with direction, often shown by an arrow. An undirected graph has edges without direction.

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