【17】数据结构之图及图的存储篇章

图的定义Graph

• 图结构研究数据元素之间多对多的关系，任意一个顶点都可以有零个或多个前驱结点，也可以有零个或多个后继结点，亦可以作为起始顶点或终结顶点.
• Graph可简化为顶点(Vertex)和边(Edge)组合.采用形式化的定义表示一个图G=(V, R).
• G表示图，V表示顶点的非空有限集，R表示边的有限集，可为空集.

图的基本术语

顶点与邻接点

• 若P<x,y>属于V表示顶点x和顶点y之间的一条连线，则称x、y为该边的两个顶点，同时称x和y互为邻接点.且称边P<x，y>依附于顶点x和顶点y，或者称边P<x,y>与顶点x、顶点y相关联.

有向图与无向图

• 有向图：若一条边从x指向y，则称x为起点，y为终点.称这条边为弧.此时构成的图为有向图.(线条有箭头)
  
• 无向图：若当边P<x，y>属于V时必有边P<x，y>属于V，则E是对称的.且顶点x和y不分起点和终点，此时以无序对(x，y)来表示x与y之间的一条边，称构成的图为无向图.(线条无箭头)
  
  • 其中：
  • 边有方向有箭头，则称为弧
  • 否则称为边

顶点的度degree

• 指依附于某顶点v的边数，记为D(v).
• 无向图顶点的度：关联于该顶点的边的数目，记为D(v).
• 有向图顶点的度：
  • 以顶点v为终点的边的数目，称为v的入度，记为ID(v).
  • 以顶点v为起点的边的数目，称为v的出度，记为OD(v).
  • 顶点v的度定义为该顶点的入度与出度之和，即D(v)=ID(v)+OD(v)
  • 边数与顶点的度的关系为$$e=\frac{1}{2}\sum _{i=1}^{n}D(v_i)$$

路径

• 存在一个图G,从一个顶点p到另一个顶点q的路径为一个顶点序列，假如这个序列为(p,v1,v2,…,vn,q)，此序列就是p到q的一条路径.
• 路径长度值一条路径上的边的数目
• 若一条路径上除了起点和终点，其余顶点各不相同，则称该路径为简单路径.

回路

• 起点和终点相同的路径称为回路.
• 起点和终点相同的简单路径称为简单回路.
• 以上图为例：(3,2,4,3)为一条路径，也是简单路径，同时也是回路.

连通图与强连通图

• 连通图(无向图)：在无向图中，若从顶点u到顶点v有一条路径，则称顶点u和v在图G中是连通的，若G图中的任意两个不同的顶点都连通，则称G为连通图.
• 强连通图(无向图)：在有向图G中，若对G中任意两个不同的顶点u和v，都存在从u到v和从v到u的路径，则称G为强连通图.
  

稀疏图和稠密图

• 稀疏图：有很少条边的图.即n为顶点数，e为边数$$(e<n\log n)$$
• 稠密图：与稀疏图相反的图.

赋权图或网

权具有某种实际意义，将其与边或者弧相关起来的数据信息称为权weight.而边带有权值的图称为赋权图或网.

• 若无向图的每一条边都带一个权，则相应的图称无向赋权图或无向网.
• 若有向图的每一条边都带一个权，则相应的图称有向赋权图或有向网.
  

完全图

完全图是具有最多的边数、任一对顶点都有边相连的图.若在一个完全图中，顶点树为n，边数为e.则存在：

• 对于无向图而言，若e=n(n-1)/2，则该图称为完全的无向图.
• 对于有向图而言，若e=n(n-1)，则该图称为完全的无向图.
  

子图

假设有两个图分别为G=(V,R)，和G’=(V’,R’)，若V’是V的子集，R’是R的子集，则称图G’是图G的子图.

图的存储结构

图的存储结构有邻接矩阵、邻接表、十字链表和邻接多重表等.

邻接矩阵

