Convert Adjacency Matrix to Adjacency List representation of Graph
Prerequisite: Graph and its representations
Given a adjacency matrix representation of a Graph. The task is to convert the given Adjacency Matrix to Adjacency List representation.
Examples:
Input: arr[][] = [ [0, 0, 1], [0, 0, 1], [1, 1, 0] ]
Output: The adjacency list is:
0 -> 2
1 -> 2
2 -> 0 -> 1
Input: arr[][] = [ [0, 1, 0, 0, 1], [1, 0, 1, 1, 1], [0, 1, 0, 1, 0], [0, 1, 1, 0, 1], [1, 1, 0, 1, 0] ]
Output: The adjacency list is:
0 -> 1 -> 4
1 -> 0 -> 2 -> 3 -> 4
2 -> 1 -> 3
3 -> 1 -> 2 -> 4
4 -> 0 -> 1 -> 3
Adjacency Matrix: Adjacency Matrix is a 2D array of size V x V where V is the number of vertices in a graph. Let the 2D array be adj[][], a slot adj[i][j] = 1 indicates that there is an edge from vertex i to vertex j.
Adjacency List: An array of lists is used. The size of the array is equal to the number of vertices. Let the array be array[]. An entry array[i] represents the list of vertices adjacent to the ith vertex.
To convert an adjacency matrix to the adjacency list. Create an array of lists and traverse the adjacency matrix. If for any cell (i, j) in the matrix “mat[i][j] != 0“, it means there is an edge from i to j, so insert j in the list at i-th position in the array of lists.
Below is the implementation of the above approach:
C++
#include<bits/stdc++.h> using namespace std; // CPP program to convert Adjacency matrix // representation to Adjacency List // converts from adjacency matrix to adjacency list vector<vector< int >> convert( vector<vector< int >> a) { vector<vector< int >> adjList(a.size()); for ( int i = 0; i < a.size(); i++) { for ( int j = 0; j < a[i].size(); j++) { if (a[i][j] != 0) { adjList[i].push_back(j); } } } return adjList; } // Driver code int main() { vector<vector< int >> a; vector< int > p({0, 0, 1}); vector< int > q({0, 0, 1}); vector< int > r({1, 1, 0}); // adjacency matrix a.push_back(p); a.push_back(q); a.push_back(r); vector<vector< int >> AdjList = convert(a); cout<< "Adjacency List:" <<endl; // print the adjacency list for ( int i = 0; i < AdjList.size(); i++) { cout << i; for ( int j = 0; j < AdjList[i].size(); j++) { if (j == AdjList[i].size() - 1) { cout << " -> " << AdjList[i][j] << endl; break ; } else cout << " -> " << AdjList[i][j]; } } } // This code is contributed by Surendra_Gangwar // This code is modified by Susobhan Akhuli |
Java
// Java program to convert adjacency // matrix representation to // adjacency list import java.util.*; public class GFG { // Function to convert adjacency // list to adjacency matrix static ArrayList<ArrayList<Integer>> convert( int [][] a) { // no of vertices int l = a[ 0 ].length; ArrayList<ArrayList<Integer>> adjListArray = new ArrayList<ArrayList<Integer>>(l); // Create a new list for each // vertex such that adjacent // nodes can be stored for ( int i = 0 ; i < l; i++) { adjListArray.add( new ArrayList<Integer>()); } int i, j; for (i = 0 ; i < a[ 0 ].length; i++) { for (j = 0 ; j < a.length; j++) { if (a[i][j] != 0 ) { adjListArray.get(i).add(j); } } } return adjListArray; } // Function to print the adjacency list static void printArrayList(ArrayList<ArrayList<Integer>> adjListArray) { // Print the adjacency list for ( int v = 0 ; v < adjListArray.size(); v++) { System.out.print(v); for (Integer u : adjListArray.get(v)) { System.out.print( " -> " + u); } System.out.println(); } } // Driver Code public static void main(String[] args) { // Given Adjacency Matrix int [][] a = { { 0 , 0 , 1 }, { 0 , 0 , 1 }, { 1 , 1 , 0 } }; // function to convert adjacency // list to adjacency matrix ArrayList<ArrayList<Integer>> adjListArray = convert(a); System.out.println( "Adjacency List: " ); printArrayList(adjListArray); } } // This code is modified by Susobhan Akhuli |
Python3
# Python 3 program to convert Adjacency matrix # representation to Adjacency List from collections import defaultdict # converts from adjacency matrix to adjacency list def convert(a): adjList = defaultdict( list ) for i in range ( len (a)): for j in range ( len (a[i])): if a[i][j] ! = 0 : adjList[i].append(j) return adjList # driver code a = [[ 0 , 0 , 1 ], [ 0 , 0 , 1 ], [ 1 , 1 , 0 ]] # adjacency matrix AdjList = convert(a) print ( "Adjacency List:" ) # print the adjacency list for i in AdjList: print (i, end = "") for j in AdjList[i]: print ( " -> {}" . format (j), end = "") print () # This code is contributed by Muskan Kalra. # This code is modified by Susobhan Akhuli |
C#
// C# program to convert adjacency // matrix representation to // adjacency list using System; using System.Collections.Generic; class GFG { // Function to convert adjacency // list to adjacency matrix static List<List< int >> convert( int [,] a) { // no of vertices int l = a.GetLength(0); List<List< int >> adjListArray = new List<List< int >>(l); int i, j; // Create a new list for each // vertex such that adjacent // nodes can be stored for (i = 0; i < l; i++) { adjListArray.Add( new List< int >()); } for (i = 0; i < a.GetLength(0); i++) { for (j = 0; j < a.GetLength(1); j++) { if (a[i,j] != 0) { adjListArray[i].Add(j); } } } return adjListArray; } // Function to print the adjacency list static void printList(List<List< int >> adjListArray) { // Print the adjacency list for ( int v = 0; v < adjListArray.Count; v++) { Console.Write(v); foreach ( int u in adjListArray[v]) { Console.Write( " -> " + u); } Console.WriteLine(); } } // Driver Code public static void Main(String[] args) { // Given Adjacency Matrix int [,] a = { { 0, 0, 1 }, { 0, 0, 1 }, { 1, 1, 0 } }; // function to convert adjacency // list to adjacency matrix List<List< int >> adjListArray = convert(a); Console.WriteLine( "Adjacency List: " ); printList(adjListArray); } } // This code is contributed by 29AjayKumar // This code is modified by Susobhan Akhuli |
Javascript
// JavaScript program to convert Adjacency matrix // representation to Adjacency List function convert(a) { let adjList = new Array(a.length); for (let i = 0; i < a.length; i++) { for (let j = 0; j < a[i].length; j++) { if (a[i][j] != 0) { if (!adjList[i]) { adjList[i] = []; } adjList[i].push(j); } } } return adjList; } // Driver code let a = [[0, 0, 1], [0, 0, 1], [1, 1, 0]]; // adjacency matrix let AdjList = convert(a); console.log( "Adjacency List:" ); // print the adjacency list for (let i = 0; i < AdjList.length; i++) { let output = i; for (let j = 0; j < AdjList[i].length; j++) { if (j === AdjList[i].length - 1) { output += " -> " + AdjList[i][j]; break ; } else { output += " -> " + AdjList[i][j]; } } console.log(output); } // This code is modified by Susobhan Akhuli |
Adjacency List: 0 -> 2 1 -> 2 2 -> 0 -> 1
Time Complexity: O(N2).
Auxiliary Space: O(N2).