Learnerslesson
   JAVA   
  SPRING  
  SPRINGBOOT  
 HIBERNATE 
  HADOOP  
   HIVE   
   ALGORITHMS   
   PYTHON   
   GO   
   KOTLIN   
   C#   
   RUBY   
   C++   




KOTLIN - BREADTH FIRST SEARCH CODE




Example :



import java.util.LinkedList;
import java.util.Queue;

var vertices = LinkedList<String>();
var adjacencyList = LinkedList<LinkedList<String>>();
var visited: BooleanArray = booleanArrayOf();
var level: IntArray = intArrayOf();

class BFS {
    
    fun insertVertex(vertex: String) {

        vertices.add(vertex);
    }

    fun constructAdjacencyList(vtx: String, adjcVertex: String) {

        var vtxIndex = vertices.indexOf(vtx);

        adjacencyList.add(LinkedList<String>());
        adjacencyList.get(vtxIndex).add(adjcVertex);
    }

    fun breadthFirstSearch(source: String) {

        var queue: Queue<Int> = LinkedList<Int>();

        var sourceIndex = vertices.indexOf(source);

        visited[sourceIndex] = true;
        queue.add(sourceIndex);

        while (queue.size != 0) {

            sourceIndex = queue.poll();

            var iter = adjacencyList.get(sourceIndex).iterator();
            while (iter.hasNext() ) {

                var str = iter.next();

                var i = vertices.indexOf(str);

                if (visited[i] == false) {

                    visited[i] = true;
                    level[i] = level[sourceIndex] + 1;

                    queue.add(i);
                }
            }
            print("${vertices.get(sourceIndex)} of level ${level[sourceIndex]} --> ");
        }
        print("\b\b\b\b");
    }
}

fun main(arr: Array<String>) {

    var V = 5;

    var bfs = BFS();

    visited = BooleanArray(V)

    level = IntArray(5);

    adjacencyList = LinkedList<LinkedList<String>>();

    vertices = LinkedList();

    // Insert Vertices

    bfs.insertVertex("a");
    bfs.insertVertex("b");
    bfs.insertVertex("c");
    bfs.insertVertex("d");
    bfs.insertVertex("e");

    // Construct Adjacency List

    bfs.constructAdjacencyList("a", "b");
    bfs.constructAdjacencyList("a", "c");
    bfs.constructAdjacencyList("a", "d");

    bfs.constructAdjacencyList("b", "a");
    bfs.constructAdjacencyList("b" ,"e");

    bfs.constructAdjacencyList("c", "a");
    bfs.constructAdjacencyList("c", "d");
    bfs.constructAdjacencyList("c", "e");

    bfs.constructAdjacencyList("d", "a");
    bfs.constructAdjacencyList("d" ,"c");
    bfs.constructAdjacencyList("d", "e");

    bfs.constructAdjacencyList("e", "b");
    bfs.constructAdjacencyList("e", "c");
    bfs.constructAdjacencyList("e", "d");

    bfs.breadthFirstSearch("c");
}


Output :



  c of level 0 --> a of level 1 --> d of level 1 --> e of level 1 --> b of level 2

Code Explanation for BFS - Breadth First Search


Let's list out, what all do we need to support Breadth First Search Data Structure.

  1. We need a Linked List to store the vertices.
    java_Collections

  2. We need a doubly Linked List to store the adjacency linked list.
    java_Collections

  3. We need a Queue and an array to store its Levels.

  4. We need a boolean array to store the Vertices that are already visited.

Now, let us see the above code.


We have a Linked List to store the Vertices.


var vertices = LinkedList<String>();

We also have a doubly Linked List to store the Adjacency List.


var adjacencyList = LinkedList<LinkedList<String>>();

Similarly, we have a Queue defined inside the method breadthFirstSearch(...).


var queue: Queue<Int> = LinkedList<Int>();

And, we have an array to store the Levels.


var visited: BooleanArray = booleanArrayOf();

