Skip to main content

Construct adjacency list by using adjacency matrix in scala

Scala program for Construct adjacency list by using adjacency matrix. Here problem description and other solutions.

import scala.collection.mutable._;
/*
    Scala program for
    Construct adjacency list using adjacency matrix
*/
class Graph(var vertices: Int,
	var adgeList: ArrayBuffer[ArrayBuffer[Int]])
{
	def this(matrix: Array[Array[Int]])
    {   
        this(matrix.length, new ArrayBuffer[ArrayBuffer[Int]](matrix.length))
        var i: Int = 0;
        while (i < this.vertices)
        {
            this.adgeList += new ArrayBuffer[Int]();
            i += 1;
        }
        this.makeAdjacencyList(matrix);
        
    }
	// Convert into adjacency list
	def makeAdjacencyList(matrix: Array[Array[Int]]): Unit = {
		var i: Int = 0;
		while (i < this.vertices)
		{
			var j: Int = 0;
			while (j < this.vertices)
			{
				if (matrix(i)(j) == 1)
				{
					this.addEdge(i, j);
				}
				j += 1;
			}
			i += 1;
		}
	}
	def addEdge(u: Int, v: Int): Unit = {
		if (u < 0 || u >= this.vertices || 
             v < 0 || v >= this.vertices)
		{
			return;
		}
		// Add node edge
		adgeList(u) += v;
	}
	// Display graph nodes and edges
	def printGraph(): Unit = {
		print("\n Graph Adjacency List ");
		var i: Int = 0;
		while (i < this.vertices)
		{
			print(" \n [" + i + "] :");
			var j: Int = 0;
			// iterate edges of i node
			while (j < this.adgeList(i).size)
			{
				if (j != 0)
				{
					print(" → ");
				}
				print(" " + this.adgeList(i)(j));
				j += 1;
			}
			i += 1;
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var matrix: Array[Array[Int]] = Array(
          Array(0, 1, 1, 0, 1), 
          Array(1, 0, 1, 0, 1), 
          Array(1, 1, 0, 1, 0), 
          Array(0, 1, 0, 0, 1), 
          Array(1, 1, 0, 1, 0)
        );
		var g: Graph = new Graph(matrix);
		// Display graph element
		g.printGraph();
	}
}

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