Топологический тип python

Я закодировал решение для нерекурсивного 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 

Любые идеи, как его изменить?

  • Как сравнить кластеры?
  • Python-сито из Eratosthenes-Compact Python
  • Есть ли хороший способ сделать этот тип добычи?
  • Скорость вычисления мощности (в питоне)
  • Простая задача Python: быстрый побитовый XOR для буферов данных
  • Совместная фильтрация: неперсонализированное сходство предметов к элементу
  • С рекурсивной версией я могу легко сортировать:

     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 

  • Производительность OrderedDict (по сравнению с deque)
  • График анимации Python
  • Форматирование метки метки метки метки Matplotlib
  • Matplotlib: как построить категориальные данные по оси y?
  • Эффективное планирование университетских курсов
  • matplotlib 3D-диаграмма рассеяния с цветом маркера, соответствующим значениям RGB
  • 2 Solutions collect form web for “Топологический тип python”

    FWIW, вот какой-то код, который я обработал для нерекурсивной топологической сортировки.

     from collections import defaultdict, namedtuple from itertools import islice Results = namedtuple('Results', ['sorted', 'cyclic']) def topological_sort(dependency_pairs): 'Sort values subject to dependency constraints' num_heads = defaultdict(int) # num arrows pointing in tails = defaultdict(list) # list of arrows going out heads = [] # unique list of heads in order first seen for h, t in dependency_pairs: num_heads[t] += 1 if h in tails: tails[h].append(t) else: tails[h] = [t] heads.append(h) ordered = [h for h in heads if h not in num_heads] for h in ordered: for t in tails[h]: num_heads[t] -= 1 if not num_heads[t]: ordered.append(t) cyclic = [n for n, heads in num_heads.items() if heads] return Results(ordered, cyclic) if __name__ == '__main__': print( topological_sort('aa'.split()) ) print( topological_sort('ah bg cf ch di ed fb fg hd he ib'.split()) ) 
      #this algorithm gives the logic of topological sorting..if u want to run this #give adjacency mat of your choice and this algorithm works on graph elements ranging from 0 to na=[[0,0,1,0,0,0],[0,0,1,0,0,0],[0,0,0,1,1,0],[0,0,0,0,1,0],[0,0,0,0,0,0],[0,0,1,0,0,0]] vis=[0 for i in range(0,len(a))] s=[] orderstack=[]#stores the reverse order of topological sorted elements def dfs_for_topological_sorting(a,vis,i): vis[i]=1 x=0 for j in range(0,len(a[0])): if(a[i][j]==1 and vis[j]==0): x=1 s.append(j) #print(s) dfs_for_topological_sorting(a,vis,j) if(x==0 and len(s)!=0): orderstack.append(s[len(s)-1]) if(len(s)>0): dfs_for_topological_sorting(a,vis,s.pop()) for i in range(0,len(a)): if(i not in orderstack): s.append(i) dfs_for_topological_sorting(a,vis,i) print(orderstack[len(orderstack)-1::-1]) по  #this algorithm gives the logic of topological sorting..if u want to run this #give adjacency mat of your choice and this algorithm works on graph elements ranging from 0 to na=[[0,0,1,0,0,0],[0,0,1,0,0,0],[0,0,0,1,1,0],[0,0,0,0,1,0],[0,0,0,0,0,0],[0,0,1,0,0,0]] vis=[0 for i in range(0,len(a))] s=[] orderstack=[]#stores the reverse order of topological sorted elements def dfs_for_topological_sorting(a,vis,i): vis[i]=1 x=0 for j in range(0,len(a[0])): if(a[i][j]==1 and vis[j]==0): x=1 s.append(j) #print(s) dfs_for_topological_sorting(a,vis,j) if(x==0 and len(s)!=0): orderstack.append(s[len(s)-1]) if(len(s)>0): dfs_for_topological_sorting(a,vis,s.pop()) for i in range(0,len(a)): if(i not in orderstack): s.append(i) dfs_for_topological_sorting(a,vis,i) print(orderstack[len(orderstack)-1::-1]) по  #this algorithm gives the logic of topological sorting..if u want to run this #give adjacency mat of your choice and this algorithm works on graph elements ranging from 0 to na=[[0,0,1,0,0,0],[0,0,1,0,0,0],[0,0,0,1,1,0],[0,0,0,0,1,0],[0,0,0,0,0,0],[0,0,1,0,0,0]] vis=[0 for i in range(0,len(a))] s=[] orderstack=[]#stores the reverse order of topological sorted elements def dfs_for_topological_sorting(a,vis,i): vis[i]=1 x=0 for j in range(0,len(a[0])): if(a[i][j]==1 and vis[j]==0): x=1 s.append(j) #print(s) dfs_for_topological_sorting(a,vis,j) if(x==0 and len(s)!=0): orderstack.append(s[len(s)-1]) if(len(s)>0): dfs_for_topological_sorting(a,vis,s.pop()) for i in range(0,len(a)): if(i not in orderstack): s.append(i) dfs_for_topological_sorting(a,vis,i) print(orderstack[len(orderstack)-1::-1]) по  #this algorithm gives the logic of topological sorting..if u want to run this #give adjacency mat of your choice and this algorithm works on graph elements ranging from 0 to na=[[0,0,1,0,0,0],[0,0,1,0,0,0],[0,0,0,1,1,0],[0,0,0,0,1,0],[0,0,0,0,0,0],[0,0,1,0,0,0]] vis=[0 for i in range(0,len(a))] s=[] orderstack=[]#stores the reverse order of topological sorted elements def dfs_for_topological_sorting(a,vis,i): vis[i]=1 x=0 for j in range(0,len(a[0])): if(a[i][j]==1 and vis[j]==0): x=1 s.append(j) #print(s) dfs_for_topological_sorting(a,vis,j) if(x==0 and len(s)!=0): orderstack.append(s[len(s)-1]) if(len(s)>0): dfs_for_topological_sorting(a,vis,s.pop()) for i in range(0,len(a)): if(i not in orderstack): s.append(i) dfs_for_topological_sorting(a,vis,i) print(orderstack[len(orderstack)-1::-1]) 
    Python - лучший язык программирования в мире.