ascii -字母拓扑排序

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...}行过滤可打印的元素，然后从所谓的图集中减去这些元素。
生成的集合是随机排序的，因此打印的输出必须在末尾转换为排序列表，这些列表以换行符分隔。