Topological sorting in Data Structures Theory - Mini Project: Build & Apply

Understanding Topological Sorting

📖 Scenario: Imagine you are organizing tasks that depend on each other. For example, you must finish homework before watching TV. You want to find an order to do all tasks without breaking any rules.

🎯 Goal: You will build a simple representation of tasks and their dependencies, then find a valid order to complete all tasks using topological sorting.

📋 What You'll Learn

Create a dictionary called tasks with tasks as keys and lists of dependent tasks as values

Create a dictionary called in_degree to count how many prerequisites each task has

Use a list called order to store the sorted tasks

Implement the topological sorting logic to find a valid order of tasks

💡 Why This Matters

🌍 Real World

Topological sorting helps in scheduling tasks, organizing project steps, and resolving dependencies in software builds.

💼 Career

Understanding topological sorting is useful for roles in project management, software development, and data analysis where task ordering and dependency resolution are important.

1

Create the tasks dictionary

Create a dictionary called tasks with these exact entries: 'cook': ['eat'], 'shop': ['cook'], 'eat': [], 'clean': ['shop']

Data Structures Theory

# Create the tasks dictionary with dependencies
# Your code here

Hint

Think of each task as a key and the tasks that depend on it as a list of values.

2

Create the in-degree dictionary

Create a dictionary called in_degree with all tasks as keys and initial values set to 0. Then, update in_degree by counting how many prerequisites each task has from the tasks dictionary.

Data Structures Theory

tasks = {
    'cook': ['eat'],
    'shop': ['cook'],
    'eat': [],
    'clean': ['shop']
}
# Create in_degree dictionary and update counts
# Your code here

Hint

Start by setting all counts to zero, then increase the count for each dependent task.

3

Implement the topological sorting logic

Create a list called order to store the sorted tasks. Use a list called zero_in_degree to hold tasks with zero in-degree. Use a while loop to process tasks from zero_in_degree, add them to order, and decrease the in-degree of dependent tasks. Add dependent tasks to zero_in_degree when their in-degree becomes zero.

Data Structures Theory

tasks = {
    'cook': ['eat'],
    'shop': ['cook'],
    'eat': [],
    'clean': ['shop']
}
in_degree = {task: 0 for task in tasks}
for deps in tasks.values():
    for dep in deps:
        in_degree[dep] += 1
# Implement topological sorting logic
# Your code here

Hint

Start with tasks that have no dependencies, then remove them and update others.

4

Complete the topological sorting project

Add a final check to verify if the length of order is equal to the number of tasks in tasks. If they are equal, it means a valid order was found. Otherwise, it means there is a cycle and no valid order exists.

Data Structures Theory

tasks = {
    'cook': ['eat'],
    'shop': ['cook'],
    'eat': [],
    'clean': ['shop']
}
in_degree = {task: 0 for task in tasks}
for deps in tasks.values():
    for dep in deps:
        in_degree[dep] += 1

order = []
zero_in_degree = [task for task, degree in in_degree.items() if degree == 0]

while zero_in_degree:
    current = zero_in_degree.pop()
    order.append(current)
    for dependent in tasks[current]:
        in_degree[dependent] -= 1
        if in_degree[dependent] == 0:
            zero_in_degree.append(dependent)
# Add final check for cycle detection
# Your code here

Hint

Compare the number of tasks processed with the total number of tasks to detect cycles.

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