python 深度优先搜索算法

深度优先搜索（Depth-First Search，DFS）是一种用于遍历或搜索树或图的算法。它从根节点开始，沿着深度遍历树的分支，直到找到目标节点或到达叶子节点为止。如果遇到叶子节点仍未找到目标节点，则回溯到上一个节点，继续遍历其他分支。

下面是一个使用递归实现的基本的深度优先搜索算法（对于图而言，需要额外考虑访问过的节点）：

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

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

其中，`graph` 是图的邻接表表示，`start` 是起始节点，`visited` 是已访问过的节点集合。

相关问题

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'。

python深度优先搜索算法代码

深度优先搜索算法的Python代码如下所示：

class Node:
    def __init__(self, value=None, connect=[]):
        self.value = value
        self.connect = connect

    def setValue(self, value):
        self.value = value

    def getValue(self):
        return self.value

    def setConnect(self, connect):
        self.connect = connect

    def getConnect(self):
        return self.connect

    def addConnect(self, node):
        self.connect.append(node)

def dfs(node=None):
    if node is None:
        return
    nodeSet = set()
    stack = []
    print(node.getValue())
    nodeSet.add(node)
    stack.append(node)
    while len(stack) > 0:
        cur = stack.pop()
        for next in cur.getConnect():
            if next not in nodeSet:
                print(next.getValue())
                nodeSet.add(next)
                stack.append(cur)
                stack.append(next)
                break