Topological Sort

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s