问题出在这一行中,我无法获得当前连接到currentVert
的所有已连接节点的列表,当我打印此代码时,我得到了all connected (graph.vertList[currentVert].getConnections())
print(g.vertList[1].getConnections()) dict_keys([<__main__.Vertex object at 0x7f7a7db9a3c8>, <__main__.Vertex object at 0x7f7a7db9a2e8>])
我无法找到这些对象的节点(顶点)或id,因此,我可以轻松地从一个节点遍历到另一个节点,并同时打印结果。
我找不到这个bug,下面是完整的代码:
class Queue:
def __init__(self):
self.queue=[]
def enqueue(self,item):
self.queue.insert(0,item)
def isEmpty(self):
return self.queue == []
def dequeue(self):
return self.queue.pop()
def size(self):
return len(self.queue)
然后我创建另一个class Vertex
:
class Vertex:
def __init__(self,key):
self.id=key
self.connectedTo={}
def addNeighbor(self,nbr,weight=0):
self.connectedTo[nbr]=weight
def __str__(self):
return str(self.id)+' Connected To : '+str([x.id for x in self.connectedTo])
def getConnections(self):
return self.connectedTo.keys()
def getId(self):
return self.id
def getWeight(self,nbr):
return self.connectedTo[nbr]
另一个class Graph
:
class Graph:
def __init__(self):
self.vertList={}
self.numVertices=0
def addVertex(self,key):
self.numVertices=self.numVertices+1
newVertex=Vertex(key)
self.vertList[key]=newVertex
return newVertex
def addEdges(self,f,t,cost=0):
if f in self.vertList:
if t in self.vertList:
self.vertList[f].addNeighbor(self.vertList[t],cost)
else:
return "Not present in Graph"
else:
return "Not present in Graph"
def getVertex(self,n):
if n in self.vertList:
return self.vertList[n]
else:
return None
def getVertices(self):
return self.vertList.keys()
之后,我创建了一个广度优先搜索( bfs
)函数:
def bfs(graph,start):
#Keep track of all visited nodes
visited=[]
#keep track of nodes to be checked using queue
vertQueue= Queue()
vertQueue.enqueue(start)
#Keep looking until there are nodes still to be checked
while vertQueue:
#pop shallowest node (first node ) from queue
currentVert=vertQueue.dequeue()
print(currentVert,end="")
for nbr in (graph.vertList[currentVert].getConnections()):
if nbr not in visited:
#add node to list of checked nodes
vertQueue.enqueue(nbr)
visited.append(currentVert)
我如何解决这个问题?
发布于 2018-07-26 06:13:58
问题出在这里:
self.vertList[f].addNeighbor(self.vertList[t],cost)
将其更改为
self.vertList[f].addNeighbor(t,cost)
它应该是有效的。
https://stackoverflow.com/questions/51464892
复制相似问题