Comment implémenter un algorithme de recherche en largeur à l'aide de Python ?

Comment implémenter un algorithme de recherche en largeur à l'aide de Python ?

Breadth-First Search (BFS) est un algorithme de recherche de graphiques de base utilisé pour trouver le chemin le plus court vers un nœud (ou un état) spécifique dans un graphique ou un arbre. Il peut être largement utilisé dans de nombreux domaines, comme trouver la chaîne de relations amicales la plus courte sur les réseaux sociaux, résoudre des problèmes de labyrinthe, etc. Python fournit des structures de données et des bibliothèques de fonctions puissantes, ce qui rend la mise en œuvre de BFS une tâche relativement simple. Cet article explique comment utiliser Python pour implémenter l'algorithme BFS et fournit des exemples de code spécifiques.

Tout d'abord, nous devons définir une structure de données graphique. Les graphiques peuvent être représentés à l'aide de listes de contiguïté ou de matrices de contiguïté. Dans cet article, nous représenterons des graphiques à l'aide de listes de contiguïté. Voici la définition de la structure de données du graphe :

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.adj = [[] for _ in range(vertices)]
    
    def add_edge(self, src, dest):
        self.adj[src].append(dest)

Le code ci-dessus définit une classe Graph, qui contient un constructeur et deux méthodes : add_edge()用于添加边，__init__() est utilisé pour initialiser la classe.

Ensuite, nous pouvons implémenter l'algorithme BFS. L'idée de base de l'algorithme BFS est de partir d'un nœud de départ donné et de parcourir les nœuds du graphique couche par couche jusqu'à ce que le nœud cible soit trouvé. Pendant le processus de parcours, une file d'attente est utilisée pour stocker les nœuds à visiter. Voici le code pour implémenter l'algorithme BFS à l'aide de Python :

from collections import deque

def BFS(graph, start, goal):
    visited = [False] * graph.V
    queue = deque()

    queue.append(start)
    visited[start] = True

    while queue:
        node = queue.popleft()
        print(node, end=" ")

        if node == goal:
            print("目标节点已找到")
            break

        for i in graph.adj[node]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

    if not queue:
        print("目标节点未找到")

Le code ci-dessus définit une fonction appelée BFS. Cette fonction accepte trois paramètres : le graphique de l'objet graphique, le début du nœud de départ et l'objectif du nœud cible. L'algorithme utilise une liste visitée pour enregistrer les nœuds visités et une file d'attente pour stocker les nœuds à visiter. Dans chaque boucle, le premier élément de la file d'attente est supprimé, le nœud est visité et ses nœuds voisins non visités sont ajoutés à la file d'attente. Bouclez jusqu'à ce que le nœud cible soit trouvé ou que la file d'attente soit vide.

Enfin, nous pouvons utiliser le graphe défini ci-dessus et l'algorithme BFS pour une application pratique. Voici un exemple :

g = Graph(6)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 3)
g.add_edge(1, 4)
g.add_edge(2, 4)
g.add_edge(3, 4)
g.add_edge(3, 5)
g.add_edge(4, 5)

print("BFS遍历结果为：")
BFS(g, 0, 5)

Le code ci-dessus crée d'abord un objet graphique g contenant 6 nœuds, et ajoute plusieurs arêtes. Appelez ensuite la fonction BFS pour rechercher le chemin du nœud 0 au nœud 5. Le programme affichera les résultats du parcours BFS.

En résumé, cet article présente comment utiliser Python pour implémenter l'algorithme de recherche en largeur et fournit des exemples de code spécifiques. Grâce à la puissante structure de données et à la bibliothèque de fonctions de Python, nous pouvons facilement implémenter l'algorithme BFS et l'appliquer à divers scénarios pratiques.

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!