« Previous Next »

Construct adjacency list using adjacency matrix

Given a 2d matrix that represents the node connections of an adjacency matrix. Our goal is to create a graph, which is in the form of an adjacency list, using the given adjacency matrix. For example.

Generating adjacency list using adjacency matrix

In above example adjacency matrix is form of directed graph. And adjacency list is indicates the constructed result.

Here given code implementation process.

import java.util.ArrayList;
/*
    Java Program
    Construct adjacency list using adjacency matrix
*/
public class Graph
{
    public int vertices;
    public ArrayList < ArrayList < Integer >> adgeList;
    public Graph(int[][] matrix)
    {
        this.vertices = matrix.length;
        this.adgeList = new ArrayList < ArrayList < Integer >> (matrix.length);
        for (int i = 0; i < this.vertices; ++i)
        {
            this.adgeList.add(new ArrayList < Integer > ());
        }
        this.makeAdjacencyList(matrix);
    }
    public void addEdge(int u, int v)
    {
        if (u < 0 || u >= this.vertices || 
            v < 0 || v >= this.vertices)
        {
            return;
        }
        // Add node edge
        adgeList.get(u).add(v);
    }
    public void makeAdjacencyList(int[][] matrix)
    {
        for (int i = 0; i < this.vertices; ++i)
        {
            for (int j = 0; j < this.vertices; ++j)
            {
                if (matrix[i][j] == 1)
                {
                    this.addEdge(i, j);
                }
            }
        }
    }
    // Display graph nodes and edges
    public void printGraph()
    {
        System.out.print("\n Graph Adjacency List ");
        for (int i = 0; i < this.vertices; ++i)
        {
            System.out.print(" \n [" + i + "] :");
            // iterate edges of i node
            for (int j = 0; j < this.adgeList.get(i).size(); j++)
            {
                if (j != 0)
                {
                    System.out.print(" → ");
                }
                System.out.print(" " + this.adgeList.get(i).get(j));
            }
        }
    }
    public static void main(String[] args)
    {
        int [][]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}
        };
        Graph g = 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

// Include header file
#include <iostream>
#include <vector>
#define N 5
using namespace std;
/*
    C++ Program
    Construct adjacency list using adjacency matrix
*/
class Graph
{
    public: int vertices;
    vector < vector < int > > adgeList;
    Graph(int matrix[N][N])
    {
        
        for (int i = 0; i < N; ++i)
        {
            this->adgeList.push_back(vector < int > ());
        }
        this->makeAdjacencyList(matrix);
    }
    void addEdge(int u, int v)
    {
        if (u < 0 || u >= N || 
            v < 0 || v >= N)
        {
            return;
        }
        // Add node edge
        this->adgeList.at(u).push_back(v);
    }
    void makeAdjacencyList(int matrix[N][N])
    {
        for (int i = 0; i < N; ++i)
        {
            for (int j = 0; j < N; ++j)
            {
                if (matrix[i][j] == 1)
                {
                    this->addEdge(i, j);
                }
            }
        }
    }
    // Display graph nodes and edges
    void printGraph()
    {
        cout << "\n Graph Adjacency List ";
        for (int i = 0; i < N; ++i)
        {
            cout << " \n [" << i << "] :";
            // iterate edges of i node
            for (int j = 0; j < this->adgeList.at(i).size(); j++)
            {
                if (j != 0)
                {
                    cout << " → ";
                }
                cout << " " << this->adgeList.at(i).at(j);
            }
        }
    }
};
int main()
{
    int matrix[N][N] = {
        {
            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
        }
    };
    Graph *g = new Graph(matrix);
    // Display graph element
    g->printGraph();
    return 0;
}

Output

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

