w3resource

Python: Sort a list of elements using Topological sort

Python Search and Sorting : Exercise-22 with Solution

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:

Flowchart: Python Data Structures and Algorithms: Sort a list of elements using Topological sort

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.

What is the difficulty level of this exercise?

Test your Programming skills with w3resource's quiz.



Become a Patron!

Follow us on Facebook and Twitter for latest update.

It will be nice if you may share this link in any developer community or anywhere else, from where other developers may find this content. Thanks.

https://www.w3resource.com/python-exercises/data-structures-and-algorithms/python-search-and-sorting-exercise-22.php