algorithms-python/algorithms/sort/top_sort.py at master · ivan1911/algorithms-python · GitHub

History

66 lines (59 loc) · 1.78 KB

Raw

GRAY, BLACK = 0, 1

def top_sort_recursive(graph):

""" Time complexity is the same as DFS, which is O(V + E)

Space complexity: O(V)

"""

order, enter, state = [], set(graph), {}

def dfs(node):

state[node] = GRAY

#print(node)

for k in graph.get(node, ()):

sk = state.get(k, None)

if sk == GRAY:

raise ValueError("cycle")

if sk == BLACK:

continue

enter.discard(k)

dfs(k)

order.append(node)

state[node] = BLACK

while enter: dfs(enter.pop())

return order

def top_sort(graph):

""" Time complexity is the same as DFS, which is O(V + E)

Space complexity: O(V)

"""

order, enter, state = [], set(graph), {}

def is_ready(node):

lst = graph.get(node, ())

if len(lst) == 0:

return True

for k in lst:

sk = state.get(k, None)

if sk == GRAY:

raise ValueError("cycle")

if sk != BLACK:

return False

return True

while enter:

node = enter.pop()

stack = []

while True:

state[node] = GRAY

stack.append(node)

for k in graph.get(node, ()):

sk = state.get(k, None)

if sk == GRAY:

raise ValueError("cycle")

if sk == BLACK:

continue

enter.discard(k)

stack.append(k)

while stack and is_ready(stack[-1]):

node = stack.pop()

order.append(node)

state[node] = BLACK

if len(stack) == 0:

break

node = stack.pop()

return order

algorithms-python/algorithms/sort/top_sort.py at master · ivan1911/algorithms-python · GitHub

Expand file tree

Breadcrumbs

top_sort.py

Latest commit

History

Breadcrumbs

top_sort.py

File metadata and controls