Adjacency Matrix to Adjacency List Editorial

Practice Problem Link: Adjacency Matrix to Adjacency List

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given the nodes and adjacency matrix of a graph, calculate the adjacency list for it.

You have a graph with n nodes indexed from 0 to n-1. You also have the adjacency matrix where each cell denotes whether two nodes are connected.

You have to return the adjacency list for the given graph.

Approach

An adjacency list is a way of representing graphs, where each node corresponds to a list of nodes, to which it is connected.

• Create a 2-D array having n rows.
• Traverse the given matrix and if matrix[i][j] = 1 where i is the row number and j is the column number then add j in the ith row of the 2-D array.

Analysis

• Time Complexity: O(n2)
• Auxiliary Space Complexity: O(1)

Implementation

C++

vector<vector<int>> matrixToAdjList(int n, vector<vector<int>> matrix) {
    vector<vector<int>> adjList (n);
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) {
			if(matrix[i][j] == 1) {
				adjList[i].push_back(j);
			}
		}
	}
	return adjList;
}

Java

class Solution {
    ArrayList<Integer>[] matrixToAdjList(int n, int[][] matrix) {
        ArrayList<Integer>[] adjList = new ArrayList [n];
		for (int i = 0; i < n; i++) {
			adjList[i] = new ArrayList<Integer>();
		}
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				if(matrix[i][j] == 1) {
					adjList[i].add(j);
				}
			}
		}
		return adjList;
    }
}