DinS Written in 2017/12/8
BFS (breadth-first search)
The strategy of BFS can be summarized as below:
First chosen neighbor, first to visit.
This should remind you of queue’s FIFO. Yes, we actually use a queue to implement BFS.
Let’s see a concrete example below. This is a digraph with initial setup.
As a random choice, we’ll start from vertex B this time. To help understanding, I’ll add a queue to the left to denote chosen neighbors.
Vertex B is chosen as a candidate. We check B’s neighbors and push them in the queue. For this step they are C and D. Notice that there’s no absolute order for neighbors being pushed. We’ll use alphabet order here.
B is visited. According to BFS’s rule, we’ll choose C as the next candidate. In a more strict sense, we dequeue and the vertex we get will be the next candidate.
C is visited, and since it has no neighbor, we don’t need to enqueue. The next candidate we get is D. D has two neighbors A and F. We push them in the queue.
D is visited. The next candidate is A. A has two neighbors B and E. But notice that B is already visited. In graph search we will only visit the same vertex once, so we’ll just push E in the queue. And as an additional operation we’ll cut the edge from A to B.
A is visited, edge AB is cut. The next candidate we get from dequeue is F. F has noneighbor so this is an easy case.
F is visited. The next to visit is E. E has two neighbors D and G. Since D is visited we’ll only push G in the queue and cut the edge ED.
E is visited. The next is G. G has only one neighbor F but F is visited. As a result we’ll push no vertex in the queue and cut the edge GF.
Now that there’s no vertex in the queue, we’re done. Let’s see what we’ve got. If we tweak the graph a bit, changing vertexes’ position without touching connections, we can actually get this.
What we got is a tree. This is called BFS tree. Operating on a tree is much easier than on a graph. That’s the meaning of graph search.
You’ve probably figured out that if we start from different vertex, we can get different tree. That’s true. This time let’s start from vertex A as an example. It’s also a good opportunity to check if you’ve understood BFS.
Notice here that D is problematic. This is because D is both B and E’s neighbor and by this time D is not visited yet. Using previous method, we’ll push D in the queue so that there’re two Ds. This is not correct, however. Strictly speaking, D should be counted as discovered but not visited. Vertexes that are already in the queue but not visited are all like this. We don’t push discovered vertexes in the queue. That means we need to check in advance.
In a more programming sense, each vertex in BFS has a status: undiscovered, discovered or visited. We only push undiscovered vertexes in the queue, and then mark them as discovered. This will avoid the above problem.
So in this case, D is discovered as B’s neighbor. As a result, E will only push G in the queue and cut the edge ED.
The same story happens here for F. F is discovered but not visited, so G will not push F in the queue and will cut edge GF.
In the end we get this BFS tree.
One more notice. Sometimes if you start from certain vertex, you can’t get to the whole graph. Doing graph search using BFS actually means apply BFS to each vertex. This will cause many vertexes to become visited. After one round BFS, check the next vertex. If the vertex is already visited, skip it. In this way we can assure that all vertexes are visited once and only once.
I hope BFS isn’t too hard to understand.