errors in my implement of topological sort using python

Question

UPDATE

I did not use nested function in the following code,but the answer is wrong: {'s': 4, 't': 4, 'w': 4, 'v': 4}

I think the problem is in the recursive call,where n does not decrease when the functions call back,but I don't know how to revise it.

import unittest
#dfs
def dfs(graph,start,visited,n,topo_order):
        visited.add(start)
        for w in graph[start]:
            if w not in visited:
                dfs(graph,w,visited,n,topo_order)
        topo_order[start]=n
        n-=1
def topological_sort(graph):
    visited=set()
    n=len(graph)
    topo_order={}
    for v in graph:
        if v not in visited:
            dfs(graph,v,visited,n,topo_order)
    print(topo_order)
class topological_sort_test(unittest.TestCase):
    def test(self):
        file=[]
        with open('topological_test.txt') as f:
            data=f.read()
        data=data.split('\n')
        data=[i.split() for i in data]        
        G={}
        for lst in data:
            G[lst[0]]=lst[1:]
        topological_sort(G)
if __name__=='__main__':
    unittest.main()

Łukasz Rogalski · Accepted Answer · 2015-02-25 09:53:52Z

1

def dfs(graph,start)

Function declaration creates local scope for variables. To access any variable from outside you'll need to pass it as an argument to this function.

answered Feb 25, 2015 at 9:53

Łukasz Rogalski

23.3k10 gold badges63 silver badges93 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

errors in my implement of topological sort using python

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related