如何在python中使用BFS Algo打印顶点?

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (1)
  • 关注 (0)
  • 查看 (82)

问题是在这一行(graph.vertList[currentVert].getConnections())我无法获取当前连接的所有连接节点的列表currentVert,当我打印此代码时,我得到所有连接的对象,print(g.vertList[1].getConnections()) dict_keys([<__main__.Vertex object at 0x7f7a7db9a3c8>, <__main__.Vertex object at 0x7f7a7db9a2e8>]) 我无法找到这些对象的节点(顶点)或id,以便,我可以轻松地从一个节点到另一个节点Tratra并同时打印结果。

我无法解决这个错误,这里是完整的代码: -

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)

我该如何解决这个问题?

提问于
用户回答回答于

问题出在这里:

self.vertList[f].addNeighbor(self.vertList[t],cost)

将此更改为

self.vertList[f].addNeighbor(t,cost)

它应该工作。

扫码关注云+社区

领取腾讯云代金券