Python 图数据结构实现 - 邻接表

import re
class Vertex:
    # 定义顶点类
    def __init__(self, key):
        # 初始化顶点类，每个顶点有一个唯一的key作为标识
        self.id = key
        # 用于保存与该顶点相连的其他顶点及其连接权重
        self.connectedTo = {}

    def addNeighbor(self, nbr, weight=0):
        # 添加与该顶点相连的另一个顶点及其连接权重
        self.connectedTo[nbr] = weight

    def __str__(self):
        # 返回该顶点的字符串表示，包括顶点的key和与其相连的顶点的key
        return str(self.id) + ' connectedTo: ' + str([x.id for x in self.connectedTo])

    def getConnections(self):
        # 返回与该顶点相连的所有顶点的key
        return self.connectedTo.keys()

    def getId(self):
        # 返回该顶点的key
        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):
        # 获取图中指定key的顶点
        if n in self.vertList:
            return self.vertList[n]
        else:
            return None

    def __contains__(self, n):
        # 判断图中是否包含指定key的顶点
        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):
        # 获取图中所有顶点的key
        return self.vertList.keys()

    def __iter__(self):
        # 迭代器，用于遍历图中的所有顶点
        return iter(self.vertList.values())

# 创建一个图实例
g = Graph()
# 添加6个顶点到图中
for i in range(6):
    g.addVertex(i)

print(g.vertList)

# 添加边连接顶点
g.addEdge(0, 1, 5)
g.addEdge(0, 5, 2)
g.addEdge(1, 2, 4)
g.addEdge(2, 3, 9)
g.addEdge(3, 4, 7)
g.addEdge(3, 5, 3)
g.addEdge(4, 0, 1)
g.addEdge(5, 4, 8)
g.addEdge(5, 2, 1)

# 遍历图中的每个顶点，并打印与其相连的顶点及连接权重
for v in g:
    for w in v.getConnections():
        temp=w.getId()
        number=g.vertList[w.getId()]
        print("( %s , %s , %s )" % (v.getId(), w.getId(), v.connectedTo[number]))