Validate graph symmetric

Question

Given an undirected graph represented as an adjacency matrix, write a function to determine if the graph is symmetric. The function should return true if the graph is symmetric (i.e., for every edge from node A to node B, there is an edge from node B to node A), and false otherwise.

Codemia · Accepted Answer

To determine if the graph represented by the adjacency matrix is symmetric, we can recognize that the underlying pattern involves checking the equality of matrix entries. Specifically, for an undirected graph, the adjacency matrix should satisfy the property that `matrix[i][j]` should equal `matrix[j][i]` for all pairs of nodes $i$ and $j$. This indicates that if there is an edge from node A to node B, there must also be an edge from node B to node A, which is the definition of a symmetric graph.

We will iterate through the upper triangle of the adjacency matrix (excluding the diagonal) and check if each entry is equal to its corresponding entry in the lower triangle. This is a straightforward $O(n^2)$ approach since we need to check all pairs in the matrix. For example, given the adjacency matrix:

```
  0  1  0  0
  1  0  1  0
  0  1  0  1
  0  0  1  0
```

We need to check:
- `matrix[0][1]` vs `matrix[1][0]`
- `matrix[0][2]` vs `matrix[2][0]`
- `matrix[0][3]` vs `matrix[3][0]`
- `matrix[1][2]` vs `matrix[2][1]`
- `matrix[1][3]` vs `matrix[3][1]`
- `matrix[2][3]` vs `matrix[3][2]`

In this case, all pairs are equal, confirming the graph is symmetric.

Here is the Python solution for the problem:

```python
def is_symmetric(graph):
    n = len(graph)
    for i in range(n):
        for j in range(i + 1, n):  # Check only upper triangle
            if graph[i][j] != graph[j][i]:
                return False
    return True
```

This function takes an adjacency matrix `graph` as input and iterates through it to check symmetry.

The time complexity of this approach is $O(n^2)$ because we are iterating over half of the adjacency matrix (upper triangle). The space complexity is $O(1)$ since we are not using any additional data structures that scale with input size; we are only using a couple of integer variables for indexing.

1. **Empty Matrix**: If the graph is empty (`[]`), the function should return `True` since there are no edges to contradict symmetry.
2. **Single Node**: For a graph with one node (e.g., `[[0]]`), it should return `True` as there are no edges.
3. **Disconnected Graph**: Even if the graph is disconnected, as long as the symmetry condition is satisfied, the function should return `True`. For instance, `[[0, 0], [0, 0]]` is symmetric.
4. **Asymmetric Graph**: Any graph where `graph[i][j]` does not equal `graph[j][i]` should yield `False`, such as `[[0, 1], [0, 0]]`.

Validate graph symmetric

JPMorgan

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

JPMorgan 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