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:

``````A: [B]
B: [A, C]
C: [B, D]
D: [C]
``````

## What is an Adjacency Matrix?

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.

## Example Graph Used For Conversion

For the examples below, a graph with the following nodes/vertices and edges is considered:

``````vertices = ['A', 'B', 'C', 'D', 'E', 'F']

edges = [['A','B'], ['A','C'], ['B','C'], ['B','D'], ['C','E'], ['C','F']]
``````

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]]
``````

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).

``````
# Get the number of nodes in the graph

# 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
# Iterate through the neighbors of the current node
for destination in neighbors:
# Mark the edge between source and destination in adjacency matrix

adj_list = [[1, 2], [0, 2, 3], [0, 1, 4, 5], [1], [2], [2]]
print(f"{vertex} : {neighbors}")
for edge_status in row:
print(edge_status, end=' ')
print()
``````

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`.

``````
# Get the number of nodes in the graph

# 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

[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]
]
for edge_status in row:
print(edge_status, end=' ')
print()