Skip to main content

Construct adjacency list by using adjacency matrix in node js

Js program for Construct adjacency list by using adjacency matrix. Here problem description and explanation.

/*
    Node JS program for
    Construct adjacency list using adjacency matrix
*/
class Graph
{
	constructor(matrix)
	{
		// Set number of nodes
		this.vertices = matrix.length;
		this.adgeList = [];
		// Create memory of adgeList of each vertice
		for (var i = 0; i < this.vertices; ++i)
		{
			this.adgeList.push([]);
		}
		this.makeAdjacencyList(matrix);
	}
	// Convert into adjacency list
	makeAdjacencyList(matrix)
	{
		for (var i = 0; i < this.vertices; ++i)
		{
			for (var j = 0; j < this.vertices; ++j)
			{
				if (matrix[i][j] == 1)
				{
					this.addEdge(i, j);
				}
			}
		}
	}
	addEdge(u, v)
	{
		if (u < 0 || u >= this.vertices || 
            v < 0 || v >= this.vertices)
		{
			return;
		}
		// Add node edge
		this.adgeList[u].push(v);
	}
	// Display graph nodes and edges
	printGraph()
	{
		process.stdout.write("\n Graph Adjacency List ");
		for (var i = 0; i < this.vertices; ++i)
		{
			process.stdout.write(" \n [" + i + "] :");
			// iterate edges of i node
			for (var j = 0; j < this.adgeList[i].length; j++)
			{
				if (j != 0)
				{
					process.stdout.write(" → ");
				}
				process.stdout.write(" " + this.adgeList[i][j]);
			}
		}
	}
}

function main()
{
	var matrix = [
		[0, 1, 1, 0, 1],
		[1, 0, 1, 0, 1],
		[1, 1, 0, 1, 0],
		[0, 1, 0, 0, 1],
		[1, 1, 0, 1, 0]
	];
	var g = new Graph(matrix);
	// Display graph element
	g.printGraph();
}
// Start program execution
main();

Output

 Graph Adjacency List
 [0] : 1 →  2 →  4
 [1] : 0 →  2 →  4
 [2] : 0 →  1 →  3
 [3] : 1 →  4
 [4] : 0 →  1 →  3




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