数据结构与算法-图

基于邻接矩阵实现的图

图（graph）是一种非线性数据结构，由顶点（vertex）和边（edge）组成。我们可以将图 抽象地表示为一组顶点 和一组边
的集合

# 图节点与邻接矩阵初始化
class graph:
    def __init__(self,vertex=[],edges=[]):
        # 初始化顶点
        self._vertex = []
        for ver in  vertex:
            self._vertex.append(ver)
        # 基于列表推导式初始化二维邻接矩阵
        self._adjmatrx = [[0 for _ in range(len(self._vertex))] for _ in range(len(self._vertex))]
        for edge in edges:
            self.addedge(edge[0],edge[1])
    # 图中顶点数量与邻接矩阵大小
    def size(self):
        self.size = len(self._vertex)
        return self.size 
        # 添加顶点
    def addvertex(self,vertex):
        self._vertex.append(vertex)
        # 临接矩阵添加一行
        row = [0]*len(self._vertex)
        self._adjmatrx.append(row)
        # 每行添加一列
        for rows in self._adjmatrx:
            rows.append(0)
    # 添加边
    def addedge(self,e1:int,e2:int):
        # 对应邻接矩阵位置设置为1
        self._adjmatrx[e1][e2] = 1
        self._adjmatrx[e2][e1] = 1

    # 删除边
    def remove(self,e1:int,e2:int):
        # 对应位置置为0
        self._adjmatrx[e1,e2] = 0
        self._adjmatrx[e2,e1] = 0

    # 删除顶点
    def remove_vertex(self,vertex):
        if self._vertex == []:
            raise IndexError("索引错误")
        # 删除顶点
        self._vertex.remove(vertex)
        # 删除对应行
        self._adjmatrx.pop(vertex)
        for rows in self._adjmatrx:
            rows.pop(vertex)
    def print(self):
        # 打印顶点及其相邻的边
        # 顶点
        print(self._vertex)
        # 打印边
        print(self._adjmatrx)

测试

# 起始点为0
gh = graph([0,1,2,3],[[0,1],[1,3]])
gh.print()
gh.addvertex(4)
gh.print()
gh.remove_vertex(2)
gh.print()