python数据结构之图的实现方法

以下是关于“Python数据结构之图的实现方法”的完整攻略：

简介

图是一种常用的数据结构，用于表示对象之间的关系。在本教程中，我们将介绍如何使用Python实现图，包括邻接矩阵和邻接表两种实现方法。

邻接矩阵

邻接矩阵是一种常用的图的实现方法，它使用二维数组表示图中的节点和边。在邻接矩阵中，每个节点都对应数组中的一行和一列，如果两个节点之间有边相连，则在对应的数组元素中存储1，否则存储0。

以下是使用Python实现邻接矩阵的示例代码：

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

    def add_edge(self, u, v):
        self.matrix[u][v] = 1
        self.matrix[v][u] = 1

    def remove_edge(self, u, v):
        self.matrix[u][v] = 0
        self.matrix[v][u] = 0

    def print_graph(self):
        for i in range(self.vertices):
            for j in range(self.vertices):
                print(self.matrix[i][j], end=' ')
            print()

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()

在这个示例中，我们使用二维数组实现了邻接矩阵。我们定义了Graph类作为图的实现，使用matrix数组存储图的节点和边，使用add_edge函数添加边，使用remove_edge函数删除边，使用print_graph函数打印图的邻接矩阵。

邻接表

邻接表是一种常用的图的实现方法，它使用链表表示图中的节点和边。在邻接表中，每个节点都对应一个链表，链表中存储与该节点相连的所有节点。

以下是使用Python实现邻接表的示例代码：

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, u, v):
        node = Node(v)
        node.next = self.adj_list[u]
        self.adj_list[u] = node

        node = Node(u)
        node.next = self.adj_list[v]
        self.adj_list[v] = node

    def remove_edge(self, u, v):
        node = self.adj_list[u]
        if node.value == v:
            self.adj_list[u] = node.next
        else:
            while node.next:
                if node.next.value == v:
                    node.next = node.next.next
                    break
                node = node.next

        node = self.adj_list[v]
        if node.value == u:
            self.adj_list[v] = node.next
        else:
            while node.next:
                if node.next.value == u:
                    node.next = node.next.next
                    break
                node = node.next

    def print_graph(self):
        for i in range(self.vertices):
            print(i, end=' ')
            node = self.adj_list[i]
            while node:
                print('->', node.value, end=' ')
                node = node.next
            print()

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()

在这个示例中，我们使用链表实现了邻接表。我们定义了Node类作为链表节点，定义了Graph类作为图的实现，使用adj_list数组存储图的节点和边，使用add_edge函数添加边，使用remove_edge函数删除边，使用print_graph函数打印图的邻接表。

示例说明

以下是两个示例说明，展示了如何使用Python实现图。

示例1

假设我们要使用Python实现图，可以使用示例代码：

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

    def add_edge(self, u, v):
        self.matrix[u][v] = 1
        self.matrix[v][u] = 1

    def remove_edge(self, u, v):
        self.matrix[u][v] = 0
        self.matrix[v][u] = 0

    def print_graph(self):
        for i in range(self.vertices):
            for j in range(self.vertices):
                print(self.matrix[i][j], end=' ')
            print()

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()

可以看到，我们成功使用Python实现了图，并使用示例测试了函数的功能。

示例2

假设我们要使用Python实现图，可以使用示例代码：

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, u, v):
        node = Node(v)
        node.next = self.adj_list[u]
        self.adj_list[u] = node

        node = Node(u)
        node.next = self.adj_list[v]
        self.adj_list[v] = node

    def remove_edge(self, u, v):
        node = self.adj_list[u]
        if node.value == v:
            self.adj_list[u] = node.next
        else:
            while node.next:
                if node.next.value == v:
                    node.next = node.next.next
                    break
                node = node.next

        node = self.adj_list[v]
        if node.value == u:
            self.adj_list[v] = node.next
        else:
            while node.next:
                if node.next.value == u:
                    node.next = node.next.next
                    break
                node = node.next

    def print_graph(self):
        for i in range(self.vertices):
            print(i, end=' ')
            node = self.adj_list[i]
            while node:
                print('->', node.value, end=' ')
                node = node.next
            print()

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()

可以看到，我们成功使用Python实现了图，并使用示例测试了函数的功能。

结

本教程介绍了如何使用Python实现图，包括邻接矩阵和邻接表两种实现方法。我们使用二维数组实现了邻接矩阵，使用链表实现了邻接表。我们还提供了两个示例，展示了如何使用Python实现图。