Posted on by Kalkicode
Code Graph

Implementation of BFS using adjacency list in node js

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

/*
    Node JS Program for 
    Breadth first traversal in directed graph
*/
class AjlistNode
{
	constructor(id)
	{
		// Set value of node key
		this.id = id;
		this.next = null;
	}
}
// Graph Vertices
class Vertices
{
	constructor(data)
	{
		this.data = data;
		this.next = null;
		this.last = null;
	}
}
// Create class of queue
class QNode
{
	constructor(value)
	{
		this.data = value;
		this.next = null;
	}
}
class MyQueue
{
	constructor()
	{
		this.head = null;
		this.tail = null;
		this.count = 0;
	}
	size()
	{
		return this.count;
	}
	isEmpty()
	{
		return this.count == 0;
	}
	// Add new node of queue
	enqueue(value)
	{
		// Create dynamic node
		var node = 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++;
		this.tail = node;
	}
	// Delete a element into queue
	dequeue()
	{
		if (this.head == null)
		{
			console.log("Empty Queue");
			return -1;
		}
		// Pointer variable which are storing 
		// the address of deleted node
		var temp = this.head;
		// Visit next node 
		this.head = this.head.next;
		this.count--;
		if (this.head == null)
		{
			// When deleting a last node 
			this.tail = null;
		}
		return temp.data;
	}
	// Get front node
	peek()
	{
		if (this.head == null)
		{
			console.log("Empty Queue");
			return -1;
		}
		return this.head.data;
	}
}
class Graph
{
	constructor(size)
	{
		// Set value
		this.size = size;
		this.node = Array(size).fill(null);
		this.setData();
	}
	// Set initial node value
	setData()
	{
		if (this.size <= 0)
		{
			console.log("\nEmpty Graph");
		}
		else
		{
			for (var index = 0; index < this.size; index++)
			{
				// Set initial node value
				this.node[index] = new Vertices(index);
			}
		}
	}
	//  Handling the request of adding new edge
	addEdge(start, last)
	{
		if (start >= 0 && start < this.size && 
            last >= 0 && last < this.size)
		{
			// Safe connection
			var edge = new AjlistNode(last);
			if (this.node[start].next == null)
			{
				this.node[start].next = edge;
			}
			else
			{
				// Add edge at the end
				this.node[start].last.next = edge;
			}
			// Get last edge 
			this.node[start].last = edge;
		}
		else
		{
			// When invalid nodes
			console.log("\nHere Something Wrong");
		}
	}
	printGraph()
	{
		if (this.size > 0)
		{
			// Print graph ajlist Node value
			for (var index = 0; index < this.size; ++index)
			{
				process.stdout.write("\nAdjacency list of vertex " + 
                                     index + " : ");
				var temp = this.node[index].next;
				while (temp != null)
				{
					// Display graph node 
					process.stdout.write("  " + this.node[temp.id].data);
					// Visit to next edge
					temp = temp.next;
				}
			}
		}
	}
	// Breadth first traversal for a directed graph node
	bfs(point)
	{
		if (point > this.size || this.size <= 0)
		{
			return;
		}
		var q = new MyQueue();
		var temp = null;
		// Set false to each element
		var visit = Array(this.size).fill(false);
		//Add first element into queue
		q.enqueue(point);
		process.stdout.write("\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;
			process.stdout.write("  " + q.peek());
			q.dequeue();
		}
	}
}

function main()
{
	// 6 implies the number of nodes in graph
	var g = 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);
}
// Start program execution
main();

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