Ascialphabetic拓扑排序

Question

我一直在试图找出一个问题，在这个问题上，我的程序进行拓扑排序，但不是以我试图得到的格式。例如，如果我给它输入：

Learn Python
Understand higher-order functions
Learn Python
Read the Python tutorial
Do assignment 1
Learn Python 

它应该输出：

Read the python tutorial
Understand higher-order functions
Learn Python
Do assignment 1

相反，我在前两个实例被交换的地方得到了它，对于我的一些其他测试用例，这也发生在它将交换2个随机实例的地方，下面是我的代码：

import sys 
graph={}

def populate(name,dep):
    if name in graph:
        graph[name].append(dep)
    else:
        graph[name]=[dep]
        
    if dep not in graph:
        graph[dep]=[]
    

def main():
    last = ""
    for line in sys.stdin:
        lne=line.strip()
        if last == "":
            last=lne
        else:
            populate(last,lne)
            last=""
            
            
def topoSort(graph):
    sortedList=[] #result
    zeroDegree=[]
    inDegree = { u : 0 for u in graph }
    for u in graph:
        for v in graph[u]:
            inDegree[v]+=1
    for i in inDegree:
        if(inDegree[i]==0):
            zeroDegree.append(i)
    while zeroDegree:
        v=zeroDegree.pop(0)
        sortedList.append(v)
        #selection sort for alphabetical sort 
            
        for x in graph[v]:
            inDegree[x]-=1
            if (inDegree[x]==0):
                zeroDegree.insert(0,x)
    
    sortedList.reverse()
    
    #for y in range(len(sortedList)):
    #       min=y
    #       for j in range(y+1,len(sortedList)):
    #           if sortedList[min]>sortedList[y]:
    #               min=j
    #               sortedList[y],sortedList[min]=sortedList[min],sortedList[y]
            
    return sortedList
    
if __name__=='__main__':
    main()
    result=topoSort(graph)
    if (len(result)==len(graph)):
        print(result)
    else:
        print("cycle")

有没有关于为什么会发生这种情况的想法

Answer 1

字典或集合中的元素没有排序。如果添加元素，它们将随机插入，而不是附加到末端。我认为这就是为什么排序算法会得到随机结果的原因。我想它一定与inDegree有关，但我没有进行太多调试。
我无法为您的代码提供特定的修复，但根据所需的输入和输出，它应该如下所示：

# read tuples from stdin until ctrl+d is pressed (on linux) or EOF is reached
graph = set()
while True:
  try:
    graph |= { (input().strip(), input().strip()) }
  except:
    break

# apply topological sort and print it to stdout
print("  ")
while graph:
  z = { (a,b) for a,b in graph if not [1 for c,d in graph if b==c] }
  print ( "\n".join ( sorted ( {b for a,b in z} )
    + sorted ( {a for a,b in z if not [1 for c,d in graph if a==d]} ) ) )
  graph -= z

Python的最大优势（这里是3.9.1）是您可能得到的简短解决方案。我不使用列表，而是使用集合，因为这些集合可以更容易地编辑：graph|{elements}将项目插入到该集合中，graph-{elements}从其中删除实体。重复项将被忽略。
首先是一些从stdin中红色的元组，带有... = input(), input()进入图形项集中。
行z = {result loop condition...}过滤可打印元素，然后从所谓的图形集中减去这些元素。
生成的集合是随机排序的，因此打印输出必须转到末尾的排序列表中，这些列表用换行符分隔。