Transform matrix to adjacency list

Question

Given a matrix representation of a graph, convert it into an adjacency list format. The input will be a 2D array where each element indicates the presence of an edge between nodes, and the output should be a list of lists where each sublist contains the neighbors of the corresponding node. Ensure that the adjacency list accurately reflects the connections defined by the matrix.

Codemia · Accepted Answer

The problem requires converting a matrix representation of a graph into an adjacency list. Each cell in the input matrix indicates whether there is an edge between two nodes (1 for an edge, 0 for no edge). The adjacency list will be a list where each index corresponds to a node, and the value at that index is a list of neighboring nodes. This problem can be solved using a simple iteration through the matrix. It is a straightforward mapping task, which makes it suitable for a direct index-based approach.

1. Initialize an empty list called `adjacency_list` to store the neighbors for each node.
2. Loop through each row of the matrix. The index of the row represents the current node.
3. For each element in the row, check if the value is 1 (indicating an edge).
4. If an edge exists (matrix[i][j] == 1), append the index of the column `j` to the `adjacency_list` at index `i`.
5. Continue this process for all nodes in the matrix.

**Example:** Given the matrix:
```
[[0, 1, 0],
 [1, 0, 1],
 [0, 1, 0]]
```
The adjacency list will be:
```
[[1],
 [0, 2],
 [1]]
```
This indicates that node 0 is connected to node 1, node 1 is connected to nodes 0 and 2, and node 2 is connected to node 1.

```python
def matrix_to_adjacency_list(matrix):
    adjacency_list = []
    for i in range(len(matrix)):
        neighbors = []
        for j in range(len(matrix[i])):
            if matrix[i][j] == 1:
                neighbors.append(j)
        adjacency_list.append(neighbors)
    return adjacency_list
```
**Explanation:** This function initializes an empty list, iterates through each node, checks for edges, and constructs the adjacency list accordingly.

The time complexity of this approach is O(V^2), where V is the number of vertices (or nodes) in the graph. This is because we need to iterate through each element in the matrix, which has V rows and V columns. The space complexity is O(V) for the adjacency list, as in the worst case, each node could connect to every other node. Given the constraints, this is efficient enough.

1. **Empty Matrix:** If the input is an empty matrix `[]`, the output should also be an empty list `[]`.
2. **Single Node:** For a matrix like `[[0]]`, the output should be `[[ ]]`, indicating that the lone node has no connections.
3. **Disconnected Nodes:** If the matrix is `[[0, 0], [0, 0]]`, the output should be `[[ ], [ ]]`, confirming that there are no edges between nodes.

Transform matrix to adjacency list

Zscaler

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Zscaler Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string