我在Python中发现了以下图形实现:
class Vertex:
def __init__(self,key):
self.id = key
self.connectedTo = {}
def addNeighbor(self,nbr,weight=0):
self.connectedTo[nbr] = weight
def getConnections(self):
return self.connectedTo.keys()
def getId(self):
return self.id
def getWeight(self,nbr):
return self.connectedTo[nbr]
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 getVertex(self,n):
if n in self.vertList:
return self.vertList[n]
else:
return None
def addEdge(self,f,t,cost=0):
if f not in self.vertList:
nv=self.addVertex(f)
if t not in self.vertList:
nv=self.addVertex(t)
self.vertList[f].addNeighbor(self.vertList[t], cost)
def getVertices(self):
return self.vertList.keys()
def __iter__(self):
return iter(self.vertList.values())
def main():
g=Graph()
for i in range(6):
g.addVertex(i)
g.addEdge(0,1,5)
g.addEdge(1,5,4)
g.addEdge(5,3,6)
g.addEdge(3,4,5)
for v in g:
for w in v.getConnections():
print v.getId(),",",w.getId(),",",v.getWeight(w)
if __name__=="__main__":
main()
程序执行得很好,但是我想知道作者是否放了一些多余的部分,比如在函数addEdge()
和{
在我看来,addEdge有一个从未使用过的赋值:
^{pr2}$还有一部分说:
if t not in self.vertList:
nv=self.addVertex(t)
在同一个方法中不做任何事情,而且变量nv根本没有使用。在我看来,这是一个有向图的实现,所以如果我想编程一个非有向图,它就足够了:
self.vertList[t].addNeighbor(self.vertList[f], cost)
所以我也可以去掉addVertex函数中返回的newVertex。我已经做了那些修改,程序仍然运行良好。当我重用这个类时,这些修改是好的并且不会带来任何奇怪的行为吗?在
最后一个问题,在那部分说:
for v in g:
for w in v.getConnections():
print v.getId(),",",w.getId(),",",v.getWeight(w)
它似乎只迭代G字典中那些有值的值而不是空值(我是指那些只有键的值),是这样吗?在
是的,我认为}是必要的,因为您需要添加顶点。
nv=
是多余的,但是{添加
self.vertList[t].addNeighbor(self.vertList[f], cost)
将生成一个无向图,为true。在不,它将迭代所有顶点,但只有那些具有连接(边)的顶点才会生成输出。在
相关问题 更多 >
编程相关推荐