深度优先搜索python

深度优先搜索（Depth First Search，DFS）是一种用于遍历或搜索树或图的算法。它从根节点开始，沿着每个分支尽可能深入，直到达到叶子节点或无法继续为止。然后回溯到上一个分支，继续探索其他分支。

以下是一个用Python实现深度优先搜索的示例代码：

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start, end=' ')

    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

# 测试代码
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

dfs(graph, 'A')

输出结果为：A B D E F C

相关问题

深度优先搜索 python

深度优先搜索（Depth First Search, DFS）是一种用于遍历或搜索树或图的算法。在Python中，可以使用递归或栈来实现深度优先搜索。

以下是一个使用递归实现深度优先搜索的示例代码：

def dfs(graph, node, visited):
    if node not in visited:
        print(node)
        visited.add(node)
        neighbors = graph[node]
        for neighbor in neighbors:
            dfs(graph, neighbor, visited)

# 示例图的邻接表表示
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

visited = set()
dfs(graph, 'A', visited)

这段代码会按照深度优先的顺序遍历并打印图中的节点。其中，`graph` 是图的邻接表表示，`node` 是当前节点，`visited` 是已经访问过的节点集合。在每次递归调用时，我们检查当前节点是否已经被访问过，如果没有，则将其加入到已访问集合中，并递归地对其未访问的邻居节点进行深度优先搜索。

希望这个示例对你有帮助！如果你还有其他问题，请随时提问。

深度优先搜索Python实现

深度优先搜索（Depth-First Search，DFS）是一种常用的图遍历算法，它通过递归的方式从起始节点开始，沿着一条路径尽可能深入地搜索，直到无法继续为止，然后回溯到上一个节点，继续搜索其他路径。下面是深度优先搜索的Python实现：

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

    # 添加边
    def add_edge(self, u, v):
        if u in self.graph:
            self.graph[u].append(v)
        else:
            self.graph[u] = [v]

    # 深度优先搜索
    def dfs(self, start):
        visited = set()  # 记录已访问的节点
        self._dfs(start, visited)

    def _dfs(self, node, visited):
        visited.add(node)
        print(node, end=" ")  # 输出当前节点
        neighbors = self.graph.get(node, [])
        for neighbor in neighbors:
            if neighbor not in visited:
                self._dfs(neighbor, visited)

# 创建图对象
g = Graph()

# 添加边
g.add_edge(1, 2)
g.add_edge(1, 3)
g.add_edge(2, 4)
g.add_edge(2, 5)
g.add_edge(3, 6)
g.add_edge(3, 7)

# 从节点1开始进行深度优先搜索
print("深度优先搜索结果：")
g.dfs(1)

以上代码中，首先定义了一个`Graph`类来表示图，其中`add_edge`方法用于添加边，`dfs`方法用于进行深度优先搜索。在`_dfs`方法中，使用递归的方式进行深度优先搜索，并通过一个`visited`集合来记录已访问的节点，避免重复访问。