And, there is a boolean array to store the Vertices that are visited.


static var visited: BooleanArray;

Note : The variables are marked as static, so that they could be accessed from main(...) method.

So, the first thing we will do is, insert the Vertices to the LinkedList<String> vertices Linked List.


vertices = LinkedList();

bfs.insertVertex("a");
bfs.insertVertex("b");
bfs.insertVertex("c");
bfs.insertVertex("d");
bfs.insertVertex("e");

Explanation of 'fun insertVertex(vertex: String)' method


fun insertVertex(vertex: String) {

	vertices.add(vertex);
}

fun insertVertex(vertex: String) is quite simple.


There is just one statement in it.


vertices.add(vertex);

It accepts vertex: String as a parameter and adds it to the Linked List, vertices.

java_Collections

The next thing we will do is, create an Adjacency List to track the Adjacent Vertices.


Let us take the example of vertex a, to explain the creation of Adjacency List.


As we have seen, a has three adjacent vertices(i.e. b, c and d). And we have used the constructAdjacencyList(...) method to construct the Adjacency Matrix.


bfs.constructAdjacencyList("a", "b");
bfs.constructAdjacencyList("a", "c");
bfs.constructAdjacencyList("a", "d");

Note : Just remember, creating an Adjacency List above is same as creating an Edge. As the Adjacency List is actually a group of Edges.


Explanation of 'fun constructAdjacencyList(vtx: String, adjcVertex: String)' method


fun constructAdjacencyList(vtx: String, adjcVertex: String) {

	var vtxIndex = vertices.indexOf(vtx);

	adjacencyList.add(LinkedList<String>());
	adjacencyList.get(vtxIndex).add(adjcVertex);
}

Although, the above method is explained in Adjacency List Code tutorial. I will give a brief explanation in this tutorial.


When a method call is made,

java_Collections

The variable vtx is assigned with value "a" and adjcVertex is assigned with "b".


Now, the first line,


var vtxIndex = vertices.indexOf(vtx);

Calculates the index/position of Vertex a. And as we can see the index a is 0.


Now, in the next line,


adjacencyList.add(LinkedList<String>());

We are initialising the first row of the 2D Linked List, adjacencyList.


But with what ?


We are initialising it with a Linked List LinkedList<String>(),


adjacencyList.add(LinkedList<String>());

So that the first row can hold the Adjacency List for vertex a.

java_Collections

Similarly, the second row should hold the Adjacency List for vertex b and so on.


And in this iteration, our target is to find out the first row(To create an Adjacency List for vertex a) and insert vertex b to it.


And the below code does that.


adjacencyList.get(vtxIndex).add(adjcVertex);

We get the index of vertex a


vtxIndex = vertices.indexOf(vtx);

As we know vtx is a.


Then add adjcVertex(That contains vertex b) to the 0th index of adjacencyList.


adjacencyList.get(0).add("b");

And following it we form the Adjacency List.


Then we come across the most important method fun breadthFirstSearch(source: String) that performs the Breadth First Search (BFS).


Explanation of 'fun breadthFirstSearch(source: String)' method


fun breadthFirstSearch(source: String) {

	var queue: Queue<Int> = LinkedList<Int>();

	var sourceIndex = vertices.indexOf(source);

	visited[sourceIndex] = true;
	queue.add(sourceIndex);

	while (queue.size != 0) {

		sourceIndex = queue.poll();

		var iter = adjacencyList.get(sourceIndex).iterator();
		while (iter.hasNext() ) {

			var str = iter.next();

			var i = vertices.indexOf(str);

			if (visited[i] == false) {

				visited[i] = true;
				level[i] = level[sourceIndex] + 1;

				queue.add(i);
			}
		}
		print("${vertices.get(sourceIndex)} of level ${level[sourceIndex]} --> ");
	}
	print("\b\b\b\b");
}

So, we are calling the method


bfs.breadthFirstSearch("c");

Passing the vertex c as source.


Below is the graph on which we had to perform a Breadth First Search (BFS).

