Comment écrire un algorithme de recherche en profondeur en Python ?

Comment écrire un algorithme de recherche en profondeur en Python ?

Depth-First Search (DFS) est un algorithme de traversée de graphiques couramment utilisé. Dans la recherche en profondeur d'abord, en commençant par le nœud de départ, les nœuds adjacents sont explorés en continu jusqu'à ce qu'aucune autre exploration ne soit possible, puis il revient au nœud précédent et continue de traverser les nœuds adjacents inexplorés jusqu'à ce que tous les nœuds soient visités.

Ce qui suit est un exemple d'algorithme de recherche en profondeur écrit en 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)

Le code ci-dessus implémente une classe Graph pour représenter la structure du graphe, qui contient le nombre initial de nœuds et la définition des nœuds adjacents. Ensuite, la fonction pour ajouter un bord add_edge est définie. add_edge。

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

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

L'algorithme DFS est exécuté à l'aide de la fonction récursive dfs_util La fonction accepte deux paramètres : le nœud actuel u et un tableau visité. pour Marquer si le nœud a été visité. L'algorithme marque d'abord le nœud actuel comme visité et génère la valeur du nœud. Parcourez ensuite tous les nœuds adjacents du nœud actuel. Si les nœuds adjacents n'ont pas encore été visités, appelez la fonction dfs_util de manière récursive.

Enfin, la fonction dfs sert d'interface externe, accepte le nœud de départ comme paramètre et crée un tableau visité initialisé à False. Appelez la fonction dfs_util pour démarrer la traversée DFS.

Dans le code de test, nous avons créé un graphe avec 4 nœuds et ajouté quelques arêtes. Utilisez ensuite le nœud de départ 2 pour effectuer le parcours DFS et afficher les résultats. 🎜🎜J'espère que cet exemple de code vous aidera à comprendre comment écrire un algorithme de recherche en profondeur en Python. Vous pouvez également modifier et optimiser le code selon vos propres besoins. 🎜

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!