// Include namespace system
using System;
using System.Collections.Generic;
/*
    Csharp Program
    Construct adjacency list using adjacency matrix
*/
public class Graph
{
    public int vertices;
    public List < List < int >> adgeList;
    public Graph(int[,] matrix)
    {
        this.vertices = matrix.GetLength(0);
        this.adgeList = new List < List < int >> (matrix.Length);
        for (int i = 0; i < this.vertices; ++i)
        {
            this.adgeList.Add(new List < int > ());
        }
        this.makeAdjacencyList(matrix);
    }
    public void addEdge(int u, int v)
    {
        if (u < 0 || u >= this.vertices || 
            v < 0 || v >= this.vertices)
        {
            return;
        }
        // Add node edge
        this.adgeList[u].Add(v);
    }
    public void makeAdjacencyList(int[,] matrix)
    {
        for (int i = 0; i < this.vertices; ++i)
        {
            for (int j = 0; j < this.vertices; ++j)
            {
                if (matrix[i,j] == 1)
                {
                    this.addEdge(i, j);
                }
            }
        }
    }
    // Display graph nodes and edges
    public void printGraph()
    {
        Console.Write("\n Graph Adjacency List ");
        for (int i = 0; i < this.vertices; ++i)
        {
            Console.Write(" \n [" + i + "] :");
            // iterate edges of i node
            for (int j = 0; j < this.adgeList[i].Count; j++)
            {
                if (j != 0)
                {
                    Console.Write(" → ");
                }
                Console.Write(" " + this.adgeList[i][j]);
            }
        }
    }
    public static void Main(String[] args)
    {
        int[,] 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
            }
        };
        Graph g = 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

package main
import "fmt"
/*
    Go Program
    Construct adjacency list using adjacency matrix
*/
type Graph struct {
    vertices int
    adgeList [][]int
}
func getGraph(matrix [][]int ) * Graph {
    var me *Graph = &Graph {}
    me.vertices = len(matrix)
    me.adgeList = make([][]int,me.vertices)
    for i := 0 ; i < me.vertices ; i++ {
        me.adgeList = append(me.adgeList, make([]int,0))
    }
    me.makeAdjacencyList(matrix)
    return me
}
func(this Graph) addEdge(u, v int) {
    if u < 0 || u >= this.vertices || 
       v < 0 || v >= this.vertices {
        return
    }
    // Add node edge
    this.adgeList[u] = append(this.adgeList[u], v)
}
func(this Graph) makeAdjacencyList(matrix[][] int) {
    for i := 0 ; i < this.vertices ; i++ {
        for j := 0 ; j < this.vertices ; j++ {
            if matrix[i][j] == 1 {
                this.addEdge(i, j)
            }
        }
    }
}
// Display graph nodes and edges
func(this Graph) printGraph() {
    fmt.Print("\n Graph Adjacency List ")
    for i := 0 ; i < this.vertices ; i++ {
        fmt.Print(" \n [", i, "] :")
        // iterate edges of i node
        for j := 0 ; j < len(this.adgeList[i]) ; j++ {
            if j != 0 {
                fmt.Print(" → ")
            }
            fmt.Print(" ", this.adgeList[i][j])
        }
    }
}
func main() {
    var matrix = [][] int {
            {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 * Graph = getGraph(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

<?php
/*
    Php Program
    Construct adjacency list using adjacency matrix
*/
class Graph
{
    public $vertices;
    public $adgeList;
    public  function __construct($matrix)
    {
        $this->vertices = count($matrix);
        $this->adgeList = array();
        for ($i = 0; $i < $this->vertices; ++$i)
        {
            $this->adgeList[] = array();
        }
        $this->makeAdjacencyList($matrix);
    }
    public  function addEdge($u, $v)
    {
        if ($u < 0 || $u >= $this->vertices || 
            $v < 0 || $v >= $this->vertices)
        {
            return;
        }
        // Add node edge
        $this->adgeList[$u][] = $v;
    }
    public  function makeAdjacencyList($matrix)
    {
        for ($i = 0; $i < $this->vertices; ++$i)
        {
            for ($j = 0; $j < $this->vertices; ++$j)
            {
                if ($matrix[$i][$j] == 1)
                {
                    $this->addEdge($i, $j);
                }
            }
        }
    }
    // Display graph nodes and edges
    public  function printGraph()
    {
        echo("\n Graph Adjacency List ");
        for ($i = 0; $i < $this->vertices; ++$i)
        {
            echo(" \n [".$i."] :");
            // iterate edges of i node
            for ($j = 0; $j < count($this->adgeList[$i]); $j++)
            {
                if ($j != 0)
                {
                    echo(" → ");
                }
                echo(" ".$this->adgeList[$i][$j]);
            }
        }
    }
}

function main()
{
    $matrix = 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)
    );
    $g = new Graph($matrix);
    // Display graph element
    $g->printGraph();
}
main();

Output

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

/*
    Node JS Program
    Construct adjacency list using adjacency matrix
*/
class Graph
{
    constructor(matrix)
    {
        this.vertices = matrix.length;
        this.adgeList = [];
        for (var i = 0; i < this.vertices; ++i)
        {
            this.adgeList.push([]);
        }
        this.makeAdjacencyList(matrix);
    }
    addEdge(u, v)
    {
        if (u < 0 || u >= this.vertices || 
            v < 0 || v >= this.vertices)
        {
            return;
        }
        // Add node edge
        this.adgeList[u].push(v);
    }
    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);
                }
            }
        }
    }
    // 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();
}
main();

