Sometimes you might need to traverse the graph in a bit different way. (not DFS or BFS)

Suppose each tree node represent a course. Each course has some prerequisites .

Eg: For taking Android course you need to have taken Java course.

If you want to print the dependency of all nodes in sequential way, you can perform `Topological sort`.

/- Algorithms \ Maths -> \-> Java -> Android developement \- Datastructure/

We can traverse in Maths, Algo, DS, Java, Android dev.

Concept:

Similar to Depth first search, we add a node to the output list only after we have traversed through all it’s childrens.

Note: Such a sorting is not possible if the graph cyclic. (Deadlock).

Here is the python implementation:

''' Topological Sort ''' from collections import deque from collections import defaultdict def topo_sort(adj_list, nodes): visited = set() stack = deque() for each_node in range(nodes): if each_node not in visited: dfs_search(each_node, visited, stack, adj_list) return list(stack) def dfs_search(current_node,visited, stack, adj_list): visited.add(current_node) for each_neighbour in adj_list[current_node]: if each_neighbour not in visited: dfs_search(each_neighbour, visited, stack, adj_list) stack.appendleft(current_node) class Graph: def __init__(self,vertices): self.graph = defaultdict(list) self.V = vertices def addEdge(self,u,v): self.graph[u].append(v) g = Graph(6) g.addEdge(5, 2); g.addEdge(5, 0); g.addEdge(4, 0); g.addEdge(4, 1); g.addEdge(2, 3); g.addEdge(3, 1); print topo_sort(g.graph, g.V)

Advertisements