Posted on by Kalkicode
Code Graph

Implementation of BFS using adjacency list in scala

Scala program for Implementation of BFS using adjacency list. Here problem description and explanation.

/*
    Scala Program for 
    Breadth first traversal in directed graph
*/
class AjlistNode(
	// Vertices node key
	var id: Int,
		var next: AjlistNode)
{
	def this(id: Int)
	{
		// Set value of node key
		this(id, null);
	}
}
// Graph Vertices
class Vertices(var data: Int,
	var next: AjlistNode,
		var last: AjlistNode)
{
	def this(data: Int)
	{
		this(data, null, null);
	}
}
// Create class of queue
class QNode(var data: Int,
	var next: QNode)
{
	def this(value: Int)
	{
		this(value, null);
	}
}
class MyQueue(var head: QNode,
	var tail: QNode,
		var count: Int)
{
	def this()
	{
		this(null, null, 0);
	}
	def size(): Int = {
		return this.count;
	}
	def isEmpty(): Boolean = {
		return this.count == 0;
	}
	// Add new node of queue
	def enqueue(value: Int): Unit = {
		// Create dynamic node
		var node: QNode = new QNode(value);
		if (this.head == null)
		{
			// Add first element into queue
			this.head = node;
		}
		else
		{
			// Add node at the end using tail 
			this.tail.next = node;
		}
		this.count += 1;
		this.tail = node;
	}
	// Delete a element into queue
	def dequeue(): Int = {
		if (this.head == null)
		{
			println("Empty Queue");
			return -1;
		}
		// Pointer variable which are storing 
		// the address of deleted node
		var temp: QNode = this.head;
		// Visit next node 
		this.head = head.next;
		this.count -= 1;
		if (this.head == null)
		{
			// When deleting a last node 
			this.tail = null;
		}
		return temp.data;
	}
	// Get front node
	def peek(): Int = {
		if (this.head == null)
		{
			println("Empty Queue");
			return -1;
		}
		return this.head.data;
	}
}
class Graph(
	// Number of Vertices
	var size: Int,
		var node: Array[Vertices])
{
	def this(size: Int)
	{
		// Set value
		this(size, Array.fill[Vertices](size)(null));
      	this.setData();
	}
	// Set initial node value
	def setData(): Unit = {
		if (size <= 0)
		{
			println("\nEmpty Graph");
		}
		else
		{
			var index: Int = 0;
			while (index < size)
			{
				// Set initial node value
				node(index) = new Vertices(index);
				index += 1;
			}
		}
	}
	//  Handling the request of adding new edge
	def addEdge(start: Int, last: Int): Unit = {
		if (start >= 0 && start < size && last >= 0 && last < size)
		{
			// Safe connection
			var edge: AjlistNode = new AjlistNode(last);
			if (node(start).next == null)
			{
				node(start).next = edge;
			}
			else
			{
				// Add edge at the end
				node(start).last.next = edge;
			}
			// Get last edge 
			node(start).last = edge;
		}
		else
		{
			// When invalid nodes
			println("\nHere Something Wrong");
		}
	}
	def printGraph(): Unit = {
		if (size > 0)
		{
			var index: Int = 0;
			// Print graph ajlist Node value
			while (index < size)
			{
				print("\nAdjacency list of vertex " + index + " : ");
				var temp: AjlistNode = node(index).next;
				while (temp != null)
				{
					// Display graph node 
					print("  " + node(temp.id).data);
					// Visit to next edge
					temp = temp.next;
				}
				index += 1;
			}
		}
	}
	// Breadth first traversal for a directed graph node
	def bfs(point: Int): Unit = {
		if (point > this.size || this.size <= 0)
		{
			return;
		}
		var q: MyQueue = new MyQueue();
		var temp: AjlistNode = null;
		// Set false to each element
		var visit: Array[Boolean] = Array.fill[Boolean](size)(false);
		//Add first element into queue
		q.enqueue(point);
		print("\n BFS :");
		while (q.isEmpty() == false)
		{
			temp = this.node(q.peek()).next;
			while (temp != null)
			{
				if (!visit(temp.id))
				{
					visit(temp.id) = true;
					q.enqueue(temp.id);
				}
				// visit to next edge
				temp = temp.next;
			}
			visit(q.peek()) = true;
			print("  " + q.peek());
			q.dequeue();
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		// 6 implies the number of nodes in graph
		var g: Graph = new Graph(6);
		// Connect node with an edge
		g.addEdge(0, 1);
		g.addEdge(0, 5);
		g.addEdge(1, 1);
		g.addEdge(2, 1);
		g.addEdge(3, 0);
		g.addEdge(3, 3);
		g.addEdge(4, 2);
		g.addEdge(4, 3);
		g.addEdge(5, 1);
		// print graph element
		g.printGraph();
		g.bfs(4);
	}
}

Output

Adjacency list of vertex 0 :   1  5
Adjacency list of vertex 1 :   1
Adjacency list of vertex 2 :   1
Adjacency list of vertex 3 :   0  3
Adjacency list of vertex 4 :   2  3
Adjacency list of vertex 5 :   1
 BFS :  4  2  3  1  0  5

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment