Szenen, in denen die Suche nach Breitenpriorität (BFS) erforderlich ist (Vorwort)

Ich habe mit Atcoder ein Problem beim Finden des kürzesten Abstands zwischen zwei Punkten in einem Baumstrukturdiagramm festgestellt. Zu diesem Zeitpunkt habe ich den Algorithmus selbst erstellt, konnte das Problem jedoch nicht lösen. Daher habe ich beschlossen, BFS ordnungsgemäß zu erstellen. Wenn ich es tatsächlich benutze, werde ich eine praktische Bibliothek verwenden Dieses Mal werde ich die Grundidee programmieren und organisieren. Die Neuimplementierung mithilfe der Bibliothek erfolgt zu einem späteren Zeitpunkt.

Bis zum letzten Mal habe ich eine Baumstrukturklasse und ein Zeichenprogramm erstellt. Erstellen Sie Ihre eigene Diagrammstrukturklasse und ihre Zeichnung mit Python
Die folgenden Artikel über BFS wurden ausführlich zusammengefasst, daher habe ich sie als Referenz verwendet. [BFS (Width Priority Search) Super Einführung! ~ Benutze das Stichwort lebhaft ~] (https://qiita.com/drken/items/996d80bcae64649a6580)

Implementierung

Da die Einführung gut ist, implementieren Sie sie unten.

Definition der Diagrammstrukturklasse

#Erstellen einer Diagrammstruktur
class cglaph():
  def __init__(self):
    #Knoteninitialisierung
    self.nodes={}

  def addnode(self,num):#① Fügen Sie einen Knoten hinzu
    for i in self.nodes.keys():
      if i==num:
        return(False)
    else:
      self.nodes[num]=list()
      return(True)

  def addedge(self,ag1,ag2):#② Fügen Sie eine Kante hinzu
    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):    #③ Zeigen Sie den Knoten an
    print("■Glaph:")
    print("vertice:neighbors")
    for k,v in self.nodes.items():
      print(k,":",v)


  def getnodes(self):#④ Gibt eine Liste der Knoten zurück
    keylist=list()

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

  def getedge(self, node):#⑤ Gibt die Kante (verbundener Knoten) des angegebenen Knotens zurück.
    return self.nodes[node]

Konzept dieser Baumstrukturklasse

Knoteninformationen werden in einem Wörterbuchtyp gespeichert. Speichern Sie die Knotennummer im Schlüssel und die mit diesem Knoten verbundenen Knoten in einer Werteliste. Fügen Sie die folgende Methode ein. ① Knoten hinzufügen ② Kante hinzufügen ③ Anzeige von Knoten (und mit ihnen verbundenen Knoten) ④ Gibt eine Liste der Knoten zurück ⑤ Gibt eine Liste der Knoten zurück, die mit dem angegebenen Knoten verbunden sind

Definition der Warteschlangenstrukturklasse

#Definition der Warteschlangenstruktur
class cqu():
  def __init__(self):
    #Warteschlangeninitialisierung
    self.qu=list()
    self.head=0
    self.tail=-1

  def quval(self):#① Cue-Größe
    return self.tail-self.head+1

  def printqu(self):#② Zeigen Sie den Inhalt der Warteschlange an
    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):#④ Entscheidung
    if self.quval()!=0:
      outv=self.qu[self.head]
      self.head+=1
      return outv

    else:
      return False

Konzept der Warteschlangenstrukturklasse

Die Warteschlange hat eine Listenstruktur und Variablen wie Zeiger, die den Anfang und das Ende angeben. Haben Sie die folgende Methode. ① Geben Sie die Größe der Warteschlange zurück ② Zeigen Sie den Inhalt der Warteschlange an ③ Encu ④ Entscheidung

Erstellen einer Baumstruktur

G=cglaph()

G.addnode(1)#Knoten hinzufügen
G.addnode(2)
G.addnode(3)
G.addnode(4)
G.addnode(5)
G.addedge(1,2)#Kante hinzufügen
G.addedge(2,3)
G.addedge(3,4)
G.addedge(4,5)
G.addedge(2,4)
G.printnodes()#Liste der Knoten

nodelist=G.getnodes()#Knotenliste abrufen
print ("NODE LIST:",nodelist)

