# Topological Sort

Category: /template
``````""" Implementation of [Grokking the Coding Interview: Patterns for Coding Questions](https://www.educative.io/courses/grokking-the-coding-interview/m25rBmwLV00)
"""
from collections import deque

def topological_sort(vertices, edges):
sortedOrder = []
if not vertices: return sortedOrder

# a. Initialize the graph for sources and incoming degree
in_degree = {i:0 for i in range(vertices)}  # count of incoming edges
graph = {i: [] for i in range(vertices)}  # adjacency list graph

# b. build the graph
for edge in edges:
parent, child = edge, edge
graph[parent].append(child)  # put the child into its parent list
in_degree[child] += 1  # increase the incoming degree counter

# c. find all sources i.e. all vertices with 0 in-degree
sources = deque()
for key in in_degree:
if in_degree[key] == 0:
sources.append(key)

# d. for each source, addd it to the sortedOrder and
# subtract one from all of its children's in-degree
# if a child's in-degree becomes zero, add it to the sources queue
while sources:
vertex = sources.popleft()
sortedOrder.append(vertex)
for child in graph[vertex]:
in_degree[child] -= 1
if in_degree[child] == 0:
sources.append(child)

# topological sort is not possible as the graph has a cycle
if len(sortedOrder) != vertices:
return []
return sortedOrder

if __name__ == "__main__":
print("Topological sort: " +
str(topological_sort(4, [[3, 2], [3, 0], [2, 0], [2, 1]])))
print("Topological sort: " +
str(topological_sort(5, [[4, 2], [4, 3], [2, 0], [2, 1], [3, 1]])))
print("Topological sort: " +
str(topological_sort(7, [[6, 4], [6, 2], [5, 3], [5, 4],
[3, 0], [3, 1], [3, 2], [4, 1]])))
``````

# 讨论

### 提示

• 如果看不到讨论部分, 请暂时关掉adblock in Firefox/Chrome
• 本网站使用Javascript实现评论功能, 此处外链对提高您的网站PR没有帮助. (潜台词: 请不要灌水, 谢谢)