Python数据结构之图的存储结构详解

什么是图

图是一种数据结构，用于表示不同对象之间的关系。在图中，对象通常表示为称为顶点的节点，而它们之间的关系称为边。边可以是无向的（没有方向）或有向的（有方向）。图分为有向图和无向图两种类型，根据边是否有方向来区别。

无向图

在无向图中，边没有方向，例如下图：

A -- B
|    |
C -- D

上面的图表示四个顶点 A，B，C 和 D 之间的关系，它们之间的边是无向的。例如，从顶点 A 到顶点 D 有两条路径： A -> B -> D 和 A -> C -> D。

有向图

在有向图中，边是有方向的，例如下图：

A -> B
|    |
v    v
C <- D

上图表示四个顶点 A，B，C 和 D 之间关系的有向图。它们之间的边是有方向的。例如，顶点 A 到顶点 D 之间的路径是 A -> C -> D。

图的存储结构

图的存储结构包含两种方式：邻接矩阵和邻接表。

邻接矩阵

邻接矩阵使用二维数组来表示图的顶点之间的关系。如果一个图有 N 个顶点，那么它的邻接矩阵就是 N x N 的方阵。数组中的每个元素表示一条边，如果两个顶点之间存在边，则它们之间的值为 1，否则为 0。

例如，下面的图可以用邻接矩阵来表示：

     A    B    C
A    0    1    1
B    1    0    1
C    1    1    0

上图中，每一行和每一列代表一个顶点，如果两个顶点之间有连线，则矩阵中对应位置的值为 1，否则为 0。

邻接表

邻接表使用链式数据结构来表示图的顶点之间的关系。邻接表的每个顶点都使用一个链表来存储与它相关的顶点。对于一个无向图，图中的每个顶点都与与它相邻的顶点相连。对于一个有向图，每个顶点有两个链表，一个链表存储指向该顶点的所有顶点，另一个链表存储该顶点可以到达的所有顶点。

例如，下面的图可以用邻接表来表示：

A -> B -> C
B -> A -> C
C -> A -> B

上图中，每一行代表一个顶点和与它相关的所有顶点的链表。在这个例子中，每个链表都只有一个节点，因为每个顶点只与另外两个顶点相连。

示例说明

使用邻接矩阵表示图

以下 Python 代码示例演示了如何使用邻接矩阵来表示一个无向图：

class Graph:
    def __init__(self, num_vertices):
        self.num_vertices = num_vertices
        self.adjacency_matrix = [[0] * num_vertices for _ in range(num_vertices)]

    def add_edge(self, i, j):
        self.adjacency_matrix[i][j] = 1
        self.adjacency_matrix[j][i] = 1

    def __repr__(self):
        return '\n'.join([' '.join([str(self.adjacency_matrix[i][j]) for j in range(self.num_vertices)]) for i in range(self.num_vertices)])

g = Graph(4)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(2, 3)

print(g)

输出结果如下：

0 1 1 0
1 0 1 0
1 1 0 1
0 0 1 0

使用邻接表表示图

以下 Python 代码示例演示了如何使用邻接表来表示一个无向图：

class Node:
    def __init__(self, val):
        self.val = val
        self.neighbors = []

class Graph:
    def __init__(self):
        self.adjacency_list = {}

    def add_edge(self, node1, node2):
        if node1 not in self.adjacency_list:
            self.adjacency_list[node1] = Node(node1)
        if node2 not in self.adjacency_list:
            self.adjacency_list[node2] = Node(node2)
        self.adjacency_list[node1].neighbors.append(self.adjacency_list[node2])
        self.adjacency_list[node2].neighbors.append(self.adjacency_list[node1])

    def __repr__(self):
        res = ""
        for node in self.adjacency_list:
            res += str(node) + " -> "
            for neighbor in self.adjacency_list[node].neighbors:
                res += str(neighbor.val) + " "
            res += "\n"
        return res

g = Graph()
g.add_edge("A", "B")
g.add_edge("A", "C")
g.add_edge("B", "C")
g.add_edge("C", "D")

print(g)

输出结果如下：

A -> B C 
B -> A C 
C -> A B D 
D -> C