java_Collections

To perform Breadth First Search (BFS), all we need is a Linked List to keep track of Vertices. Which we have in place.

java_Collections

And, we need a 2D Adjacency List to keep a track of Adjacent Vertices. And we also have that in place.

java_Collections

We also need a boolean array to keep a track of which all vertices are visited. Which we also have in place. All the values default to false.

java_Collections

Lastly, we need the integer array to store the Levels, that is initialised with 0.

java_Collections

Now, since we have everything in place. Let us understand the fun breadthFirstSearch(...) method.


So, if we see the first line of the above method,


var queue: Queue<Int> = LinkedList<Int>();

We have declared the Queue to maintain the order of Breadth First Search (BFS).


Next, we will try to find the index of the source vertex,


var sourceIndex = vertices.indexOf(source);

In this case our source vertex is c. i.e. We will start traversing the graph from c. And the index of vetex c is 2.


So, the next thing we will do is mark vertex c as visited. i.e. We will mark the position of Vertex c to true in the Visited Array.


visited[sourceIndex] = true;
java_Collections


And add the vertex c to the Queue.


	queue.add(sourceIndex);
java_Collections


Next, we come to the while() loop, that will continue until the Queue is not empty.


while (queue.size != 0) {

	sourceIndex = queue.poll();

	var iter = adjacencyList.get(sourceIndex).iterator();
	while (iter.hasNext() ) {

		var str = iter.next();
		var i = vertices.indexOf(str);

		if (visited[i] == false) {

			visited[i] = true;
			level[i] = level[sourceIndex] + 1;
			queue.add(i);
		}
	}
	print("${vertices.get(sourceIndex)} of level ${level[sourceIndex]} --> ");
}

Inside the while() loop, we write the below statement to get the vertex c out of the Queue and get its index in sourceIndex.


sourceIndex = queue.poll();

The next task we do is, try finding the Adjacent Vertices of vertex c.


As we know the Adjacent Vertices of vertex c are,

java_Collections

To find the Adjacent Vertices of c, we have used the below while loop,


var iter = adjacencyList.get(sourceIndex).iterator();
while (iter.hasNext() )

And the while loop itself needs a little explanation.(HIDE THE BELOW POINTS UNDER DROPDOWN)

  1. The first statement of the for loop (i.e. The initialisation section of the loop),

    var iter = adjacencyList.get(sourceIndex).iterator();


    is where we get the Adjacent Vertices of vertex c in the iter.

    Thinking How ?

    Well ! The adjacencyList is a 2D Linked List that stores the adjacent vertices. And the trick is played in,

    adjacencyList.get(sourceIndex).iterator()


    As we have seen, the sourceIndex is 2 (Because the index of vertex c is 2).

    And the iter variable of Iterator<String> gets the adjacency list of vertex c in it.

  2. The next statement,

    iter.hasNext()


    tells the for loop to continue until there are elements in the list.

  3. And ! Well ! There is no increment section. We have left it blank

Moral of the story


iter variable of Iterator<String>, stores the Adjacency List of vertex c in it.So, iter has the elements a, d and e in it.


Inside the for loop, firstly we collect the first element(i.e. a) of the Adjacency List of vertex c.


var str = iter.next();

As we know the variable str contains a. Now, it's time to check the index of a.


Which we have done in the next line.


var i = vertices.indexOf(str);

And found that the index of a is 0.

java_Collections

Then in the next few lines, we check, if we have visited vertex a or not. So we check in the visited[] array.

java_Collections

And find that visited[0] is set to false. So, we get into the below if condition.


if (visited[i] == false) {

	visited[i] = true;
	level[i] = level[sourceIndex] + 1;

	queue.add(i);
}

Firstly, we mark visited[0] to true. Then increase the level[] array by 1.


And finally add the vertex a to the Queue.

java_Collections
java_Collections
java_Collections

We keep on checking the adjacency lists of the individual vertices and continue the same process until the Queue is empty.