python深度优先搜索

Python中的深度优先搜索（DFS）是一种用于遍历或搜索图或树的算法。它使用递归的方式来依次访问节点，从一个节点开始，沿着一条路径访问其邻居节点，直到到达一个没有未访问过的邻居的节点时，回溯到上一个节点，继续从下一个邻居节点访问，直到遍历完整个图或树。

下面是一个使用递归实现深度优先搜索的例子：

def dfs(graph, node, visited):
    visited.add(node)
    print(node)

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

其中，graph是一个表示图或树的邻接表，node是当前访问的节点，visited是一个集合，用于存储已经访问过的节点。在每次访问节点时，将其加入visited集合，并打印它的值。然后，遍历该节点的邻居节点，如果邻居节点未访问过，则递归调用dfs函数。

注意，这个算法的时间复杂度是O(V+E)，其中V表示节点数，E表示边数。因为每个节点和每条边最多只会被访问一次。

相关问题

python 深度优先搜索

Python 中可以使用递归实现深度优先搜索（DFS），也可以使用栈来实现。下面是一个使用递归实现 DFS 的示例：

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start)
    for next in graph[start] - visited:
        dfs(graph, next, visited)
    return visited

其中，graph 是一个字典，key 表示节点，value 表示与该节点相邻的节点集合。start 表示起始节点，visited 是一个记录已访问过的节点的集合。在每次访问一个节点时，都将该节点加入 visited 集合，并输出该节点。然后递归访问与该节点相邻且未访问过的节点。最后返回 visited 集合，表示遍历过的所有节点。

使用示例：

graph = {'A': set(['B', 'C']),
         'B': set(['A', 'D', 'E']),
         'C': set(['A', 'F']),
         'D': set(['B']),
         'E': set(['B', 'F']),
         'F': set(['C', 'E'])}

dfs(graph, 'A')

输出：

A
B
D
E
F
C

这是一个简单的深度优先搜索示例，实际应用中需要根据具体情况进行相应的调整。

python深度优先搜索算法

以下是Python中深度优先搜索算法的示例：

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

    # 添加边
    def add_edge(self, node, neighbor):
        if node not in self.graph:
            self.graph[node] = []
        self.graph[node].append(neighbor)

    # 深度优先搜索函数
    def dfs(self, start, visited=None):
        if visited is None:
            visited = set()
        visited.add(start)
        print(start, end=' ')
        for next in self.graph[start] - visited:
            self.dfs(next, visited)
        return visited

# 创建图实例
g = Graph()
# 添加边
g.add_edge('A', 'B')
g.add_edge('A', 'C')
g.add_edge('B', 'D')
g.add_edge('B', 'E')
g.add_edge('C', 'F')
# 执行深度优先搜索
print("深度优先搜索结果:")
g.dfs('A')

这段代码创建了一个图的类，然后添加了一些边，并执行了深度优先搜索算法。在这个示例中，我们从节点'A'开始进行深度优先搜索，输出结果为'A B D E C F'。