所以我在做一个项目,我必须找到最好的可能的路径…所以我现在用DFS来做这个,问题是在recursive call中,它打印所有可能的结果,最后打印出最好的结果。但是这些值不会存储在类的“PathList”变量列表中。你知道吗
例如:The图形.py是存储图形的另一个文件
import Graph
class G:
def __init__(self,Graph,vis):
self.graph = Graph
self.dist=1000000
self.PathList= []
self.stack=[]
self.visited=vis
def addEdge(self, u,v):
self.graph[u].append(v)
def DFScall(self,v,f,dis):
self.visited[v]=True
self.stack.append(v)
dis+=1
if(v==f):
if(dis<self.dist):
self.PathList = self.stack
self.dist=dis
#print(self.PathList)
else :
for i in self.graph[v]:
if self.visited[i] == False:
#print(self.visited[i])
self.DFScall(i,f,dis)
self.stack.pop()
self.visited[v]=False
def DFS(self,v,f):
self.DFScall(v,f,0)
def returnPath(self):
return self.PathList
if __name__== "__main__":
graph=Graph.returnGraph()
vis=Graph.returnNodes()
g = G(graph,vis)
g.DFS('S1','B8')
Pathlist = g.returnPath()
print(Pathlist)
输出为:
['S1', 'F0', 'E1', 'D0', 'C1', 'C2', 'B3', 'B4', 'C5', 'D4', 'D3', 'E2', 'F3', 'G2', 'H3', 'I2', 'J3', 'J4', 'I5', 'H4', 'G5', 'F4', 'E5', 'E6', 'D7', 'C6', 'B7', 'B8']
['S1', 'F0', 'E1', 'D0', 'C1', 'C2', 'B3', 'B4', 'C5', 'D4', 'D3', 'E2', 'F3', 'G2', 'H3', 'H4', 'G5', 'F4', 'E5', 'E6', 'D7', 'C6', 'B7', 'B8']
['S1', 'F0', 'E1', 'D0', 'C1', 'C2', 'B3', 'B4', 'C5', 'D4', 'D3', 'E2', 'F3', 'F4', 'E5', 'E6', 'D7', 'C6', 'B7', 'B8']
['S1', 'F0', 'E1', 'D0', 'C1', 'C2', 'B3', 'B4', 'C5', 'D4', 'E5', 'E6', 'D7', 'C6', 'B7', 'B8']
['S1', 'F0', 'E1', 'D0', 'C1', 'C2', 'B3', 'B4', 'C5', 'C6', 'D7', 'D8', 'C9', 'B8']
['S1', 'F0', 'E1', 'D0', 'C1', 'C2', 'B3', 'B4', 'C5', 'C6', 'B7', 'B8']
['S1', 'F0', 'E1', 'E2', 'D3', 'D4', 'C5', 'C6', 'B7', 'B8']
[]
最后一个,列表输出是通过main调用时的输出…..在这种情况下,我应该做什么,告诉你是否有什么需要学习的东西。你知道吗
谢谢
问题是您没有创建最佳路径的副本。你应该做:
一个完整的例子(PEP8的易读性有变化):
我没有测试代码,因为我没有测试数据。你知道吗
这是因为你实际上并不是在复制
stack
替换为
或者
相关问题 更多 >
编程相关推荐