Python实现图的深度优先搜索算法

深度优先搜索（Depth First Search, DFS）是一种用于遍历图的算法。该算法从图的某一个顶点开始，沿着一条路径一直深入进入，直到不能再深入为止，然后再返回该路径上的顶点，沿着另一条路径继续访问其他顶点，直到所有顶点都被访问过为止。

下面是用Python实现图的深度优先搜索算法的代码示例：

# 定义图的类
class Graph:
    def __init__(self, vertices):
        self.vertices = vertices
        self.adjacency_list = [[] for _ in range(vertices)]

    # 添加边
    def add_edge(self, u, v):
        self.adjacency_list[u].append(v)
        self.adjacency_list[v].append(u)

    # 深度优先搜索
    def dfs(self, start_vertex):
        visited = [False] * self.vertices  # 记录顶点是否被访问过的列表
        self.dfs_helper(start_vertex, visited)

    def dfs_helper(self, current_vertex, visited):
        visited[current_vertex] = True
        print(current_vertex, end=' ')

        for neighbor in self.adjacency_list[current_vertex]:
            if not visited[neighbor]:
                self.dfs_helper(neighbor, visited)

在上面的代码中，我们首先定义了一个Graph类，该类包含vertices属性来表示图的顶点数目，adjacency_list属性用于存储图的邻接表。然后我们实现了add_edge方法用于向图中添加边。最后实现了dfs方法和dfs_helper方法来完成深度优先搜索的递归遍历。

以下是一个使用示例：

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

print("DFS traversal starting from vertex 0:")
g.dfs(0)

输出结果为：

DFS traversal starting from vertex 0:
0 1 3 2 4

在上面的示例中，我们创建了一个包含5个顶点的图，并向图中添加了几条边。然后我们从顶点0开始进行深度优先搜索，并输出遍历的结果。

总结来说，Python实现图的深度优先搜索算法可以通过定义一个Graph类和递归的方式来实现。深度优先搜索的操作是通过递归访问每一个与当前顶点相邻的未被访问过的顶点，直到所有顶点都被访问过为止。