Python: Sort a list of elements using Topological sort

Last update on April 02 2025 05:28:12 (UTC/GMT +8 hours)

22. Topological Sort

Write a Python program to sort a list of elements using Topological sort.

Sample Solution:

Python Code:

# License https://bit.ly/2InTS3W
#     a
#    / \
#   b  c
#  / \
# d  e
edges = {'a': ['c', 'b'], 'b': ['d', 'e'], 'c': [], 'd': [], 'e': []}
vertices = ['a', 'b', 'c', 'd', 'e']
def topological_sort(start, visited, sort):
    """Perform topolical sort on a directed acyclic graph."""
    current = start
    # add current to visited
    visited.append(current)
    neighbors = edges[current]
    for neighbor in neighbors:
        # if neighbor not in visited, visit
        if neighbor not in visited:
            sort = topological_sort(neighbor, visited, sort)
    # if all neighbors visited add current to sort
    sort.append(current)
    # if all vertices haven't been visited select a new one to visit
    if len(visited) != len(vertices):
        for vertice in vertices:
            if vertice not in visited:
                sort = topological_sort(vertice, visited, sort)
    # return sort
    return sort

sort = topological_sort('a', [], [])
print(sort)

Sample Output:

['c', 'd', 'e', 'b', 'a']

Flowchart:

For more Practice: Solve these Related Problems:

• Write a Python program to perform topological sort on a directed acyclic graph (DAG) represented as an adjacency list.
• Write a Python script to implement topological sort and then output the sorted order of tasks with dependencies.
• Write a Python program to detect cycles in a graph before attempting a topological sort and then print an error message if a cycle is found.
• Write a Python function to read a list of prerequisite pairs and perform a topological sort to determine a valid course order.

Python Code Editor:

Contribute your code and comments through Disqus.

Previous: Write a Python program to sort a list of elements using Time sort.
Next: Write a Python program to sort a list of elements using Tree sort.