当前位置：首页 > article >正文

Python 实现图：构建、添加和搜索详解

article 2024/11/5 14:10:14

在本篇文章中，我们将一起探讨如何在 Python 中实现图的数据结构。图是一种非常灵活的数据结构，它能够表示复杂的关系，比如社交网络、道路网络等。在本篇文章中，我们会实现一个简单的图，并支持添加顶点、添加边以及使用深度优先搜索 (DFS) 和广度优先搜索 (BFS) 两种常见的图遍历方法。

什么是图？

图 (Graph) 是一种由顶点 (vertices) 和边 (edges) 组成的数据结构，用于表示实体之间的关系。在图中，顶点是代表的实体，而边是这些实体之间的关系。根据边的方向性，图可以分为有向图和无向图。无向图中的边没有方向，而有向图中的边有方向。

图的代码实现

下面是使用 Python 实现的一个简单图结构。图由一个类 Graph 来实现，包含了各种操作方法，例如添加顶点、添加边以及对图进行遍历。

class Graph:
    def __init__(self):
        self.graph = dict()

    def add_vertex(self, vertex):
        """ 添加一个顶点到图中 """
        if vertex not in self.graph:
            self.graph[vertex] = []

    def add_edge(self, vertex1, vertex2):
        """ 添加一条无向边（vertex1 - vertex2） """
        if vertex1 not in self.graph:
            self.add_vertex(vertex1)
        if vertex2 not in self.graph:
            self.add_vertex(vertex2)
        self.graph[vertex1].append(vertex2)
        self.graph[vertex2].append(vertex1)

    def add_directed_edge(self, start, end):
        """添加一条有向边（start -> end）"""
        if start not in self.graph:
            self.add_vertex(start)
        if end not in self.graph:
            self.add_vertex(end)
        self.graph[start].append(end)

    def dfs(self, start, visited=None):
        """ 深度优先搜索 """
        if visited is None:
            visited = set()
        visited.add(start)
        print(start, end=" ")
        for neighbor in self.graph[start]:
            if neighbor not in visited:
                self.dfs(neighbor, visited)

    def bfs(self, start):
        """ 广度优先搜索 """
        visited = set()
        queue = [start]
        visited.add(start)
        while queue:
            vertex = queue.pop(0)
            print(vertex, end=" ")
            for neighbor in self.graph[vertex]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)

1. Graph 类

Graph 类是整个图的管理类，用于创建图结构，包含顶点和边。它提供了一些常见的图操作，如添加顶点、添加边、深度优先搜索 (DFS) 和广度优先搜索 (BFS) 方法。

❏ `init` 方法

在 Graph 类的初始化方法中，我们使用一个字典 (dict) 来存储图的结构。字典的键是顶点，值是与该顶点相连的其他顶点的列表。

❏ `add_vertex` 方法：添加顶点

add_vertex 方法用于向图中添加新的顶点。

如果顶点不在图中，则将其添加为键，并将值初始化为空列表，表示还没有相邻的顶点。

❏ `add_edge` 方法：添加无向边

add_edge 方法用于在两个顶点之间添加一条无向边。

首先确保两个顶点都已经存在于图中，如果不存在则调用 add_vertex 方法将其添加。
然后，在两个顶点之间互相添加对方到各自的邻接列表中，表示它们之间存在无向连接。

❏ `add_directed_edge` 方法：添加有向边

add_directed_edge 方法用于在两个顶点之间添加一条有向边。

该方法与 add_edge 类似，不同之处在于它只在起点 (start) 的邻接列表中添加终点 (end)，表示有一个方向的连接。

2. 图的遍历方法

图的遍历包括深度优先搜索 (DFS) 和广度优先搜索 (BFS)，它们用于访问图中的所有节点。

❏ `dfs` 方法：深度优先搜索

深度优先搜索 (DFS) 是一种遍历图的方法，先访问一个节点，然后再递归地访问它的所有相邻节点。

如果节点还没有被访问过，就将其标记为已访问 (visited 集合)，并递归调用 dfs 访问所有相邻节点。
这种遍历方式类似于树的前序遍历。

❏ `bfs` 方法：广度优先搜索

广度优先搜索 (BFS) 是另一种遍历图的方法，它按层次来访问图中的节点。

首先将起始节点添加到队列中，并将其标记为已访问。
依次从队列中取出节点，访问该节点的所有相邻节点，并将未访问过的节点加入队列中。
这种遍历方式类似于按层访问树的节点。

示例演示

下面通过一个简单的示例来展示如何使用这些方法创建图并进行遍历：

if __name__ == "__main__":
    graph = Graph()
    graph.add_vertex(1)
    graph.add_vertex(2)
    graph.add_edge(1, 2)
    graph.add_edge(1, 3)
    graph.add_directed_edge(2, 4)
    graph.add_directed_edge(3, 5)

    print("深度优先搜索 (DFS):")
    graph.dfs(1)  # 输出：1 2 4 3 5

    print("\n广度优先搜索 (BFS):")
    graph.bfs(1)  # 输出：1 2 3 4 5