Python实现图(Graph)数据结构的方法

图(Graph)是一种非常常见的数据结构，用于表示对象间的关系。Python提供了多种方式来实现图数据结构，下面将介绍两种常见的方法：邻接矩阵和邻接表。

1. 邻接矩阵(Adjacency Matrix)：

邻接矩阵是一个二维数组，其中行和列表示图中的节点，矩阵中的值表示节点之间的连接关系。如果节点i和节点j之间有边，则矩阵中(i, j)和(j, i)位置的值为1，否则为0。对于有权图，可以将矩阵中的值设置为权重值。

以下是使用邻接矩阵表示无向图的示例代码：

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

    def add_edge(self, src, dest):
        self.adj_matrix[src][dest] = 1
        self.adj_matrix[dest][src] = 1

    def print_graph(self):
        for row in self.adj_matrix:
            print(row)

# 创建一个具有5个节点的图
g = Graph(5)
g.add_edge(0, 1)
g.add_edge(0, 4)
g.add_edge(1, 2)
g.add_edge(1, 3)
g.add_edge(1, 4)
g.add_edge(2, 3)
g.add_edge(3, 4)
g.print_graph()

运行上述代码会输出以下邻接矩阵：

[0, 1, 0, 0, 1]
[1, 0, 1, 1, 1]
[0, 1, 0, 1, 0]
[0, 1, 1, 0, 1]
[1, 1, 0, 1, 0]

2. 邻接表(Adjacency List)：

邻接表是用链表或数组的形式表示图的一种方式。每个节点对应一个链表，链表中存储了与该节点相邻的节点。对于有权图，可以将链表节点中的值设置为权重值。

以下是使用邻接表表示无向图的示例代码：

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

class Graph:
    def __init__(self, vertices):
        self.vertices = vertices
        self.adj_list = [None] * vertices

    def add_edge(self, src, dest):
        node = Node(dest)
        node.next = self.adj_list[src]
        self.adj_list[src] = node

        node = Node(src)
        node.next = self.adj_list[dest]
        self.adj_list[dest] = node

    def print_graph(self):
        for i in range(self.vertices):
            current = self.adj_list[i]
            print(f"Adjacency list of vertex {i}")
            while current:
                print(f" -> {current.value}", end="")
                current = current.next
            print()

# 创建一个具有5个节点的图
g = Graph(5)
g.add_edge(0, 1)
g.add_edge(0, 4)
g.add_edge(1, 2)
g.add_edge(1, 3)
g.add_edge(1, 4)
g.add_edge(2, 3)
g.add_edge(3, 4)
g.print_graph()

运行上述代码会输出以下邻接表：

Adjacency list of vertex 0
 -> 4 -> 1
Adjacency list of vertex 1
 -> 4 -> 3 -> 2 -> 0
Adjacency list of vertex 2
 -> 3 -> 1
Adjacency list of vertex 3
 -> 4 -> 1 -> 2
Adjacency list of vertex 4
 -> 3 -> 1 -> 0

这样，我们就通过邻接矩阵和邻接表两种方法实现了图数据结构。可以根据具体需求选择适合的实现方式。