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

深度优先搜索(DFS，Depth First Search)是一种用于遍历或搜索图的算法。它通过从起点开始，沿着一条路径一直深入到不能再深入为止，然后回溯到前一个节点，继续探索其他路径，直到遍历完所有节点为止。

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

# 定义图的类
class Graph:
   def __init__(self):
       self.graph = dict()

    # 添加节点
   def add_node(self, node):
       if node not in self.graph:
           self.graph[node] = []

    # 添加边
   def add_edge(self, node1, node2):
       if node1 in self.graph and node2 in self.graph:
           self.graph[node1].append(node2)
           self.graph[node2].append(node1)
       else:
           print("节点不存在")

    # 深度优先搜索算法
   def dfs(self, start_node):
       visited = set()  # 用集合来保存已经访问过的节点
       self.dfs_helper(start_node, visited)

   def dfs_helper(self, node, visited):
       visited.add(node)
       print(node, end=" ")

       for neighbor in self.graph[node]:
           if neighbor not in visited:
               self.dfs_helper(neighbor, visited)

# 创建一个示例图
g = Graph()
g.add_node('A')
g.add_node('B')
g.add_node('C')
g.add_node('D')
g.add_node('E')
g.add_node('F')

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

# 输出深度优先搜索的结果
print("从节点A开始的深度优先搜索结果:")
g.dfs('A')

这段代码首先定义了一个名为Graph的类，表示图。其中add_node方法用于添加节点，add_edge方法用于添加边。dfs方法是深度优先搜索的入口，它首先创建一个空集合visited来保存已经访问过的节点，然后调用dfs_helper方法递归地进行深度优先搜索。

在dfs_helper方法中，首先将当前节点加入visited集合，并将其打印出来。然后遍历该节点的邻居节点，如果邻居节点没有被访问过，则继续调用dfs_helper方法进行深度优先搜索。

最后，创建一个示例图，并从节点A开始进行深度优先搜索，输出搜索结果。

执行上述代码，输出结果为:

从节点A开始的深度优先搜索结果:
A B C D E F 

这表示深度优先搜索按照顺序访问了节点A、B、C、D、E、F。

深度优先搜索算法的时间复杂度是O(V + E)，其中V是节点的数量，E是边的数量。