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:
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.
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
- Weekly Trends and Language Statistics
- Weekly Trends and Language Statistics