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

import re

# 定义顶点类
class Vertex:
    # 邻接列表构图，每个节点保存与本节点相连的节点
    def __init__(self, key):
        # 顶点的key
        self.id = key
        # 用于保存和哪些点相连，key为node的key，val为连接权重
        self.connectedTo = {}

    def addNeighbor(self, nbr, weight=0):
        # 添加与某个node的连接，连接key为该节点key，值为权重
        self.connectedTo[nbr] = weight

    def __str__(self):
        return str(self.id) + ' connectedTo: ' + str([x.id for x in self.connectedTo])

    # 获取与本节点相连的所有节点key
    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)
        # 这的key就是代表这个顶点的变量
        self.vertList[key] = newVertex
        # 此处为什么要将这个顶点返回呢
        return newVertex

    def getVertex(self, n):
        # 遍历图中所有的顶点
        if n in self.vertList:
            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())

g = Graph()
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]))

代码解释

1. import re

这行代码导入Python的正则表达式库，但在本代码中没有使用，可以删除。

2. class Vertex

定义一个名为Vertex的类，代表图中的一个顶点。
__init__(self, key)：构造函数，接受一个顶点标识key，并初始化顶点的id属性为key，以及一个字典connectedTo用来存储与当前顶点相连的邻居顶点及其边权。
addNeighbor(self, nbr, weight=0)：添加一个邻居顶点nbr，并设置其边权为weight。
__str__(self)：定义顶点对象的字符串表示，用于打印信息。
getConnections(self)：返回所有邻居顶点的key。
getId(self)：返回顶点的id。
getWeight(self, nbr)：返回当前顶点与给定邻居顶点nbr之间的边权。

3. class Graph

定义一个名为Graph的类，代表一个图。
__init__(self)：构造函数，初始化图的vertList属性为一个空字典，用于存储图的所有顶点，以及numVertices属性为0，记录图中顶点的数量。
addVertex(self, key)：添加一个新的顶点，并返回该顶点。
getVertex(self, n)：返回给定key的顶点。
__contains__(self, n)：判断图中是否包含给定key的顶点。
addEdge(self, f, t, cost=0)：添加一条边，连接顶点f和t，边权为cost。
getVertices(self)：返回所有顶点的key。
__iter__(self)：使图可迭代，返回一个遍历所有顶点的迭代器。

4. 示例代码

创建一个Graph对象。
添加6个顶点，编号为0到5。
添加几条边，分别连接不同顶点，并设置边权。
打印图中的所有边，输出格式为(源顶点, 目标顶点, 边权)。

这段代码展示了如何使用Python创建图数据结构，并添加顶点和边。其中，Vertex类使用字典存储与当前顶点相连的邻居顶点及其权重，实现了邻接表表示。Graph类则使用字典存储图中的所有顶点，并提供了一些操作方法，方便用户创建和操作图。