Yanyi Bao
0%

BFS Search Algorithm

Posted on Edited on

In one of my recent projects, I needed to find the shortest path from one state to another. This reminds me of the Breadth-First Search Algorithm.

Breadth-First Search is commonly used in traverse all the nodes in the graph and finding the shortest path between two nodes in a graph where all edges have equal and positive weights. In most cases, the Breadth-First Search algorithm can find the shortest path without traversing all the nodes and paths.

The Breadth-First Search algorithm traverses nodes layer by layer. So, intuitively, the depth you traversed is the shortest path.

In my project, the original data are organized like this. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
{
    "Washington": [
        "Oregon",
        "Idaho"
    ],
    "Oregon": [
        "Washington",
        "Idaho",
        "Nevada",
        "California"
    ],
    "Nevada": [
        "Oregon",
        "Idaho",
        "Utah",
        "California",
        "Arizona"
    ],
    ...
    
}
Firstly, we need to read and deserialize them. 
1
2
TextAsset jsonTextFile = Resources.Load<TextAsset>("Text/AdjacentStates");
m_allStaesAdjacents = JsonConvert.DeserializeObject<Dictionary<string, string[]>>(jsonTextFile.text);
Breadth-First Search uses the queue data structure to store the nodes. The queue data structure is First In First Out, so the nodes will be visited layer by layer. 
1
2
var frontier = new Queue<string>();
frontier.Enqueue(origin);
And we need a dictionary to store every nodes' father node, so we can trace the path. 
1
Dictionary<string, string> prevNodes = new Dictionary<string, string>();
Firstly, we enqueue the start nodes. And then, every time, we dequeue the first node. Check it weather it's the target nodes. If true, we find the shorest path and jump out of the iteration. Otherwise, we enqueue all the un-visitied child nodes into the queue. 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
while(frontier.Count > 0)
{
    var current = frontier.Dequeue();

    if (current == destination)
        break;

    if (!m_allStaesAdjacents.ContainsKey(current))
        continue;

    foreach(var next in m_allStaesAdjacents[current])
    {
        if(!prevNodes.ContainsKey(next))
        {
            frontier.Enqueue(next);
            prevNodes[next] = current;
        }
    }
}
if until the queue is empty, we still not find the target node, that means it's unreachable. Otherwise, we can trace back to build the shortest route. 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
routes.Clear();
string node = destination;
while(node != origin)
{
    // no father node find
    // cannot reach
    if(!prevNodes.ContainsKey(node))
    {
        routes.Clear();
        Debug.Log(string.Format("Can not find any path from {0} to {1}, check the map info json!", origin, destination));
        return false;
    }

    routes.Add(node);
    node = prevNodes[node];
}
Breadth-First Search algorithm is simple and reliable.