Shortest Distance in an Unweighted Adjacency-Matrix Graph

Question

The question asks the candidate to find the shortest distance between two nodes in an unweighted graph represented by an adjacency matrix.

Codemia · Accepted Answer

To find the shortest distance in an unweighted graph, we can utilize the Breadth-First Search (BFS) algorithm. BFS is ideal for this scenario because it explores all neighbors at the present depth prior to moving on to nodes at the next depth level, ensuring that the shortest path is found first.

1. Initialize a queue to keep track of nodes to explore.
2. Create a distance array to store the shortest distance from the source node to each node, initialized to a large value (infinity).
3. Set the distance to the source node to 0.
4. While the queue is not empty, dequeue a node, explore its neighbors, and update their distances if a shorter path is found.
5. Return the distance to the target node once it is reached.

The time complexity of this BFS approach is O(V + E), where V is the number of vertices and E is the number of edges. The space complexity is O(V) due to the storage of the distance array and the queue.

```python
from collections import deque

def shortest_distance(adj_matrix, start, target):
    n = len(adj_matrix)
    distances = [float('inf')] * n
    distances[start] = 0
    queue = deque([start])

while queue:
        node = queue.popleft()
        for neighbor in range(n):
            if adj_matrix[node][neighbor] == 1 and distances[neighbor] == float('inf'):
                distances[neighbor] = distances[node] + 1
                queue.append(neighbor)
                if neighbor == target:
                    return distances[neighbor]
    return -1  # return -1 if target is not reachable
```

Interviewers will look for clarity in your explanation of the BFS algorithm and its suitability for this problem. They will also assess your coding style, efficiency, and how well you handle edge cases. A strong candidate will demonstrate not only technical proficiency but also the ability to communicate their thought process clearly.

Shortest Distance in an Unweighted Adjacency-Matrix Graph

BCG

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Approach

Algorithm

Submit Your Answer

BCG Forward Deploy 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