Adjacency List to Adjacency Matrix Editorial

Practice Problem Link: Adjacency List to Adjacency Matrix

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

Problem Statement

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

You have a graph with n nodes indexed from 0 to n-1. You are also given the adjacency list for each node.

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

Approach

An Adjacency matrix is a way of representing graphs, where matrx[i][j] is 1 if there is an edge between i and j, and 0 otherwise.

• Create a matrix of size n * n and initialize it with zero.
• Traverse the given adjacency list and for every value j in a row i change matrix[i][j] to 1.

Analysis

• Time Complexity: O(V + E)
• Auxiliary Space Complexity: O(1)

Where V denotes the number of nodes and E denotes the number of edges.

Implementation

C++

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

Java

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