ADT Graph的实现：实例
ADT Graph的实现：顶点Vertex类
Vertex包含了顶点信息， 以及顶点连接边信息
class Vertex:
def __init__(self, key):
self.id = key
self.connectedTo = {
}
def addNeighbor(self, nbr, weight=0):
# nbr是顶点对象的key
self.connectedTo[nbr] = weight
def __str__(self):
return str(self.id) + ' connectedTo: ' + 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]
ADT Graph的实现：图Graph类
Graph保存了包含所有顶点的主表
class Grapgh:
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:
# 通过key查找顶点
return self.vertList[n]
else:
return None
def __contains__(self, n):
return n in self.vertList
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())
版权声明：本文不是「本站」原创文章，版权归原作者所有 | 原文地址: