Validate graph symmetric

Question

Given an undirected graph represented as an adjacency list, write a function to determine if the graph is symmetric, meaning that for every edge (u, v), there exists a corresponding edge (v, u). The function should return a boolean value: true if the graph is symmetric, and false otherwise.

Codemia · Accepted Answer

To determine if a graph is symmetric, we need to verify that for every edge (u, v) in the adjacency list, there is a corresponding edge (v, u). This problem can be approached using a graph traversal method like Depth-First Search (DFS) or Breadth-First Search (BFS). In this case, we will use a BFS approach since we can systematically explore all neighbors of a node while keeping track of visited nodes. The BFS pattern is particularly effective here because it allows us to check each edge's symmetry in a level-order manner.

1. **Initialize**: Create a set to keep track of visited nodes. 
2. **Iterate Over Each Node**: For each node in the graph, if it hasn't been visited, perform a BFS. 
3. **BFS Implementation**: During BFS, for each current node, check its neighbors: 
   - For each neighbor v of u, check if u is also a neighbor of v. 
   - If not, return False immediately. 
4. **Mark Nodes as Visited**: After checking all neighbors, mark the current node as visited. 
5. **Return True**: If all nodes are processed without finding any asymmetrical edges, return True.

**Example**: For a graph represented by the adjacency list `{0: [1, 2], 1: [0], 2: [0]}`, the BFS from node 0 would check neighbors 1 and 2. Both edges (0, 1) and (1, 0) are confirmed, and similarly for (0, 2) and (2, 0). Since all edges are symmetric, the function should return True.

Here is a Python implementation of the solution:
```python
from collections import deque

def is_symmetric_graph(graph):
    visited = set()
    
    for node in graph:
        if node not in visited:
            queue = deque([node])
            visited.add(node)
            while queue:
                current = queue.popleft()
                for neighbor in graph[current]:
                    # Check if the reverse edge exists
                    if current not in graph[neighbor]:
                        return False
                    if neighbor not in visited:
                        visited.add(neighbor)
                        queue.append(neighbor)
    return True
```
This code uses BFS to ensure that all edges are symmetric.

The time complexity of this approach is O(V + E), where V is the number of vertices and E is the number of edges in the graph. This is because we explore each vertex and each edge exactly once. The space complexity is also O(V) due to the storage required for the visited set and the BFS queue. Given that the graph can be represented sparsely or densely, this complexity is efficient for typical graph sizes.

1. **Empty Graph**: An empty graph should return True, as there are no edges to violate symmetry. 
2. **Single Node**: A graph with a single node and no edges should also return True. 
3. **Disconnected Graph**: Ensure the algorithm works with disconnected components. Each component should be checked independently for symmetry. 
4. **Non-Symmetric Edges**: Test with a graph that has non-symmetric edges, e.g., `{0: [1], 1: []}`, which should return False. 
5. **Self-Loops**: A graph with self-loops should be considered symmetric if they exist on both ends, e.g., `{0: [0]}` should return True.

Validate graph symmetric

Twitter/X

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

Twitter/X 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