G.getedge(1)#Knoten mit Knoten 1 verbunden

Das Bild ist die Grafik unten

Die Koordinaten des Knotens beim Zeichnen des Diagramms sind Die Verwendung des Abstands vom Suchstartknoten in BFS ist etwas besser, daher werde ich ihn zuletzt zeichnen.

BFS-Implementierung


StartNode=1

#Zieldiagramm G.
G.printnodes()

#Liste zum Aufzeichnen der Entfernung
NodeList=G.getnodes()
#print(NodeList)
DistList=[0]*len(NodeList)

#Generierung der Warteschlangenstruktur
Q=cqu()

#① Den Suchstartknoten in die Warteschlange stellen
Q.enqu(StartNode)
#Q.printqu()

while Q.quval():#② Schleife, bis die Größe der Warteschlange 0 wird
  #print("=====loop=====")
  #Q.printqu()
  #print("Qval"+str(Q.quval()))

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

  nextnodes=G.getedge(checknode)#④ Erfassen Sie den Knoten, der mit dem durch Enqueue erfassten Knoten verbunden ist
  #print("next nodes:"+str(nextnodes))

  for i in nextnodes:#⑤ Geben Sie jedem verbundenen Knoten Abstand
    #print(i)
    if DistList[NodeList.index(i)]==0:#⑥ Beurteilen Sie, ob es gesucht wurde (Entfernung zum Knoten wurde angegeben)
      if i!=StartNode:#⑦ Der Suchstartknoten liegt außerhalb des Gültigkeitsbereichs
        #print("enq")
        Q.enqu(i)#⑧ Enqueue, geben Sie Abstand, wenn nicht gesucht (suchen Sie es)
        DistList[NodeList.index(i)]=DistList[NodeList.index(checknode)]+1#⑨ Suche Erhöhen Sie den Abstand zum ursprünglichen Knoten um +1
    
    #print(DistList)

print("Entfernungsliste",DistList)

Wenn es sich um eine einfache Implementierung handelt, gibt es viele auf anderen Websites. Daher habe ich einen Kommentar zum Debuggen hinterlassen, das ich erstelle.

Der Algorithmus besteht darin, den Startknoten aus der Warteschlange zu entfernen und zu bestimmen. Den mit dem Abflugknoten verbundenen Knoten in die Warteschlange stellen. wiederholen.

Zeichnen von Grafiken und Suchergebnissen

import matplotlib.pyplot as plt
import collections
import copy

#Zeichnen eines Diagramms entsprechend der Suchentfernung
N=len(nodelist)
x=DistList#x-Koordinate ist Abstand
y=[0]*N#Für die Y-Koordinate werden Knoten mit derselben X-Koordinate in gleichen Intervallen angeordnet (die gleichen Intervalle werden unten berechnet).===
c=collections.Counter(DistList)#Finden Sie die Anzahl der überlappenden Elemente.
tmp=c.most_common()

c2=collections.Counter(DistList)#Korrekturzähler


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 ist y=0 Zeile
    y[n]=-c2[i]+tmpmean[i]
    c2[i]-=1
#===Bisher x,Ich möchte nur die y-Koordinate finden

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

#Diagrammerstellung
plt.figure(1)

#Knotenzeichnung
plt.scatter(x,y)

#Geben Sie der Knotenposition einen Knotennamen
ax=plt.axes()
for i in range(N):
  ax.annotate(str(nodelist[i])+":"+str(DistList[i]),(x[i],y[i]),size=20)

#Kanten zeichnen
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)

Die an jeden Knoten angehängte Anmerkung lautet (Knotennummer: Entfernung vom Suchstartknoten).

Zusammenfassung, zukünftige Ausgaben

-BFS selbst kann einfach mithilfe einer Warteschlangenstruktur implementiert werden. ・ Wir werden die Implementierung unter Verwendung der Bibliothek im Vorgriff auf die Praxis zusammenfassen. -Wenn mehrere Knoten mit demselben Abstand (derselben Hierarchie) nacheinander fortgesetzt werden, wird der Graph verdreht. Untersuchen Sie den Algorithmus zum Zeichnen von Diagrammen.