Topological sort using non-recursive DFS – Python implementation

def dfs(graph,start):
    path = []
    stack = [start]
    label = len(graph)
    result = {}
    while stack != []:
        #this for loop could be done in other ways also
        for element in stack:
            if element not in result:
                result[element] = label
                label = label – 1
        v = stack.pop()
        if v not in path: path.append(v)
        for w in reversed(graph[v]):
            if w not in path and not w in stack:
                stack.append(w)
    result = {v:k for k, v in result.items()}
    return path,result
#
#
#
#Input:
graph = { 1: [3], 3:[5,6] , 5:[4] , 4:[7], 7:[],6:[]}
print dfs(graph,1)
#
#
#
Output:
([1, 3, 5, 4, 7, 6], {1: 7, 2: 4, 3: 5, 4: 6, 5: 3, 6: 1})
#
Check the result with the sample.
        1
       /
      3
     /\
    5  6
   /
  4
 /
7
If you think that the solution is not good, pls write me a comment.
Advertisements

Tags: , ,

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

%d bloggers like this: