图的深度遍历python

在图形的深度优先搜索中，我们访问每个顶点，从起点开始，尽可能深地探索图中的分支。我们沿着每个分支深入，直到我们到达最深处，然后回溯并访问其他分支。

在 Python 中，可以使用递归函数来实现图形的深度优先搜索。我们需要使用一个栈来保存当前遍历的所有顶点，并使用一个布尔数组来记录哪些顶点已经被访问过。

下面是一个简单的例子，展示了如何使用递归函数实现图形的深度优先搜索：

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

# 定义深度优先搜索函数
def dfs(graph, start, visited):
  # 将起点添加到已访问的顶点列表中
  visited.add(start)
  # 获取起点的所有邻接顶点
  for neighbor in graph[start]:
    # 如果邻接顶点没有被访问过，则递归调用深度优先搜索函数
    if neighbor not in visited:
      dfs(graph, neighbor, visited)

# 从 'A' 顶点开始深度优先搜索
visited = set()
dfs(graph, 'A', visited)
print(vis

相关问题

图的深度优先遍历python

以下是Python中图的深度优先遍历的实现方法：

# 定义一个图类
class Graph:
    def __init__(self, graph_dict=None):
        if graph_dict is None:
            graph_dict = {}
        self.__graph_dict = graph_dict

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

    # 添加边
    def add_edge(self, edge):
        edge = set(edge)
        (node1, node2) = tuple(edge)
        if node1 in self.__graph_dict:
            self.__graph_dict[node1].append(node2)
        else:
            self.__graph_dict[node1] = [node2]

    # 深度优先遍历
    def dfs(self, start, visited=None):
        if visited is None:
            visited = set()
        visited.add(start)
        print(start)
        for next_node in self.__graph_dict[start]:
            if next_node not in visited:
                self.dfs(next_node, visited)

# 创建一个图实例
graph = Graph()

# 添加节点
graph.add_node('A')
graph.add_node('B')
graph.add_node('C')
graph.add_node('D')
graph.add_node('E')

# 添加边
graph.add_edge(('A', 'B'))
graph.add_edge(('B', 'C'))
graph.add_edge(('C', 'D'))
graph.add_edge(('D', 'E'))
graph.add_edge(('E', 'A'))

# 深度优先遍历
graph.dfs('A')

输出结果为：

A
B
C
D
E

树的深度优先遍历python

以下是树的深度优先遍历的Python代码示例：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def dfs(self, node: TreeNode, depth: int) -> int:
        if not node:
            return depth
        left_depth = self.dfs.left, depth + 1)
        right_depth = self.dfs(node.right, depth + 1)
        return max(left_depth, right_depth)
    
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        return self.dfs(root, 0)

其中，`TreeNode`类表示树的节点，`Solution`类中的`dfs`方法是递归实现的深度优先遍历，`maxDepth`方法是调用`dfs`方法并返回最大深度。