Algorithme en Python (recherche de priorité de largeur, bfs)

introduction

Je vais expliquer la mise en œuvre de la recherche de priorité de largeur en utilisant python. (Il suffit de mettre celui que je mets toujours en œuvre.) La recherche de priorité à la largeur soulève souvent le problème de la distance, nous allons donc cette fois implémenter une fonction qui renvoie la distance d'un sommet à chaque sommet.

Recherche de priorité de largeur

Je pense que beaucoup de connaissances générales sur la recherche de priorité de largeur sortiront si vous la recherchez, donc je vais l'omettre en détail, mais je vais l'expliquer brièvement. 　　　 Comme indiqué par la flèche bleue, suivez les sommets dans l'ordre du plus proche. Pour la distance à gérer cette fois, ajoutez 1 à la distance au sommet précédent. (Dans l'image, il est secoué à partir de 1, mais s'il s'agit d'une distance, il peut être secoué à partir de 0.) L'ordre de recherche de ce sommet est géré par la file d'attente. Une file d'attente est une structure de données premier entré, premier sorti. Dans cet exemple, le début 0 est entré en premier. ([0]) Ensuite, retirez le contenu de l'avant et examinez les sommets adjacents. (1 et 2 cette fois) Si vous visitez pour la première fois, ajoutez-le à la file d'attente. ([1, 2]) Si vous répétez ceci, vous pouvez examiner les sommets dans l'ordre des flèches bleues. （[2, 3, 4]→[3, 4, 5, 6]→[4, 5, 6, 7]...） La recherche se termine lorsque la file d'attente est vide. Vive le bon travail.

la mise en oeuvre

contribution

Étant donné le nombre de sommets n et le nombre de côtés m, alors les sommets adjacents sont donnés sur m lignes.

11 9
0 1
0 2
1 3
1 4
2 5
2 6
3 7
5 8
8 9

code

import sys
input = sys.stdin.readline

n, m = [int(x) for x in input().split()] #n est le nombre de sommets, m est le nombre de côtés
g = [[] for _ in range(n)] #Liste adjacente

for _ in range(m):
    a, b = [int(x) for x in input().split()]
    g[a].append(b)
    g[b].append(a)

from collections import deque

def bfs(u):
    queue = deque([u])
    d = [None] * n #Initialisation de la distance de u
    d[u] = 0 #La distance par rapport à moi-même est de 0
    while queue:
        v = queue.popleft()
        for i in g[v]:
            if d[i] is None:
                d[i] = d[v] + 1
                queue.append(i)
    return d

#Distance de chaque sommet de 0
d = bfs(0)
print(d)

production

Génère une liste avec la distance du sommet 0 dans l'ordre du nombre de vertex à partir de la gauche. La distance à vous-même est de 0 et les sommets que vous ne pouvez pas atteindre sont Aucun.

[0, 1, 1, 2, 2, 2, 2, 3, 3, 4, None]

en conclusion

S'il vous plaît laissez-moi savoir si vous avez des erreurs! Je vous serais reconnaissant si vous pouviez me donner quelques conseils!