Output

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

#    Python 3 Program
#    Construct adjacency list using adjacency matrix
class Graph :
    def __init__(self, matrix) :
        self.vertices = len(matrix)
        self.adgeList = []
        i = 0
        while (i < self.vertices) :
            self.adgeList.append([])
            i += 1
        
        self.makeAdjacencyList(matrix)
    
    def addEdge(self, u, v) :
        if (u < 0 or u >= self.vertices or v < 0 or v >= self.vertices) :
            return
        
        #  Add node edge
        self.adgeList[u].append(v)
    
    def makeAdjacencyList(self, matrix) :
        i = 0
        while (i < self.vertices) :
            j = 0
            while (j < self.vertices) :
                if (matrix[i][j] == 1) :
                    self.addEdge(i, j)
                
                j += 1
            
            i += 1
        
    
    #  Display graph nodes and edges
    def printGraph(self) :
        print("\n Graph Adjacency List ", end = "")
        i = 0
        while (i < self.vertices) :
            print(" \n [", i ,"] : ", end = "",sep = "")
            j = 0
            #  iterate edges of i node
            while (j < len(self.adgeList[i])) :
                if (j != 0) :
                    print(" → ", end = "",sep = "")
                
                print("", self.adgeList[i][j], end = "",sep = "")
                j += 1
            
            i += 1
        
    

def main() :
    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]
    ]
    g = Graph(matrix)
    #  Display graph element
    g.printGraph()

if __name__ == "__main__": main()

Output

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

#    Ruby Program
#    Construct adjacency list using adjacency matrix
class Graph 
    # Define the accessor and reader of class Graph
    attr_reader :vertices, :adgeList
    attr_accessor :vertices, :adgeList
    def initialize(matrix) 
        self.vertices = matrix.length
        self.adgeList = []
        i = 0
        while (i < self.vertices) 
            self.adgeList.push([])
            i += 1
        end

        self.makeAdjacencyList(matrix)
    end

    def addEdge(u, v) 
        if (u < 0 || u >= self.vertices || 
            v < 0 || v >= self.vertices) 
            return
        end

        #  Add node edge
        self.adgeList[u].push(v)
    end

    def makeAdjacencyList(matrix) 
        i = 0
        while (i < self.vertices) 
            j = 0
            while (j < self.vertices) 
                if (matrix[i][j] == 1) 
                    self.addEdge(i, j)
                end

                j += 1
            end

            i += 1
        end

    end

    #  Display graph nodes and edges
    def printGraph() 
        print("\n Graph Adjacency List ")
        i = 0
        while (i < self.vertices) 
            print(" \n [", i ,"] :")
            j = 0
            #  iterate edges of i node
            while (j < self.adgeList[i].length) 
                if (j != 0) 
                    print(" → ")
                end

                print(" ", self.adgeList[i][j])
                j += 1
            end

            i += 1
        end

    end