• 核心定义公式$$A[i][j]=\{\begin{array}{ll}1,& ⟨v_i,v_j⟩\text{ 或 }(v_i,v_j)\in V\\ 0,& \text{其他}\end{array}$$
• 其中，i和j是顶点，若任意两顶点连通则A中对应位置为1，否则为0
• 例如：下图无向图的矩阵为$$A=\left[\begin{array}{cccc}0& 1& 0& 1\\ 1& 0& 1& 0\\ 0& 1& 0& 1\\ 1& 0& 1& 0\end{array}\right]$$
  
• 若为赋权图，则矩阵中的1对应具体的权重.
• 代码实现

class GraphMatrix:
    def __init__(self, vertex=[], matrix=[]):
        self.vertex = vertex  # 顶点列表
        self.matrix = matrix  # 邻接矩阵

    def getPosition(self, v):
        """返回顶点v在矩阵中的下标"""
        for i in range(len(self.vertex)):
            if v == self.vertex[i]:
                return i
        return -1  # 修正：遍历完所有顶点后返回-1

    def addEdge(self, edges):
        """添加边集合（无向图）"""
        for edge in edges:
            p1 = self.getPosition(edge[0])
            p2 = self.getPosition(edge[1])
            if p1 == -1 or p2 == -1:
                raise ValueError("顶点不存在")
            self.matrix[p1][p2] = 1
            self.matrix[p2][p1] = 1  # 无向图需要对称设置

    def ID(self, v):
        """计算顶点入度（无向图入度=出度）"""
        index = self.getPosition(v)
        if index == -1:
            return 0
        return sum(row[index] for row in self.matrix)  # 修正：遍历所有行的index列

    def OD(self, v):
        """计算顶点出度"""
        index = self.getPosition(v)
        if index == -1:
            return 0
        return sum(self.matrix[index])  # 当前行的和即为出度

    def traversal(self):
        """打印邻接矩阵"""
        # 打印列标题
        print("   ", end="")
        for v in self.vertex:
            print(f"{v:2}", end=" ")
        print("\n  +" + "-" * (3 * len(self.vertex)))

        # 打印矩阵行
        for i, row in enumerate(self.matrix):
            print(f"{self.vertex[i]} |", end="")
            for val in row:
                print(f"{val:2}", end=" ")
            print()


# ---------------------- 测试用例 ----------------------
if __name__ == "__main__":
    # 正确测试数据（顶点与边类型一致）
    nodes = [0, 1, 2, 3]
    matrix = [
        [0, 1, 0, 1],
        [1, 0, 1, 0],
        [0, 1, 0, 1],
        [1, 0, 1, 0]
    ]

    gm = GraphMatrix(vertex=nodes, matrix=matrix)

    print("邻接矩阵：")
    gm.traversal()

    print("\n顶点3的度：", gm.ID(3))  # 正确：2
    print("顶点1的度：", gm.OD(1))  # 正确：2

邻接表

• 邻接表结点和头结点的结构
  

• 其中：data值域，存储顶点的值

• firstEdge指针域，存储依附于该顶点的第一条边

• adjVex值域，存储该顶点的邻接点在顶点列表中的下标值

• nextEdge指针域，存储指向邻接表中下一个结点的指针

• info数据域，存储权值的信息

• 实例

• 代码实现

# 无权无方向的无向图
class Edge(object):
    def __init__(self, adjVex):
        self.adjVex = adjVex  # 相邻顶点的索引
        self.nextEdge = None   # 指向下一个边的指针

class Vertex(object):
    def __init__(self, data):
        self.data = data       # 顶点的数据（如顶点的名称）
        self.firstEdge = None  # 指向第一条边的指针

class UndirectedUnweightedGraph(object):
    def __init__(self, vers, edges):
        self.vers = vers               # 顶点列表
        self.edges = edges             # 边列表
        self.vexLen = len(self.vers)  # 顶点数量
        self.edgeLen = len(self.edges) # 边数量
        self.listVex = [Vertex for i in range(self.vexLen)]  # 初始化顶点列表
        for i in range(self.vexLen):
            self.listVex[i] = Vertex(self.vers[i])  # 创建顶点对象
        for i in range(self.edgeLen):
            c1 = self.edges[i][0]  # 获取边的起点
            c2 = self.edges[i][1]  # 获取边的终点
            self.addEdge(c1, c2)    # 添加边

    def addEdge(self, c1, c2):
        p1 = self.getPosition(c1)  # 获取起点的索引
        p2 = self.getPosition(c2)  # 获取终点的索引
        edge2 = Edge(p2)           # 创建从 p1 到 p2 的边
        edge1 = Edge(p1)           # 创建从 p2 到 p1 的边（因为是无向图）
        if self.listVex[p1].firstEdge is None:
            self.listVex[p1].firstEdge = edge2  # 如果 p1 没有第一条边，直接设置
        else:
            self.linkLast(self.listVex[p1].firstEdge, edge2)  # 否则将新边添加到链表末尾
        if self.listVex[p2].firstEdge is None:
            self.listVex[p2].firstEdge = edge1  # 如果 p2 没有第一条边，直接设置
        else:
            self.linkLast(self.listVex[p2].firstEdge, edge1)  # 否则将新边添加到链表末尾

    def linkLast(self, list, edge):
        p = list  # 从链表的头部开始
        while p.nextEdge:
            p = p.nextEdge  # 遍历链表直到找到最后一个节点
        p.nextEdge = edge  # 将新边添加到链表末尾

    def getPosition(self, key):
        for i in range(self.vexLen):
            if self.listVex[i].data is key:
                return i  # 返回顶点的索引
        return -1  # 如果顶点不存在，返回 -1

    def display(self):
        for i in range(self.vexLen):
            print(f"{self.listVex[i].data} -> ", end="")  # 打印当前顶点
            edge = self.listVex[i].firstEdge
            while edge:
                print(f"{self.listVex[edge.adjVex].data} ", end="")  # 打印相邻顶点
                edge = edge.nextEdge
                if edge:
                    print("-> ", end="")  # 如果还有下一个相邻顶点，打印 "->"
            print()  # 换行


# ---------------------- 测试用例 ----------------------
if __name__ == "__main__":
    vers = ['A', 'B', 'C', 'D']  # 顶点列表
    edges = [
        ['A', 'B'], ['A', 'D'], ['B', 'C']
    ]  # 边列表
    G = UndirectedUnweightedGraph(vers, edges)  # 创建图
    G.display()  # 打印邻接表

十字链表

• 表结点和头结点

• 头结点

  • data值域，存储顶点的值
  • firstIn指针域，存储指向以该顶点为弧头的顶点
  • firstOut指针域，存储执行以该顶点为弧尾的顶点

• 表结点

  • headvex值域，存储该弧的头顶点的位置
  • tailvex值域，存储该弧的尾顶点的位置
  • tlink指针域，存储弧尾相同的结点
  • hlink指针域，存储弧头相同的结点
  • info数据域，存储权值信息

• 代码实现

# 十字链表存储形式
class Vertex:
    """顶点类，包含数据、入边链表头指针和出边链表头指针"""

    def __init__(self, data):
        self.data = data  # 顶点数据
        self.first_in = None  # 以该顶点为终点的边链表头指针
        self.first_out = None  # 以该顶点为起点的边链表头指针


class Edge:
    """边类，十字链表存储结构"""

    def __init__(self, head_vex, tail_vex):
        self.head_vex = head_vex  # 弧头顶点索引（边的终点）
        self.tail_vex = tail_vex  # 弧尾顶点索引（边的起点）
        self.hlink = None  # 同一终点的下一条边
        self.tlink = None  # 同一起点的下一条边


class OrthogonalList:
    """十字链表有向图"""

    def __init__(self, vertexs, edges):
        # 顶点初始化
        self.vertex_list = [Vertex(v) for v in vertexs]
        self.vertex_num = len(vertexs)

        # 边初始化
        for from_v, to_v in edges:
            self.add_edge(from_v, to_v)

    def add_edge(self, from_v, to_v):
        """添加有向边"""
        # 获取顶点索引
        head_vex = self._get_vertex_index(from_v)  # 起点索引
        tail_vex = self._get_vertex_index(to_v)  # 终点索引

        if head_vex == -1 or tail_vex == -1:
            raise ValueError("顶点不存在")

        # 创建边对象
        new_edge = Edge(head_vex, tail_vex)

        # 添加到起点的出边链表（头插法）
        new_edge.tlink = self.vertex_list[head_vex].first_out
        self.vertex_list[head_vex].first_out = new_edge

        # 添加到终点的入边链表（头插法）
        new_edge.hlink = self.vertex_list[tail_vex].first_in
        self.vertex_list[tail_vex].first_in = new_edge

    def _get_vertex_index(self, key):
        """根据顶点值查找索引"""
        for idx in range(self.vertex_num):
            if self.vertex_list[idx].data == key:  # 使用值比较而非对象标识
                return idx
        return -1

    def in_degree(self, vertex):
        """计算顶点入度"""
        count = 0
        edge = vertex.first_in
        while edge:
            count += 1
            edge = edge.hlink
        return count

    def out_degree(self, vertex):
        """计算顶点出度"""
        count = 0
        edge = vertex.first_out
        while edge:
            count += 1
            edge = edge.tlink
        return count


# ---------------------- 测试用例 ----------------------
if __name__ == "__main__":
    # 测试数据
    vertices = [1, 2, 3, 4, 5, 6]
    edges = [
        (1, 2), (4, 5), (1, 3), (1, 4), (2, 4),
        (2, 5), (2, 6), (3, 5), (5, 1), (4, 6)
    ]

    # 创建图
    graph = OrthogonalList(vertices, edges)

    # 验证顶点1的出入度
    v1 = graph.vertex_list[0]
    print(f"顶点1的入度: {graph.in_degree(v1)}")  # 正确应输出1
    print(f"顶点1的出度: {graph.out_degree(v1)}")  # 正确应输出3

    # 打印顶点连接信息
    print("\n顶点1的出边：")
    edge = v1.first_out
    while edge:
        print(f"{vertices[edge.head_vex]}->{vertices[edge.tail_vex]}")
        edge = edge.tlink

邻接多重表

• 头结点和表结点
  

• 头结点

  • data值域，存储顶点的值
  • firstEdge指针域，存储依附于该顶点的第一条边

• 表结点

  • flag标志位，标志该表结点是否已被访问
  • verTex1值域，存储图中一条边一端的顶点所在数组中的位置下标
  • verTex2值域，存储图中一条边另一端的顶点所在数组中的位置下标
  • link1指针域，指向下一个存储与verTex1有直接关联顶点的结点
  • link2指针域，指向下一个存储与verTex2有直接关联顶点的结点

• 示意图