python - トポロジカルソートpython

Question

DFS 非再帰のソリューションをコーディングしましたが、それを変更してトポロジカル ソートを作成することはできません。

def dfs(graph,start):
    path = []
    stack = [start]    
    while stack != []: 
        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) 
    return path

それを変更する方法はありますか？

再帰バージョンを使用すると、簡単にソートできます。

def dfs_rec(graph,start,path):
    path = path + [start]
    for edge in graph[start]: 
        if edge not in path:
            path = dfs_rec(graph, edge,path)
    print start
    return path

入力：

>>> graph = {
        1: [2, 3],
        2: [4, 5, 6],
        3: [4,6],
        4: [5,6],
        5: [6],
        6: []
    }
>>> dfs_rec(graph,1,[])
6
5
4
2
3
1
[1, 2, 4, 5, 6, 3]
>>> dfs(graph,1)
[1, 2, 4, 5, 6, 3]
>>> graph = {
        1: [3],
        3: [5,6],
        5: [4],
        4: [7],
        7: [],
        6: []
    }
>>> print dfs_rec(graph,1,[])
7
4
5
6
3
1
[1, 3, 5, 4, 7, 6]
>>> print dfs(graph,1)
[1, 3, 5, 4, 7, 6]

したがって、非再帰でもこの順序を取得する必要があります。

非再帰的な解決策:

これも解決策になると思います。間違っている場合はマークしてください。

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

入力：

graph = { 1: [3], 3:[5,6] , 5:[4] , 4:[7], 7:[],6:[]}
print dfs(graph,1) 

出力：

([1, 3, 5, 4, 7, 6], {1: 7, 2: 4, 3: 5, 4: 6, 5: 3, 6: 1})

        1
       / 
      3
     /\
    5  6
   /
  4
 /
7