引言

前文介绍的树中，元素的关系是一对多，本章介绍一种多对多的数据结构——图。

图的定义

一个图是一个二元组G=(V,E)，其中：

• V是非空有穷的顶点集合；
• E是定点偶对(边)的集合，E是V×V的子集
• V的中的顶点称为图G的顶点，E中的边称为图G的边

图示：

上图被称为有向图，有向图的边有方向，是顶点的有序对；相对地，无向图的边没有方向，是顶点的无序对。

图的基本概念和性质

完全图：任意两个顶点之间都有边的图称为完全图，其性质如下：

• 有n个顶点的无向完全图有n×(n-1)/2条边
• 有n个顶点的有向完全图有n×(n-1)条边

度：一个顶点的度就是与它邻接的边的数目。度还分为出度和入度，出度指的是该顶点指向多少个顶点，入度指的是有多少个顶点指向该顶点。

路径：如果一个顶点能够到达另一个顶点，那么这两个顶点之间的边的组合称为路径。路径的性质如下：

• 路径长度=边的总数
• 环指的是起点和终点相同的路径
• 如果一个环除起点和终点外其他顶点都不相同，则称为简单环
• 如果一条路径中不存在环，则称为简单路径

有根图：如果在有向图G里存在一个顶点v，从顶点v到图G中其他每个顶点都有路径，则称呈图G为有根图，称v为图的一个根。

连通图：

• 连通：如果一个顶点能够到达另外一个顶点，则称它们是连通的
• 连通无向图：无向图中如果任意两个结点都能连通，则称该图为连通无向图
• 强连通有向图：无向图中如果任意两个结点都能相互连通，则称该图为强连通有向图
• 最小连通图：即去掉任何一条边，该图都无法成为连通图。此外，最小连通无向图的边为n-1(顶点有n个)
• 最小有根图：去掉任何一条边都无法称为有根图，其边数为n-1(顶点为n)

带权图：如果图G的每条边都被赋予权值，则称G为一个带权图。此外，带权的连通无向图也被称为网络。

图的基本操作

图的操作较多，主要有以下几种：

• 创建一个图
• 判断图是否为空
• 获得这个图的顶点个数
• 获得这个图的边数
• 获得这个图的顶点集合
• 获得这个图的边集合
• 向图中新增一个顶点
• 将从v1到v2的边加入这个图
• 获得v1到v2边的信息
• 取得从v出发的所有边
• 检查v的度

Python实现

图有以下两种常用的表示方法：

• 邻接矩阵表示法，缺点是邻接矩阵较为稀疏，存在很多无用信息，浪费空间
• 邻接表表示法，对邻接矩阵表示法的空间优化

邻接矩阵表示法实现

class Graph_mat:
    def __init__(self, mat, unconn=0):
        '''
        
        Parameters
        ----------
        mat : matrix
            图的邻接矩阵.
        uncon : float、string、int, etc.
            主要用于表示无关联时的数值. The default is 0.

        Returns
        -------
        None.

        '''
        vnum = len(mat) # 顶点数
        for x in mat:
            if len(x) != vnum:
                raise ValueError('mat必须是一个标准的邻接矩阵！')
        self.mat_ = [mat[i][:] for i in range(vnum)] # 拷贝mat
        self.unconn_ = unconn
        self.vnum_ = vnum
    
    # 获得顶点的数目
    def get_v_count(self):
        return self.vnum_
    
    # 判断顶点下标是否越界
    def vertex_invalid(self, v):
        return v < 0 or v >= self.vnum_
    
    # 加入顶点
    def add_vertex(self, val):
        self.mat_.append([self.unconn_ for _ in range(self.vnum_)])
        self.vnum_ += 1
        for x in self.mat_:
            x.append(self.unconn_)
        self.mat_[self.vnum_-1][self.vnum_-1] = val
            
    # 加入一条边
    def add_edge(self, v1, v2, val):
        if self.vertex_invalid(v1) or self.vertex_invalid(v2):
            raise IndexError('顶点下标越界！')
        self.mat_[v1][v2] = val
        
    # 获取任意边的信息
    def get_edge(self, v1, v2):
        if self.vertex_invalid(v1) or self.vertex_invalid(v2):
            raise IndexError('顶点下标越界！')
        return self.mat_[v1][v2]
    
    # 获取所有的出边信息
    @staticmethod
    def out_edges(row, unconn):
        output = []
        for i in range(len(row)):
            if row[i] != unconn:
                output.append([i, row[i]])
        return output


if __name__ == '__main__':
    mat = [[1,0,0,1], [0,1,0,0], [0,0,1,0], [1,0,0,1]]
    sample = Graph_mat(mat)
    print(sample.mat_)
    print('\n')
    
    print(sample.get_v_count())
    print('\n')
    
    sample.add_vertex(3)
    print(sample.mat_)
    print('\n')
    
    print(sample.get_edge(1, 2))
    print('\n')
    
    print(sample.out_edges(sample.mat_[0], 0))

邻接表表示法实现

class Graph_AL:
    def __init__(self, mat=[], unconn=0):
        vnum = len(mat)
        for x in mat:
            if len(x) != vnum:
                raise ValueError('mat必须是一个标准的邻接矩阵！')
        self.mat_  = [Graph_AL.out_edges(mat[i], unconn) for i in range(vnum)]
        self.vnum_ = vnum
        self.unconn_ = unconn
    
    # 获取所有顶点数目
    def get_v_count(self):
        return self.vnum_
    
    # 判断顶点下标是否越界
    def v_invalid(self, v):
        return v < 0 or v >= self.vnum_
    
    # 加入顶点
    def add_vertex(self, val):
        self.mat_.append([])
        self.vnum_ += 1
    
    # 加入边
    def add_edge(self, v1, v2, val):
        if self.vnum_ == 0:
            raise GraphError('顶点数量小于2，无法形成边！')
        if self.v_invalid(v1) or self.v_invalid(v2):
            raise IndexError('顶点下标越界！')
        row = self.mat_
        i = 0
        while i < len(row):
            # 如果已经存在这条边的连接，那么只需要修改权值
            if row[i][0] == v2:
                self.mat_[v1][v2] == [v2, val]
                return
            # 如果不存在这条边，那么跳出循环直接insert
            if row[i][0] > v2:
                break
            i += 1
        self.mat_[v1].insert(i, [v2, val])
        
    # 获取边的信息
    def get_edge(self, v1, v2):
        if self.vnum_ == 0:
            raise GraphError('顶点数量小于2，无法形成边！')
        if self.v_invalid(v1) or self.v_invalid(v2):
            raise IndexError('顶点下标越界！')
        for i, val in self.mat_[v1]:
            if i == v2:
                return val
        return self.unconn_
    
    # 获取所有的出边信息
    @staticmethod
    def out_edges(row, unconn):
        output = []
        for i in range(len(row)):
            if row[i] != unconn:
                output.append([i, row[i]])
        return output
    
    
if __name__ == '__main__':
    mat = [[1,0,0,1], [0,1,0,0], [0,0,1,0], [1,0,0,1]]
    sample = Graph_AL(mat)
    print(sample.mat_)
    print('\n')
    
    print(sample.get_v_count())
    print('\n')
    
    sample.add_vertex(3)
    print(sample.mat_)
    print('\n')
    
    print(sample.get_edge(0, 3))
    print('\n')

参考资料

1. 裘宗燕.数据结构与算法——Python语言描述[M].北京：机械工业出版社，2015: 224-229。
2. 菜鸟教程：Python staticmethod函数