Scène où la recherche de priorité de largeur (BFS) est requise (préface)

J'ai rencontré un problème pour trouver la distance la plus courte entre deux points dans un graphique de structure arborescente avec Atcoder. À ce moment-là, j'ai créé l'algorithme moi-même, mais je ne pouvais pas résoudre le problème, j'ai donc décidé de créer correctement BFS. Lors de son utilisation, j'utiliserai une bibliothèque pratique Cette fois, je vais programmer et organiser l'idée de base. La réimplémentation à l'aide de la bibliothèque sera effectuée à une date ultérieure.

Jusqu'à la dernière fois, j'ai créé une classe d'arborescence et un programme de dessin. Créez votre propre classe de structure de graphique et son dessin avec python
Les articles suivants sur BFS ont été résumés en détail, je les ai donc utilisés comme référence. [BFS (Width Priority Search) Super Introduction! ~ Utilisez le cue vivement ~] (https://qiita.com/drken/items/996d80bcae64649a6580)

la mise en oeuvre

Puisque l'introduction est bonne, implémentez-la ci-dessous.

Définition de la classe de structure graphique

#Créer une structure graphique
class cglaph():
  def __init__(self):
    #Initialisation du nœud
    self.nodes={}

  def addnode(self,num):#① Ajouter un nœud
    for i in self.nodes.keys():
      if i==num:
        return(False)
    else:
      self.nodes[num]=list()
      return(True)

  def addedge(self,ag1,ag2):#② Ajouter un bord
    node1=min(ag1,ag2)
    node2=max(ag1,ag2)
    addok=False

    for i in self.nodes.keys():
      if i==node1:
        for j in self.nodes.keys():
          if j==node2:
            addok=True

    if addok:
      self.nodes[node1].append(node2)
      self.nodes[node2].append(node1)

  def printnodes(self):    #③ Afficher le nœud
    print("■Glaph:")
    print("vertice:neighbors")
    for k,v in self.nodes.items():
      print(k,":",v)


  def getnodes(self):#④ Renvoie une liste de nœuds
    keylist=list()

    for i in self.nodes.keys():
      keylist.append(i)
    return keylist

  def getedge(self, node):#⑤ Renvoie l'arête (nœud connecté) du nœud spécifié.
    return self.nodes[node]

Concept de cette classe de structure arborescente

Les informations de nœud sont stockées dans un type de dictionnaire. Stockez le numéro de nœud dans la clé et les nœuds connectés à ce nœud dans une liste dans la valeur. Insérez la méthode suivante. ① Ajouter un nœud ② Ajouter un bord ③ Affichage des nœuds (et des nœuds qui leur sont connectés) ④ Renvoie une liste de nœuds ⑤ Renvoie une liste de nœuds connectés au nœud spécifié

Définition de classe de structure de file d'attente

#Définition de la structure de la file d'attente
class cqu():
  def __init__(self):
    #Initialisation de la file d'attente
    self.qu=list()
    self.head=0
    self.tail=-1

  def quval(self):#① Taille de la queue
    return self.tail-self.head+1

  def printqu(self):#② Afficher le contenu de la file d'attente
    print(str(self.qu[self.head:self.tail+1])+",head:"+str(self.head)+",tail:"+str(self.tail))
    print(self.qu)

  def enqu(self,num):#③ Encu
    self.qu.append(num)
    self.tail+=1
 
  def dequ(self):#④ Decue
    if self.quval()!=0:
      outv=self.qu[self.head]
      self.head+=1
      return outv

    else:
      return False

Concept de classe de structure de file d'attente

La file d'attente a une structure de liste et des variables telles que des pointeurs indiquant le début et la fin. Ayez la méthode suivante. ① Renvoie la taille de la file d'attente ② Afficher le contenu de la file d'attente ③ Encu ④ Decue

Créer une arborescence

G=cglaph()

G.addnode(1)#Ajouter un nœud
G.addnode(2)
G.addnode(3)
G.addnode(4)
G.addnode(5)
G.addedge(1,2)#Ajouter un bord
G.addedge(2,3)
G.addedge(3,4)
G.addedge(4,5)
G.addedge(2,4)
G.printnodes()#Liste des nœuds

nodelist=G.getnodes()#Obtenir la liste des nœuds
print ("NODE LIST:",nodelist)

G.getedge(1)#Nœud connecté au nœud 1

L'image est le graphique ci-dessous

Les coordonnées du nœud lors du dessin du graphique sont Utiliser la distance du nœud de démarrage de la recherche dans BFS est un peu mieux, donc je vais le dessiner en dernier.

Implémentation BFS


StartNode=1

#Graphique cible G
G.printnodes()

#Liste pour enregistrer la distance
NodeList=G.getnodes()
#print(NodeList)
DistList=[0]*len(NodeList)

#Génération de structure de file d'attente
Q=cqu()

#① Mettre en file d'attente le nœud de démarrage de la recherche
Q.enqu(StartNode)
#Q.printqu()

while Q.quval():#② Boucle jusqu'à ce que la taille de la file d'attente devienne 0
  #print("=====loop=====")
  #Q.printqu()
  #print("Qval"+str(Q.quval()))

  checknode=Q.dequ()#③ Decue
  #print("deQ:"+str(checknode))

  nextnodes=G.getedge(checknode)#④ Acquérir le nœud connecté au nœud acquis par mise en file d'attente
  #print("next nodes:"+str(nextnodes))

  for i in nextnodes:#⑤ Donnez la distance à chaque nœud connecté
    #print(i)
    if DistList[NodeList.index(i)]==0:#⑥ Jugez s'il a été fouillé (la distance a été donnée au nœud)
      if i!=StartNode:#⑦ Le nœud de démarrage de la recherche est hors de portée
        #print("enq")
        Q.enqu(i)#⑧ Mettre en file d'attente, donner la distance si elle n'est pas recherchée (la faire rechercher)
        DistList[NodeList.index(i)]=DistList[NodeList.index(checknode)]+1#⑨ Recherche Augmentez la distance du nœud d'origine de +1
    
    #print(DistList)

print("Liste des distances",DistList)

S'il s'agit d'une implémentation simple, il y en a beaucoup sur d'autres sites, j'ai donc laissé un commentaire pour le débogage que je crée.

L'algorithme consiste à retirer la file d'attente et à déterminer le nœud de départ. Mettez en file d'attente le nœud connecté au nœud de départ. répéter.

Dessiner des graphiques et des résultats de recherche

import matplotlib.pyplot as plt
import collections
import copy

#Dessiner un graphique en fonction de la distance de recherche
N=len(nodelist)
x=DistList#la coordonnée x est la distance
y=[0]*N#Pour la coordonnée Y, les nœuds avec la même coordonnée X sont disposés à intervalles égaux (les intervalles égaux sont calculés ci-dessous).===
c=collections.Counter(DistList)#Trouvez le nombre d'éléments qui se chevauchent.
tmp=c.most_common()

c2=collections.Counter(DistList)#Compteur de correction


tmpmean=copy.deepcopy(tmp)
for i in range(len(tmp)):
  tmpmean[i]=(c[i]-1)*0.5+1


for i,n in zip(DistList,range(N)):
  if c[i]!=1:#1 est y=0 ligne
    y[n]=-c2[i]+tmpmean[i]
    c2[i]-=1
#===Jusqu'à présent x,Je veux juste trouver la coordonnée y

print("x:",x)
print("y:",y)

#Création de graphes
plt.figure(1)

#Dessin de nœud
plt.scatter(x,y)

#Donnez un nom de nœud à la position du nœud
ax=plt.axes()
for i in range(N):
  ax.annotate(str(nodelist[i])+":"+str(DistList[i]),(x[i],y[i]),size=20)

#Dessiner des bords
for i in nodelist:
  edges=G.getedge(i)
  for j in edges:
    plt.plot((x[nodelist.index(i)],x[nodelist.index(j)]),(y[nodelist.index(i)],y[nodelist.index(j)]), color='red')


plt.xlim(-1, 5)
plt.ylim(-3, 3)

L'annotation attachée à chaque nœud est (numéro de nœud: distance du nœud de début de recherche).

Résumé, futurs numéros

-BFS lui-même peut être facilement implémenté en utilisant une structure de file d'attente. ・ Nous résumerons la mise en œuvre à l'aide de la bibliothèque en prévision de la pratique. -Si plusieurs nœuds avec la même distance (même hiérarchie) se succèdent, le graphique sera tordu. Examinez l'algorithme de dessin de graphique.