Skip to main content

What are Graphs? – Part 4 BFS

· 3 min read
Strider

Hi, in the fourth part of my graph series, I want to talk about breadth-first search. We have programmed the depth-first search in Python in the third part. Now we will go into the breadth-first search.

Before we do that, let's take a look at the graph.

dia.png

The breadth-first search works differently than the depth-first search, because here we go through the graph plane by plane. In the breadth-first search, we again choose a random starting node. After we have done this, we create a queue. We mark the selected start node as visited and add it to the queue. Now comes the exciting part, because now we work through the queue. We take a node out of the queue and look at who it has as visitable neighbor nodes. But here the neighbor nodes are considered as child nodes. Our starting node is the first level.

The neighboring nodes of the start node form the second level. As you can see, it goes on like this. In contrast to the depth-first search, we visit all child nodes of the current node. But before we go one level deeper, we check if they are already visited or not. These child nodes are then all marked as visited. The child nodes of the child nodes are also queued. And now we can go one level deeper. When the queue is empty our search is finished.

A small animation shows how the breadth-first search works:

animation.gif

The blue marks, are the visits of the nodes. The red crosses mean that this node cannot be visited, because it has already been visited. Again, all nodes are marked as not visited.

Extend our graph implementation

Now we extend our Graph class with the breadth-first search. I have implemented this iteratively here.

def mstBFS(self, key):
self.unvisitAllNodes()
q = Queue()
start =self.getNode(key)
q.put(start)
start.visit()
while not q.empty():
next = q.get()
print("Visited ", next.getKey())
for edge in next.getEdges():
if not edge.getB().isVisited():
print(edge.getA().getKey(), "--->", edge.getB().getKey(), "weight:", edge.getWeight())
q.put(edge.getB())
edge.getB().visit()

Here, after a closer look, we see that our selected start node, is marked as visited. After that this node is added to the queue. To process all nodes from the queue until the queue is empty, we use a while loop that checks and saves exactly that. Per run, one node is taken from the queue and output as visited. Next, the child nodes of the affected node are determined. The child nodes, which were marked as not visited, are added to the queue. The whole runs then as long as until the Queue is empty.

I hope I could explain the width search understandably 😄