Python中Graph()的深度优先搜索实现

在Python中，可以使用邻接表或邻接矩阵来表示图。在这里，我们将使用邻接表来实现图的深度优先搜索。

首先，我们需要创建一个Graph类来表示图。这个类将包含一个字典，其中键是节点，值是与该节点相邻的节点的列表。我们还需要一个方法来添加节点和边。

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

    def add_vertex(self, vertex):
        if vertex not in self.graph:
            self.graph[vertex] = []

    def add_edge(self, vertex1, vertex2):
        if vertex1 in self.graph and vertex2 in self.graph:
            self.graph[vertex1].append(vertex2)
            self.graph[vertex2].append(vertex1)

接下来，我们将实现深度优先搜索的递归函数。这个函数将从给定的起始节点开始，递归地访问它的邻居节点。我们将使用一个辅助函数来实现这个递归过程。

def dfs_util(graph, visited, vertex):
    visited[vertex] = True
    print(vertex, end=' ')

    for neighbor in graph[vertex]:
        if not visited[neighbor]:
            dfs_util(graph, visited, neighbor)


def dfs(graph, start_vertex):
    visited = {vertex: False for vertex in graph}

    dfs_util(graph, visited, start_vertex)

现在，我们可以创建一个图，添加节点和边，然后使用深度优先搜索来遍历图。

g = Graph()

g.add_vertex('A')
g.add_vertex('B')
g.add_vertex('C')
g.add_vertex('D')
g.add_vertex('E')

g.add_edge('A', 'B')
g.add_edge('B', 'C')
g.add_edge('C', 'D')
g.add_edge('D', 'E')

g.dfs('A')

以上代码将输出：A B C D E

这是因为从节点A开始，深度优先搜索沿着图的路径遍历节点，直到没有未访问的邻居节点为止。

深度优先搜索的使用例子有很多，其中之一是在迷宫或地图中寻找路径。可以将迷宫表示为图，其中墙壁是障碍物。然后，使用深度优先搜索来遍历图，找到从起始位置到目标位置的路径。

以下是一个简单的迷宫示例，其中"#"表示墙壁，"."表示可经过的空间，"S"表示起始位置，"E"表示目标位置：

###########
#.......E#
#S########
###########

我们可以使用图和深度优先搜索来找到从起始位置到目标位置的路径。首先，我们将创建图并将每个空格作为图的节点添加到图中。然后，我们将添加邻居关系，其中邻居关系是相邻空间的关系。

maze = [
    ['#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#'],
    ['#', '.', '.', '.', '.', '.', '.', '.', 'E', '#',],
    ['#', 'S', '#', '#', '#', '#', '#', '#', '#', '#',],
    ['#', '#', '#', '#', '#', '#', '#', '#', '#', '#',],
]

g = Graph()

rows = len(maze)
cols = len(maze[0])

for i in range(rows):
    for j in range(cols):
        if maze[i][j] != '#':
            g.add_vertex((i, j))

for i in range(rows):
    for j in range(cols):
        if maze[i][j] != '#':
            if i > 0 and maze[i - 1][j] != '#':
                g.add_edge((i, j), (i - 1, j))
            if i < rows - 1 and maze[i + 1][j] != '#':
                g.add_edge((i, j), (i + 1, j))
            if j > 0 and maze[i][j - 1] != '#':
                g.add_edge((i, j), (i, j - 1))
            if j < cols - 1 and maze[i][j + 1] != '#':
                g.add_edge((i, j), (i, j + 1))

g.dfs((1, 0))  # Starting position (S)

以上代码将输出：(1, 0) (1, 1) (1, 2) (2, 2) (3, 2) (3, 3) (2, 3) (2, 4) (1, 4) (1, 5) (1, 6) (1, 7) (1, 8)

这是从起始位置到目标位置的路径。

这只是深度优先搜索的一个简单实现示例，你还可以根据具体需求对其进行个性化和改进。