Python에서 깊이 우선 검색 알고리즘을 작성하는 방법은 무엇입니까?

Python에서 깊이 우선 검색 알고리즘을 작성하는 방법은 무엇입니까?

DFS(깊이 우선 검색)는 일반적으로 사용되는 그래프 순회 알고리즘입니다. 깊이 우선 탐색에서는 시작 노드부터 시작하여 더 이상 탐색이 불가능할 때까지 인접 노드를 계속 탐색한 다음 이전 노드로 돌아가 모든 노드를 방문할 때까지 탐색되지 않은 인접 노드를 계속 탐색합니다.

다음은 Python으로 작성된 깊이 우선 검색 알고리즘의 예입니다.

# 定义图的类
class Graph:
    def __init__(self, vertices):
        self.V = vertices  # 节点数量
        self.adj = [[] for _ in range(self.V)]  # 存储节点的邻接节点
        
    # 添加边
    def add_edge(self, u, v):
        self.adj[u].append(v)
        
    # DFS递归函数
    def dfs_util(self, u, visited):
        visited[u] = True  # 标记当前节点为已访问
        
        print(u, end=' ')  # 输出当前节点
        
        # 遍历当前节点的所有邻接节点
        for i in self.adj[u]:
            if not visited[i]:
                self.dfs_util(i, visited)
            
    # 对外接口，执行DFS
    def dfs(self, u):
        visited = [False] * self.V  # 标记所有节点均未访问
        
        self.dfs_util(u, visited)
        

# 测试代码
if __name__ == '__main__':
    # 创建一个具有4个节点的图
    g = Graph(4)
    
    # 添加图的边
    g.add_edge(0, 1)
    g.add_edge(0, 2)
    g.add_edge(1, 2)
    g.add_edge(2, 0)
    g.add_edge(2, 3)
    g.add_edge(3, 3)
    
    print("深度优先遍历结果：")
    g.dfs(2)

위 코드는 Graph 클래스를 구현하여 초기 노드 수와 인접 노드 정의를 포함하는 그래프의 구조를 나타냅니다. 그런 다음 가장자리 add_edge를 추가하는 함수가 정의됩니다. add_edge。

DFS算法在dfs_util递归函数的辅助下进行，函数接受两个参数：当前节点u和一个数组visited，用于标记节点是否已经访问。算法首先将当前节点标记为已访问，并输出该节点的值。然后遍历当前节点的所有邻接节点，如果邻接节点尚未被访问，则递归调用dfs_util函数。

最后，dfs函数作为对外接口，接受起始节点作为参数，并创建一个visited数组初始化为False。调用dfs_util

DFS 알고리즘은 dfs_util 재귀 함수의 도움으로 수행됩니다. 이 함수는 현재 노드 u와 방문한 배열이라는 두 가지 매개변수를 허용합니다. 노드를 방문했는지 여부를 표시합니다. 알고리즘은 먼저 현재 노드를 방문한 것으로 표시하고 노드의 값을 출력합니다. 그런 다음 현재 노드의 모든 인접 노드를 탐색합니다. 인접 노드를 아직 방문하지 않은 경우 dfs_util 함수를 재귀적으로 호출합니다.

마지막으로 dfs 함수는 외부 인터페이스 역할을 하고 시작 노드를 매개변수로 받아들이고 False로 초기화된 visited 배열을 생성합니다. DFS 탐색을 시작하려면 dfs_util 함수를 호출하세요.

테스트 코드에서는 4개의 노드가 있는 그래프를 만들고 일부 간선을 추가했습니다. 그런 다음 시작 노드 2를 사용하여 DFS 순회를 수행하고 결과를 출력합니다. 🎜🎜이 코드 예제가 Python에서 깊이 우선 검색 알고리즘을 작성하는 방법을 이해하는 데 도움이 되기를 바랍니다. 필요에 따라 코드를 수정하고 최적화할 수도 있습니다. 🎜

위 내용은 Python에서 깊이 우선 검색 알고리즘을 작성하는 방법은 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!