Introduction
A topological sort is an ordering of the nodes of a directed graph such that if there is path from node to node , then node appears before node in the ordering. An acyclic graph always has a topological sort.
Implementation
To check if a graph has a cycle
If the graph contains a cycle, it is not possible to form a topological sort, because no node of the cycle can appear before the other nodes of the cycle in the ordering.
# state 0: the node has not been processed
# state 1: the node is under processing
# state 2: the node has been processed
def hasCycle(N, graph):
state = [0] * N
def dfs(node):
state[node] = 1
for adj in graph[node]:
if state[node] == 2: continue
if state[node] == 1: return True
if dfs(adj):
return True
state[node] = 2
return False
for node in range(N):
if state[node] == 0 and go(node):
return True
return False # the graph does not contain a cycle
Topological sorting
def topological_sort(N, graph):
visited = [False] * N
order = []
def dfs(node):
visited[node] = True
for adj in graph[node]:
if not visited[adj]:
dfs(adj)
order.append(node)
for node in range(N):
if not visited[node]:
dfs(node)
order.reverse()
Complexity
- Time complexity:
- Space complexity: