Are you planning a Europe trip such that you start covering the countries which are adjacent to where you landed. BFS can help with that.
Learning by solving a problem is one of the best ways to learn, have created a video tutorial explaining BFS in graph with target of finding which European countries you should visit if you land in one of the country and want to see other countries which are adjacent to place you landed.
breath_first_searchgraphdata_structuresalgorithms
Understand breath first search algorithm in a graph, we will be using JS to write our code. There are two way to represent a graph as in programming terms, adjacency matrix and adjacency list. Both have their pros and cons, we will be using adjacency list.
I find it easier to understand to understand with example, here will be taking the example of Europe. We already have our adjacency list created, but we will go through the methods to better understand the same, or use a map inside the class.
const EU = {
Denmark: "Denmark",
Poland: "Poland",
Luxembourg: "Luxembourg",
Austria: "Austria",
Czech: "Czech",
France: "France",
Belgium: "Belgium",
Netherlands: "Netherlands",
Norway: "Norway",
Sweden: "Sweden",
Finland: "Finland",
Russia: "Russia",
Italy: "Italy",
Slovenia: "Slovenia",
Hungary: "Hungary",
Slovakia: "Slovakia",
Malta: "Malta",
Greece: "Greece",
Slovenia: "Slovenia",
Slovakia: "Slovakia",
Germany: "Germany",
Switzerland: "Switzerland",
Spain: "Spain",
Portugal: "Portugal",
Ireland: "Ireland",
UnitedKingdom: "UnitedKingdom",
Iceland: "Iceland",
Liechtenstein: "Liechtenstein",
Monaco: "Monaco",
SanMarino: "SanMarino",
VaticanCity: "VaticanCity",
Andorra: "Andorra",
Albania: "Albania",
BosniaAndHerzegovina: "BosniaAndHerzegovina",
Bulgaria: "Bulgaria",
Croatia: "Croatia",
Cyprus: "Cyprus",
Estonia: "Estonia",
FaroeIslands: "FaroeIslands",
Gibraltar: "Gibraltar",
Greece: "Greece",
Guernsey: "Guernsey",
Hungary: "Hungary",
Lithuania: "Lithuania",
Belarus: "Belarus",
Latvia: "Latvia",
Macedonia: "Macedonia",
Ukraine: "Ukraine"
}
const europeAdjList = {
[EU.Germany]: [EU.Denmark, EU.Poland, EU.Luxembourg, EU.Austria, EU.Poland, EU.Czech, EU.France, EU.Belgium, EU.Netherlands],
[EU.Norway]: [EU.Sweden, EU.Finland, EU.Russia],
[EU.Austria]: [EU.Italy, EU.Slovakia, EU.Hungary, EU.Slovenia, EU.Czech],
[EU.Italy]: [EU.Malta, EU.Greece, EU.France, EU.Slovenia],
[EU.France]: [EU.UnitedKingdom, EU.Belgium, EU.Netherlands, EU.Germany, EU.Italy, EU.Spain],
[EU.Spain]: [EU.Portugal, EU.France],
[EU.Portugal]: [EU.Spain],
[EU.UnitedKingdom]: [EU.Ireland, EU.France],
[EU.Ireland]: [EU.UnitedKingdom],
[EU.Croatia]: [EU.BosniaAndHerzegovina, EU.Serbia, EU.Bulgaria, EU.Hungary, EU.Slovenia],
[EU.BosniaAndHerzegovina]: [EU.Croatia, EU.Serbia, EU.Montenegro],
[EU.Serbia]: [EU.BosniaAndHerzegovina, EU.Montenegro, EU.Kosovo, EU.Bulgaria, EU.Hungary, EU.Romania, EU.Macedonia, EU.Greece],
[EU.Montenegro]: [EU.BosniaAndHerzegovina, EU.Serbia, EU.Albania],
[EU.Albania]: [EU.Montenegro, EU.Greece, EU.Macedonia],
[EU.Greece]: [EU.Albania, EU.Macedonia, EU.Bulgaria, EU.Turkey, EU.Cyprus],
[EU.Bulgaria]: [EU.Greece, EU.Serbia, EU.Romania, EU.Hungary, EU.Turkey],
[EU.Romania]: [EU.Bulgaria, EU.Serbia, EU.Hungary, EU.Ukraine],
[EU.Hungary]: [EU.Romania, EU.Serbia, EU.Croatia, EU.Slovakia, EU.Austria, EU.Slovenia, EU.Bulgaria],
[EU.Slovakia]: [EU.Hungary, EU.Austria, EU.Poland, EU.Ukraine, EU.Czech],
[EU.Czech]: [EU.Slovakia, EU.Poland, EU.Germany, EU.Austria],
[EU.Poland]: [EU.Slovakia, EU.Germany, EU.Czech, EU.Lithuania, EU.Belarus, EU.Ukraine],
[EU.Lithuania]: [EU.Poland, EU.Belarus, EU.Latvia],
[EU.Belarus]: [EU.Lithuania, EU.Poland, EU.Ukraine, EU.Latvia, EU.Russia],
[EU.Ukraine]: [EU.Belarus, EU.Poland, EU.Slovakia, EU.Romania, EU.Hungary, EU.Russia],
[EU.Russia]: [EU.Ukraine, EU.Belarus, EU.Latvia, EU.Estonia, EU.Finland, EU.Norway, EU.Sweden],
[EU.Latvia]: [EU.Lithuania, EU.Belarus, EU.Russia, EU.Estonia],
[EU.Estonia]: [EU.Latvia, EU.Belarus, EU.Russia],
[EU.Slovenia]: [EU.Italy, EU.Croatia, EU.Hungary, EU.Austria, EU.Germany],
[EU.Malta]: [EU.Italy],
[EU.Sweden]: [EU.Norway, EU.Finland, EU.Russia],
[EU.Finland]: [EU.Sweden, EU.Norway, EU.Russia],
[EU.Denmark]: [EU.Germany, EU.Sweden],
[EU.Switzerland]: [EU.Germany, EU.France, EU.Italy, EU.Austria],
[EU.Iceland]: [EU.UnitedKingdom],
[EU.Liechtenstein]: [EU.Austria, EU.Switzerland],
[EU.Monaco]: [EU.France],
[EU.SanMarino]: [EU.Italy],
[EU.VaticanCity]: [EU.Italy]
};
// Queue class
class Queue
{
// Array is used to implement a Queue
constructor()
{
this.items = [];
}
enqueue(element)
{
// adding element to the queue
this.items.push(element);
}
dequeue()
{
// removing element from the queue
if(this.isEmpty())
throw new Error("Underflow");
return this.items.shift(); // pop but from front
}
// front function
peek()
{
// returns the Front element of
// the queue without removing it.
if(this.isEmpty())
return "No elements in Queue";
return this.items[0];
}
isEmpty() {
return this.items.length === 0;
}
// printQueue()
}
// create a graph class
class Graph {
// defining vertex array and
// adjacent list
constructor(noOfVertices)
{
this.noOfVertices = noOfVertices;
this.AdjList = europeAdjList;
}
// add vertex to the graph
addVertex(v)
{
// initialize the adjacent list with a
// null array
this.AdjList.set(v, []);
}
// add edge to the graph
addEdge(v, w)
{
// get the list for vertex v and put the
// vertex w denoting edge between v and w
this.AdjList.get(v).push(w);
// Since graph is undirected,
// add an edge from w to v also
this.AdjList.get(w).push(v);
}
// Prints the vertex and adjacency list
printGraph()
{
// get all the vertices
var get_keys = this.AdjList.keys();
// iterate over the vertices
for (var i of get_keys)
{
// get the corresponding adjacency list
// for the vertex
var get_values = this.AdjList.get(i);
var conc = "";
// iterate over the adjacency list
// concatenate the values into a string
for (var j of get_values)
conc += j + " ";
// print the vertex and its adjacency list
console.log(i + " -> " + conc);
}
}
// function to performs BFS
bfs(startingNode)
{
// create a visited object
var visited = {};
// Create an object for queue
var q = new Queue();
// add the starting node to the queue
visited[startingNode] = true;
q.enqueue(startingNode);
// loop until queue is empty
while (!q.isEmpty()) {
// get the element from the queue
var getQueueElement = q.dequeue();
// passing the current vertex to callback function
console.log(getQueueElement);
// get the adjacent list for current vertex
var adj_list = this.AdjList[getQueueElement];
// loop through the list and add the element to the
// queue if it is not processed yet
for (var i in adj_list) {
var neigh = adj_list[i];
if (!visited[neigh]) {
visited[neigh] = true;
q.enqueue(neigh);
}
}
}
}
// Main DFS method
dfs(startingNode)
{
var visited = {};
this.DFSUtil(startingNode, visited);
}
// Recursive function which process and explore
// all the adjacent vertex of the vertex with which it is called
DFSUtil(vert, visited)
{
visited[vert] = true;
console.log(vert);
var get_neighbours = this.AdjList.get(vert);
for (var i in get_neighbours) {
var get_elem = get_neighbours[i];
if (!visited[get_elem])
this.DFSUtil(get_elem, visited);
}
}
}
// Using the above implemented graph class
var g = new Graph(37);
console.log("BFS");
g.bfs('Poland');
// prints
// DFS
// A B C E D F
console.log("DFS");
// g.dfs('A');
Links
- https://www.geeksforgeeks.org/breadth-first-search-or-bfs-for-a-graph/
- https://www.geeksforgeeks.org/applications-of-breadth-first-traversal/?ref=appendix
- https://github.com/hearsid/gfg-dsa-course
- https://www.geeksforgeeks.org/comparison-between-adjacency-list-and-adjacency-matrix-representation-of-graph/
- https://www.google.com/maps/place/Europe/@51.256878,1.1849127,2636035m/data=!3m1!1e3!4m5!3m4!1s0x46ed8886cfadda85:0x72ef99e6b3fcf079!8m2!3d54.5259614!4d15.2551187
- https://www.javatpoint.com/list-of-european-countries
- https://ksvi.mff.cuni.cz/~dingle/2017/lecture10/europe_bfs_reversed.svg
