Converting between Adjacency List and Adjacency Matrix Graph Representation
In this article, we will explore on how to convert from adjacency list representation of a graph to adjacency matrix representation and vice versa.
What is an Adjacency List?
An adjacency list is a way of representing a graph, where each node is associated with a list of its neighboring nodes (the nodes it is connected to). This representation is often more efficient for sparse graphs, where each node has only a few connections.
For the same example graph above, the adjacency list would be:
An Adjacency Matrix is another way of representing a graph. It is a square matrix where the rows and columns represent the nodes of the graph, and the values in the matrix indicate whether there is an edge between the corresponding nodes.
For example, if we have the same graph as before, with nodes A, B, C, and D, and the edges (A, B), (B, C), and (C, D), the adjacency matrix would look like this:
A B C D
A 0 1 0 0
B 1 0 1 0
C 0 1 0 1
D 0 0 1 0
In this matrix, a value of 1 indicates that there is an edge between the corresponding row and column nodes, and a value of 0 indicates that there is no edge. This representation is more suitable for dense graphs where the number of edges are more.
In programmatic representation of a graph, each node or vertex is typically assigned a number between 0 and N-1, where N is the total number of nodes in the graph. This numbering is efficient in terms of storage and also allows us to use an array to represent the adjacency list or matrix, rather than a dictionary or hash table. This approach is more efficient because accessing elements in an array using the node ID/number as index is generally faster than accessing elements in a hash table or dictionary. Below is how the vertices and edges look like after optimizing the representation:
A B C D E F
vertices = [0, 1, 2, 3, 4, 5]
edges = [[0,1], [0,2], [1,2], [1,3], [2,4], [2,5]]
Converting from Adjacency List to Adjacency Matrix
To convert from an adjacency list to an adjacency matrix, we first initialize an N x N matrix with all elements set to 0, where N is the number of nodes. Then, we iterate through each node and its list of neighbors in the adjacency list. For each neighbor, we set the corresponding elements in the matrix to 1 (or the weight of the edge, if applicable).
# Function to convert Adjacency List to Adjacency Matrix
def convert_to_adjacency_matrix(adjacency_list):
# Get the number of nodes in the graph
num_vertices = len(adjacency_list)
# Initialize the adjacency matrix with all zeros
adj_mat = [[0 for _ in range(num_vertices)] for _ in range(num_vertices)]
# Iterate through the adjacency list
for source, neighbors in enumerate(adjacency_list):
# Iterate through the neighbors of the current node
for destination in neighbors:
# Mark the edge between source and destination in adjacency matrix
adj_mat[source][destination] = 1
# Return the adjacency matrix
return adj_mat
adj_list = [[1, 2], [0, 2, 3], [0, 1, 4, 5], [1], [2], [2]]
adj_mat = convert_to_adjacency_matrix(adj_list)
print("For the following Adjacency list")
for vertex, neighbors in enumerate(adj_list):
print(f"{vertex} : {neighbors}")
print("Below is the Adjacency Matrix")
for row in adj_mat:
for edge_status in row:
print(edge_status, end=' ')
print()
#include <iostream>
#include <vector>
// Function to convert Adjacency List to Adjacency Matrix
std::vector<std::vector<bool>> convert_to_adjacency_matrix(const std::vector<std::vector<int>>& adjacency_list) {
// Get the number of nodes in the graph
int num_vertices = adjacency_list.size();
// Initialize the adjacency matrix with all zeros
std::vector<std::vector<bool>> adj_mat(num_vertices, std::vector<bool>(num_vertices, false));
// Iterate through the adjacency list
for (int source = 0; source < num_vertices; source++) {
// Iterate through the neighbors of the current node
for (int destination : adjacency_list[source]) {
// Mark the edge between source and destination in adjacency matrix
adj_mat[source][destination] = true;
}
}
// Return the adjacency matrix
return adj_mat;
}
int main() {
std::vector<std::vector<int>> adj_list = {{1, 2}, {0, 2, 3}, {0, 1, 4, 5}, {1}, {2}, {2}};
std::vector<std::vector<bool>> adj_mat = convert_to_adjacency_matrix(adj_list);
std::cout << "For the following Adjacency list" << std::endl;
for (int vertex = 0; vertex < adj_list.size(); vertex++) {
std::cout << vertex << " : ";
for (int neighbor : adj_list[vertex]) {
std::cout << neighbor << " ";
}
std::cout << std::endl;
}
std::cout << "Below is the Adjacency Matrix" << std::endl;
for (const auto& row : adj_mat) {
for (bool edge_status : row) {
std::cout << edge_status << " ";
}
std::cout << std::endl;
}
return 0;
}
// Function to convert Adjacency List to Adjacency Matrix
function convertToAdjacencyMatrix(adjacencyList) {
// Get the number of nodes in the graph
const numVertices = adjacencyList.length;
// Initialize the adjacency matrix with all zeros
const adjMat = Array.from({ length: numVertices }, () => Array(numVertices).fill(0));
// Iterate through the adjacency list
for (let source = 0; source < numVertices; source++) {
// Iterate through the neighbors of the current node
for (const destination of adjacencyList[source]) {
// Mark the edge between source and destination in adjacency matrix
adjMat[source][destination] = 1;
}
}
// Return the adjacency matrix
return adjMat;
}
const adjList = [[1, 2], [0, 2, 3], [0, 1, 4, 5], [1], [2], [2]];
const adjMat = convertToAdjacencyMatrix(adjList);
console.log("For the following Adjacency list");
for (let vertex = 0; vertex < adjList.length; vertex++) {
console.log(`${vertex} : ${adjList[vertex]}`);
}
console.log("Below is the Adjacency Matrix");
for (const row of adjMat) {
console.log(row.join(" "));
}
import java.util.List;
import java.util.ArrayList;
public class Main {
// Function to convert Adjacency List to Adjacency Matrix
public static int[][] convertToAdjacencyMatrix(List<List<Integer>> adjacencyList) {
// Get the number of nodes in the graph
int numVertices = adjacencyList.size();
// Initialize the adjacency matrix with all zeros
int[][] adjMat = new int[numVertices][numVertices];
// Iterate through the adjacency list
for (int source = 0; source < numVertices; source++) {
// Iterate through the neighbors of the current node
for (int destination : adjacencyList.get(source)) {
// Mark the edge between source and destination in adjacency matrix
adjMat[source][destination] = 1;
}
}
// Return the adjacency matrix
return adjMat;
}
public static void main(String[] args) {
// Example adjacency list
List<List<Integer>> adjList = new ArrayList<>();
adjList.add(new ArrayList<>());
adjList.get(0).add(1);
adjList.get(0).add(2);
adjList.add(new ArrayList<>());
adjList.get(1).add(0);
adjList.get(1).add(2);
adjList.get(1).add(3);
adjList.add(new ArrayList<>());
adjList.get(2).add(0);
adjList.get(2).add(1);
adjList.get(2).add(4);
adjList.get(2).add(5);
adjList.add(new ArrayList<>());
adjList.get(3).add(1);
adjList.add(new ArrayList<>());
adjList.add(new ArrayList<>());
adjList.get(5).add(2);
// Convert adjacency list to adjacency matrix
int[][] adjMat = convertToAdjacencyMatrix(adjList);
// Print the adjacency list
System.out.println("For the following Adjacency list");
for (int vertex = 0; vertex < adjList.size(); vertex++) {
System.out.print(vertex + " : ");
for (int neighbor : adjList.get(vertex)) {
System.out.print(neighbor + " ");
}
System.out.println();
}
// Print the adjacency matrix
System.out.println("Below is the Adjacency Matrix");
for (int[] row : adjMat) {
for (int edgeStatus : row) {
System.out.print(edgeStatus + " ");
}
System.out.println();
}
}
}
Converting from Adjacency Matrix to Adjacency List
To convert from an adjacency matrix to an adjacency list, we initialize an array of size N with an empty list of neighbors for each node. Then, we iterate through each element in the N x N matrix. For each non-zero element at position [i, j], we add node j to the adjacency list of node i. In the code below, source variable refers to index i and destination variable refers to index j.
# Function to convert Adjacency Matrix to Adjacency List
def convert_to_adjacency_list(adjacency_matrix):
# Get the number of nodes in the graph
num_vertices = len(adjacency_matrix)
# Initialize an empty list of size "num_vertices"
# To store the adjacency list of each vertex
adjacency_list = [[] for _ in range(num_vertices)]
# Iterate through each row in the adjacency matrix
for source in range(num_vertices):
# Iterate through each column in the current row
for destination in range(num_vertices):
# If the value in the adjacency matrix is 1
# It means there is a path from source node to destination node
# Add destination node to the list of neighbors from source node
if adjacency_matrix[source][destination] == 1:
adjacency_list[source].append(destination)
# Return the adjacency list
return adjacency_list
adj_mat = [
[0, 1, 1, 0, 0, 0],
[1, 0, 1, 1, 0, 0],
[1, 1, 0, 0, 1, 1],
[0, 1, 0, 0, 0, 0],
[0, 0, 1, 0, 0, 0],
[0, 0, 1, 0, 0, 0]
]
adj_list = convert_to_adjacency_list(adj_mat)
print("For the following Adjacency Matrix")
for row in adj_mat:
for edge_status in row:
print(edge_status, end=' ')
print()
print("Below is the Adjacency list")
for vertex, neighbors in enumerate(adj_list):
print(f"{vertex} : {neighbors}")
#include <iostream>
#include <vector>
// Function to convert Adjacency Matrix to Adjacency List
std::vector<std::vector<int>> convert_to_adjacency_list(const std::vector<std::vector<bool>>& adjacency_matrix) {
// Get the number of nodes in the graph
int num_vertices = adjacency_matrix.size();
// Initialize an empty list of size "num_vertices"
// To store the adjacency list of each vertex
std::vector<std::vector<int>> adjacency_list(num_vertices);
// Iterate through each row in the adjacency matrix
for (int source = 0; source < num_vertices; source++) {
// Iterate through each column in the current row
for (int destination = 0; destination < num_vertices; destination++) {
// If the value in the adjacency matrix is 1
// It means there is a path from source node to destination node
// Add destination node to the list of neighbors from source node
if (adjacency_matrix[source][destination]) {
adjacency_list[source].push_back(destination);
}
}
}
// Return the adjacency list
return adjacency_list;
}
int main() {
// Example Adjacency Matrix
std::vector<std::vector<bool>> adj_mat = {
{0, 1, 1, 0, 0, 0},
{1, 0, 1, 1, 0, 0},
{1, 1, 0, 0, 1, 1},
{0, 1, 0, 0, 0, 0},
{0, 0, 1, 0, 0, 0},
{0, 0, 1, 0, 0, 0}
};
// Convert Adjacency Matrix to Adjacency List
std::vector<std::vector<int>> adj_list = convert_to_adjacency_list(adj_mat);
// Print the Adjacency Matrix
std::cout << "For the following Adjacency Matrix" << std::endl;
for (const auto& row : adj_mat) {
for (bool edge_status : row) {
std::cout << edge_status << " ";
}
std::cout << std::endl;
}
// Print the Adjacency List
std::cout << "Below is the Adjacency list" << std::endl;
for (int vertex = 0; vertex < adj_list.size(); vertex++) {
std::cout << vertex << " : ";
for (int neighbor : adj_list[vertex]) {
std::cout << neighbor << " ";
}
std::cout << std::endl;
}
return 0;
}
// Function to convert Adjacency Matrix to Adjacency List
function convertToAdjacencyList(adjacencyMatrix) {
// Get the number of nodes in the graph
const numVertices = adjacencyMatrix.length;
// Initialize an empty list of size "numVertices"
// To store the adjacency list of each vertex
const adjacencyList = new Array(numVertices).fill(0).map(() => []);
// Iterate through each row in the adjacency matrix
for (let source = 0; source < adjacencyMatrix.length; source++) {
// Iterate through each column in the current row
for (let destination = 0; destination < adjacencyMatrix[source].length; destination++) {
// If the value in the adjacency matrix is 1
// It means there is a path from source node to destination node
// Add destination node to the list of neighbors from source node
if (adjacencyMatrix[source][destination] === 1) {
adjacencyList[source].push(destination);
}
}
}
// Return the adjacency list
return adjacencyList;
}
const adjMat = [
[0, 1, 1, 0, 0, 0],
[1, 0, 1, 1, 0, 0],
[1, 1, 0, 0, 1, 1],
[0, 1, 0, 0, 0, 0],
[0, 0, 1, 0, 0, 0],
[0, 0, 1, 0, 0, 0]
];
const adjList = convertToAdjacencyList(adjMat);
console.log("For the following Adjacency Matrix");
for (const row of adjMat) {
console.log(row.join(" "));
}
console.log("Below is the Adjacency list");
for (let vertex = 0; vertex < adjList.length; vertex++) {
console.log(`${vertex} : ${adjList[vertex]}`);
}
import java.util.ArrayList;
import java.util.List;
public class Main {
// Function to convert Adjacency Matrix to Adjacency List
public static List<List<Integer>> convertToAdjacencyList(int[][] adjacencyMatrix) {
// Get the number of nodes in the graph
int numVertices = adjacencyMatrix.length;
// Initialize an empty list of size "numVertices"
// To store the adjacency list of each vertex
List<List<Integer>> adjacencyList = new ArrayList<>();
for (int i = 0; i < numVertices; i++) {
adjacencyList.add(new ArrayList<>());
}
// Iterate through each row in the adjacency matrix
for (int source = 0; source < adjacencyMatrix.length; source++) {
// Iterate through each column in the current row
for (int destination = 0; destination < adjacencyMatrix[source].length; destination++) {
// If the value in the adjacency matrix is 1
// It means there is a path from source node to destination node
// Add destination node to the list of neighbors from source node
if (adjacencyMatrix[source][destination] == 1) {
adjacencyList.get(source).add(destination);
}
}
}
// Return the adjacency list
return adjacencyList;
}
public static void main(String[] args) {
int[][] adjMat = {
{0, 1, 1, 0, 0, 0},
{1, 0, 1, 1, 0, 0},
{1, 1, 0, 0, 1, 1},
{0, 1, 0, 0, 0, 0},
{0, 0, 1, 0, 0, 0},
{0, 0, 1, 0, 0, 0}
};
List<List<Integer>> adjList = convertToAdjacencyList(adjMat);
System.out.println("For the following Adjacency Matrix");
for (int[] row : adjMat) {
for (int edgeStatus : row) {
System.out.print(edgeStatus + " ");
}
System.out.println();
}
System.out.println("Below is the Adjacency list");
for (int vertex = 0; vertex < adjList.size(); vertex++) {
System.out.println(vertex + " : " + adjList.get(vertex));
}
}
}