Topological sorting in Data Structures Theory - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

Understanding the purpose of topological sorting

What is the main purpose of performing a topological sort on a directed graph?

A To find the shortest path between two nodes in the graph

B To order the nodes so that for every directed edge from node A to node B, A comes before B

C To detect cycles in an undirected graph

D To find the maximum flow between two nodes

💡 Hint

Think about how tasks with dependencies should be arranged.

Topological sorting arranges nodes in a linear order respecting the direction of edges, so that each node appears before all nodes it points to. This is useful for scheduling tasks with dependencies.

📋 Factual

intermediate

Conditions for topological sorting

Which condition must a directed graph satisfy to have a valid topological ordering?

A The graph must be acyclic (no cycles)

B The graph must be undirected

C The graph must be strongly connected

D The graph must have at least one cycle

💡 Hint

Think about what happens if there is a cycle in the graph.

A graph must be a Directed Acyclic Graph (DAG) to have a valid topological ordering. Cycles prevent a linear ordering that respects all edges.

🔍 Analysis

advanced

Output of topological sort on a given graph

Given the directed graph with edges: A → B, A → C, B → D, C → D, which of the following is a valid topological order?

A [A, B, C, D]

B [B, A, C, D]

C [C, A, B, D]

D [D, B, C, A]

💡 Hint

Remember that a node must come before all nodes it points to.

In the graph, A points to B and C, so A must come before B and C. Both B and C point to D, so B and C must come before D. The order [A, B, C, D] respects all these constraints.

❓ Reasoning

advanced

Detecting cycles using topological sorting

What does it indicate if a topological sort algorithm cannot include all nodes of a directed graph in its ordering?

A The graph is undirected

B The graph is disconnected

C The graph contains at least one cycle

D The graph has isolated nodes

💡 Hint

Think about why some nodes might never get placed in the order.

If a topological sort cannot include all nodes, it means some nodes are part of a cycle. Cycles prevent nodes from having zero incoming edges, so they never get added to the order.

🚀 Application

expert

Number of valid topological orders

Consider a directed acyclic graph with nodes A, B, C, and edges A → B and A → C only. How many different valid topological orders exist for this graph?

A 4

B 1

C 3

D 2

💡 Hint

Think about the positions of B and C relative to each other.

Since A must come before B and C, A is fixed first. B and C have no order between them, so they can appear in either order after A. Thus, there are 2 valid orders: [A, B, C] and [A, C, B].

Practice

1. What is the main requirement for a graph to have a valid topological sorting?

easy

A. The graph must be a Directed Acyclic Graph (DAG)

B. The graph must be undirected

C. The graph must contain cycles

D. The graph must be complete

Solution

1. Step 1: Understand the definition of topological sorting

   Topological sorting orders nodes so that every directed edge from node A to node B means A comes before B in the order.

2. Step 2: Identify the graph type needed

   This ordering is only possible if the graph has no cycles, meaning it must be a Directed Acyclic Graph (DAG).

3. Final Answer:

   The graph must be a Directed Acyclic Graph (DAG) -> Option A

4. Quick Check:

   DAG = Required for topological sorting [OK]

Hint: Topological sort needs no cycles, so graph must be DAG [OK]

Common Mistakes:

• Thinking topological sort works on undirected graphs
• Assuming cycles are allowed
• Confusing DAG with any directed graph

2. Which of the following is the correct way to represent the order of nodes after a topological sort?

easy

A. A list where each node appears before all nodes it points to

B. A list where nodes appear in random order

C. A list where each node appears after all nodes it points to

D. A list sorted by node values numerically

Solution

1. Step 1: Recall the property of topological order

   In topological sorting, every node appears before all nodes it has edges to (its dependencies come first).

2. Step 2: Match this property to the options

   A list where each node appears before all nodes it points to correctly states that each node appears before all nodes it points to, which is the definition of topological order.

3. Final Answer:

   A list where each node appears before all nodes it points to -> Option A

4. Quick Check:

   Node order respects edges direction = A list where each node appears before all nodes it points to [OK]

Hint: Topological order means dependencies come first [OK]

Common Mistakes:

• Confusing order with numerical sorting
• Thinking nodes appear after their dependencies
• Assuming random order is valid

3. Given the directed edges: A -> B, B -> C, and A -> C, which of the following is a valid topological order?

medium

A. [C, A, B]

B. [B, A, C]

C. [C, B, A]

D. [A, B, C]

Solution

1. Step 1: Analyze the edges and dependencies

   Node A points to B and C, so A must come before B and C. Node B points to C, so B must come before C.

2. Step 2: Check each option against these rules

   [A, B, C] respects A before B and C, and B before C. The other options violate these dependencies.

3. Final Answer:

   [A, B, C] -> Option D

4. Quick Check:

   Order respects edges = [A, B, C] [OK]

Hint: Place nodes before their dependents in order [OK]

Common Mistakes:

• Ignoring edge directions
• Placing dependent nodes before their prerequisites
• Choosing reverse order

4. Consider the following graph edges: 1 -> 2, 2 -> 3, 3 -> 1. What is the problem when trying to perform topological sorting on this graph?

medium

A. The graph has too many nodes

B. The graph is disconnected

C. The graph contains a cycle, so topological sorting is impossible

D. The graph is undirected

Solution

1. Step 1: Identify the cycle in the graph

   The edges form a cycle: 1 -> 2 -> 3 -> 1, which means the graph is not acyclic.

2. Step 2: Understand topological sorting requirements

   Topological sorting requires the graph to be acyclic. A cycle makes it impossible to order nodes without violating dependencies.

3. Final Answer:

   The graph contains a cycle, so topological sorting is impossible -> Option C

4. Quick Check:

   Cycle present = no topological sort [OK]

Hint: Cycles block topological sorting; check for cycles first [OK]

Common Mistakes:

• Ignoring cycles and trying to sort anyway
• Confusing disconnected graphs with cycles
• Assuming undirected graphs can be topologically sorted

5. You have tasks with dependencies: Task 1 before Task 3, Task 2 before Task 3, and Task 3 before Task 4. Which of the following is a valid topological order for these tasks?

hard

A. [3, 1, 2, 4]

B. [1, 2, 3, 4]

C. [4, 3, 2, 1]

D. [2, 1, 4, 3]

Solution

1. Step 1: List the dependencies clearly

   Task 1 and Task 2 must come before Task 3, and Task 3 must come before Task 4.

2. Step 2: Validate each option against dependencies

   [1, 2, 3, 4] respects all dependencies. The other options violate at least one dependency.

3. Final Answer:

   [1, 2, 3, 4] -> Option B

4. Quick Check:

   Order respects all dependencies = [1, 2, 3, 4] [OK]

Hint: Place all prerequisites before dependent tasks [OK]

Common Mistakes:

• Placing dependent tasks before prerequisites
• Ignoring order of multiple dependencies
• Assuming any order is valid