首页
学习
活动
专区
工具
TVP
发布
社区首页 >问答首页 >如何在python中使用BFS Algo打印顶点?

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

Stack Overflow用户
提问于 2018-07-22 19:59:14
回答 1查看 244关注 0票数 0

问题出在这一行中,我无法获得当前连接到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)

我如何解决这个问题?

EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/51464892

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档