Scenes where breadth-first search (BFS) is required (preface)

I encountered a problem of finding the shortest distance between two points in a tree-structured graph with Atcoder. At that time, I created the algorithm by myself, but I couldn't solve the problem, so I decided to create BFS properly. When actually using it, I will use a convenient library, This time, I will program and organize the basic idea. Reimplementation using the library will be done at a later date.

Up to the last time, I made a tree structure class and a drawing program. Create your own graph structure class and its drawing with python
The following articles about BFS have been summarized in detail, so I used them as a reference. [BFS (Breadth-first Search) Super Introduction! ~ Use the queue vividly ~] (https://qiita.com/drken/items/996d80bcae64649a6580)

Implementation

Since the introduction is good, implement it below.

Graph structure class definition

#Creating a graph structure
class cglaph():
  def __init__(self):
    #Node initialization
    self.nodes={}

  def addnode(self,num):#① Add a node
    for i in self.nodes.keys():
      if i==num:
        return(False)
    else:
      self.nodes[num]=list()
      return(True)

  def addedge(self,ag1,ag2):#② Add an edge
    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):    #③ Display the node
    print("■Glaph:")
    print("vertice:neighbors")
    for k,v in self.nodes.items():
      print(k,":",v)


  def getnodes(self):#④ Returns a list of nodes
    keylist=list()

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

  def getedge(self, node):#⑤ Returns the edge (connected node) of the specified node.
    return self.nodes[node]

Concept of this tree structure class

Node information is stored in dictionary type. The node number is stored in key, and the nodes connected to that node are stored in a list in value. Insert the following method. ① Add node ② Add edge ③ Display of nodes (and nodes connected to them) ④ Returns a list of nodes ⑤ Returns a list of nodes connected to the specified node

Queue structure class definition

#Definition of queue structure
class cqu():
  def __init__(self):
    #Queue initialization
    self.qu=list()
    self.head=0
    self.tail=-1

  def quval(self):#① Queue size
    return self.tail-self.head+1

  def printqu(self):#② Display the contents of the queue
    print(str(self.qu[self.head:self.tail+1])+",head:"+str(self.head)+",tail:"+str(self.tail))
    print(self.qu)

  def enqu(self,num):#③ Enqueue
    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 of queue structure class

The queue has a list structure and has variables such as pointers that indicate the beginning and end. Have the following method. ① Return the size of the queue ② Display the contents of the queue ③ Enqueue ④ Decue

Creating a tree structure

G=cglaph()

G.addnode(1)#Add node
G.addnode(2)
G.addnode(3)
G.addnode(4)
G.addnode(5)
G.addedge(1,2)#Add edge
G.addedge(2,3)
G.addedge(3,4)
G.addedge(4,5)
G.addedge(2,4)
G.printnodes()#List of nodes

nodelist=G.getnodes()#Get node list
print ("NODE LIST:",nodelist)

G.getedge(1)#Node connected to node 1

The image is the graph below

The coordinates of the node when drawing the graph are Using the distance from the search start node in BFS is a little better, so I'll draw it last.

BFS implementation


StartNode=1

#Target graph G
G.printnodes()

#List to record distance
NodeList=G.getnodes()
#print(NodeList)
DistList=[0]*len(NodeList)

#Queue structure generation
Q=cqu()

#① Enqueue the search start node
Q.enqu(StartNode)
#Q.printqu()

while Q.quval():#② Loop until the size of the queue becomes 0
  #print("=====loop=====")
  #Q.printqu()
  #print("Qval"+str(Q.quval()))

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

  nextnodes=G.getedge(checknode)#④ Acquire the node connected to the node acquired by enqueue
  #print("next nodes:"+str(nextnodes))

  for i in nextnodes:#⑤ Give a distance to each connected node
    #print(i)
    if DistList[NodeList.index(i)]==0:#⑥ Judge whether it has been searched (distance has been given to the node)
      if i!=StartNode:#⑦ Search start node is out of scope
        #print("enq")
        Q.enqu(i)#⑧ Enqueue, give distance if not searched (make it searched)
        DistList[NodeList.index(i)]=DistList[NodeList.index(checknode)]+1#⑨ Search Increase the distance from the original node by +1
    
    #print(DistList)

print("Distance list",DistList)

If it is a simple implementation, there are many on other sites, so I have left a comment for debugging that I am creating.

The algorithm is to dequeue and determine the starting node. Enqueue the node connected to the departure node. repeat.

Drawing graphs and search results

import matplotlib.pyplot as plt
import collections
import copy

#Drawing a graph according to the search distance
N=len(nodelist)
x=DistList#x coordinate is distance
y=[0]*N#For the Y coordinate, nodes with the same X coordinate are arranged at equal intervals (the equal intervals are calculated below).===
c=collections.Counter(DistList)#Find the number of overlapping elements.
tmp=c.most_common()

c2=collections.Counter(DistList)#Correction counter


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 is y=0 line
    y[n]=-c2[i]+tmpmean[i]
    c2[i]-=1
#===So far x,I just want to find the y coordinate

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

#Graph creation
plt.figure(1)

#Node drawing
plt.scatter(x,y)

#Give the node name to the node position
ax=plt.axes()
for i in range(N):
  ax.annotate(str(nodelist[i])+":"+str(DistList[i]),(x[i],y[i]),size=20)

#Draw edges
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)

The annotation attached to each node is (node number: distance from the search start node).

Summary, future issues

-BFS itself can be easily implemented using a queue structure. ・ We will summarize the implementation using the library in anticipation of practice. -If multiple nodes with the same distance (same hierarchy) continue in succession, the graph will be twisted. Examine the graph drawing algorithm.