Topological sorting
The following code is trying to detect the cycle by counting the number of iterations. If the number of iterations is larger than n, it means we have a cycle, return [], else return the result
DFS approach (using the number of iterations of detect cycle)
class Solution:
def findOrder(self, n: int, prerequisites: List[List[int]]) -> List[int]:
if not prerequisites:return list(range(n))
graph = collections.defaultdict(list)
for a,b in prerequisites:
graph[b].append(a)
visited = [False]*n
res = []
self.iteration=0
def dfs(i):
self.iteration +=1
if self.iteration>n:return False
for j in graph[i]:
if not visited[j]:
if not dfs(j):return False
visited[i] = True
res.append(i)
return True
for i in range(n):
if not visited[i]:
if not dfs(i):return []
return res[::-1]DFS approach (standard Tarjan’s algorithm)
UNVISITED = 1
EXPLORED = 2
VISITED = 3class Solution:
def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:# Create the adjacency list representation of the graph
graph = defaultdict(list)# A pair [a, b] in the input represents edge from b --> a
for dest,src in prerequisites:
graph[src].append(dest)res = []
self.hascycle = False# By default all vertces are UNVISITED
vertex_state = [UNVISITED]*numCourses
def dfs(node):# Don't recurse further if we found a cycle already
if self.hascycle:return# Start the recursion
vertex_state[node] = EXPLORED
# Traverse on neighboring vertices
if node in graph:
for neighbor in graph[node]:
if vertex_state[neighbor] == UNVISITED:
dfs(neighbor)
elif vertex_state[neighbor] == EXPLORED:
# An edge to a GRAY vertex represents a cycle
self.hascycle=True
return# Recursion ends. We mark it as black
vertex_state[node] = VISITED
res.append(node)for i in range(numCourses):
# If the node is unprocessed, then call dfs on it.
if vertex_state[i] == UNVISITED:
dfs(i)return [] if self.hascycle else res[::-1]
time complexity O(V+E)
space complexity O(V+E)
BFS approach (Kahn’s algorithm)
time complexity O(V+E)
“A DAG G has at least one vertex with in-degree 0 and one vertex with out-degree 0.
Proof: There’s a simple proof to the above fact is that a DAG does not contain a cycle which means that all paths will be of finite length. Now let S be the longest path from u(source) to v(destination). Since S is the longest path there can be no incoming edge to u and no outgoing edge from v, if this situation had occurred then S would not have been the longest path
=> indegree(u) = 0 and outdegree(v) = 0
Algorithm:
Steps involved in finding the topological ordering of a DAG:
Step-1: Compute in-degree (number of incoming edges) for each of the vertex present in the DAG and initialize the count of visited nodes as 0.
Step-2: Pick all the vertices with in-degree as 0 and add them into a queue (Enqueue operation)
Step-3: Remove a vertex from the queue (Dequeue operation) and then.
- Increment count of visited nodes by 1.
- Decrease in-degree by 1 for all its neighboring nodes.
- If in-degree of a neighboring nodes is reduced to zero, then add it to the queue.
Step 5: Repeat Step 3 until the queue is empty.
Step 5: If count of visited nodes is not equal to the number of nodes in the graph then the topological sort is not possible for the given graph.
How to find in-degree of each node?
There are 2 ways to calculate in-degree of every vertex:
Take an in-degree array which will keep track of
1) Traverse the array of edges and simply increase the counter of the destination node by 1.
for each node in Nodes
indegree[node] = 0;
for each edge(src,dest) in Edges
indegree[dest]++Time Complexity: O(V+E)
2) Traverse the list for every node and then increment the in-degree of all the nodes connected to it by 1.
for each node in Nodes
If (list[node].size()!=0) then
for each dest in list
indegree[dest]++;Time Complexity: The outer for loop will be executed V number of times and the inner for loop will be executed E number of times, Thus overall time complexity is O(V+E).
The overall time complexity of the algorithm is O(V+E)”[1]
class Solution:
def findOrder(self, n: int, prerequisites: List[List[int]]) -> List[int]:
graph = collections.defaultdict(list)
indegrees = [0]*n
for dest, src in prerequisites:
graph[src].append(dest)
indegrees[dest]+=1
zero_indegree_q= collections.deque([i for i in range(n) if indegrees[i]==0])
res = []
while zero_indegree_q:
i = zero_indegree_q.popleft()
res.append(i)
for j in graph[i]:
indegrees[j]-=1
if indegrees[j]==0:
zero_indegree_q.append(j)
return res if len(res)==n else []Reference
[1] https://www.geeksforgeeks.org/topological-sorting-indegree-based-solution/