end

def main() 
    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]
    ]
    g = Graph.new(matrix)
    #  Display graph element
    g.printGraph()
end

main()

Output

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

import scala.collection.mutable._;
/*
    Scala Program
    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);
        
    }
    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;
    }
    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;
        }
    }
    // 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

import Foundation;
/*
    Swift 4 Program
    Construct adjacency list using adjacency matrix
*/
class Graph
{
    var vertices: Int;
    var adgeList: [[Int]];
    init(_ matrix: [[Int]])
    {
        self.vertices = matrix.count;
        self.adgeList = [[Int]]()
        var i: Int = 0;
        while (i < self.vertices)
        {
            self.adgeList.append([Int]());
            i += 1;
        }
        self.makeAdjacencyList(matrix);
    }
    func addEdge(_ u: Int, _ v: Int)
    {
        if (u < 0 || u >= self.vertices || v < 0 || v >= self.vertices)
        {
            return;
        }
        // Add node edge
        self.adgeList[u].append(v);
    }
    func makeAdjacencyList(_ matrix: [
        [Int]
    ])
    {
        var i: Int = 0;
        while (i < self.vertices)
        {
            var j: Int = 0;
            while (j < self.vertices)
            {
                if (matrix[i][j] == 1)
                {
                    self.addEdge(i, j);
                }
                j += 1;
            }
            i += 1;
        }
    }
    // Display graph nodes and edges
    func printGraph()
    {
        print("\n Graph Adjacency List ", terminator: "");
        var i: Int = 0;
        while (i < self.vertices)
        {
            print(" \n [", i ,"] : ",separator :"", terminator: "");
            var j: Int = 0;
            // iterate edges of i node
            while (j < self.adgeList[i].count)
            {
                if (j  != 0)
                {
                    print(" → ",separator :"", terminator: "");
                }
                print("", self.adgeList[i][j], terminator: "");
                j += 1;
            }
            i += 1;
        }
    }
}
func main()
{
    let matrix: [
        [Int]
    ] = [
        [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]
    ];
    let g: Graph = Graph(matrix);
    // Display graph element
    g.printGraph();
}
main();

Output

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

/*
    Kotlin Program
    Construct adjacency list using adjacency matrix
*/
class Graph
{
    var vertices: Int;
    var adgeList: MutableList < MutableList < Int >>  ;
    constructor(matrix: Array < Array < Int >> )
    {
        this.vertices = matrix.count();
        this.adgeList = mutableListOf();
        var i: Int = 0;
        while (i < this.vertices)
        {
            this.adgeList.add(mutableListOf < Int > ());
            i += 1;
        }
        this.makeAdjacencyList(matrix);
    }
    fun addEdge(u: Int, v: Int): Unit
    {
        if (u < 0 || u >= this.vertices || 
            v < 0 || v >= this.vertices)
        {
            return;
        }
        // Add node edge
        this.adgeList[u].add(v);
    }
    fun 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;
        }
    }
    // Display graph nodes and edges
    fun 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;
        }
    }
}
fun main(args: Array < String > ): Unit
{
    val matrix: Array < Array < Int >> = arrayOf(arrayOf(0, 1, 1, 0, 1), arrayOf(1, 0, 1, 0, 1), arrayOf(1, 1, 0, 1, 0), arrayOf(0, 1, 0, 0, 1), arrayOf(1, 1, 0, 1, 0));
    val g: Graph = 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

« Previous Next »

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.