Validate graph complete

Question

Given an undirected graph represented as an adjacency list, write a function to determine if the graph is complete. A complete graph is one in which every pair of distinct vertices is connected by a unique edge. The function should return a boolean value indicating whether the graph is complete or not.

Codemia · Accepted Answer

To determine if an undirected graph is complete, we need to ensure that every pair of distinct vertices has a unique edge connecting them. This problem can be approached using the properties of a complete graph, which states that for a graph with `n` vertices, there should be exactly `n * (n - 1) / 2` edges. We can utilize an adjacency list representation of the graph to both count the number of vertices and edges efficiently. The two-pointer technique isn't applicable here since we're not looking for subarrays or pairs in a linear structure, but rather evaluating connections between nodes in a graph.

1. **Count Vertices**: Iterate through the adjacency list to determine the number of unique vertices `n`.  
2. **Count Edges**: For each vertex, check the length of its adjacency list and sum these lengths. Since the graph is undirected, each edge is counted twice, so we divide the total by 2.  
3. **Check Completeness**: A complete graph with `n` vertices should have `n * (n - 1) / 2` edges. Compare the counted edges with this expected value.  
**Example**: For a graph with vertices 0, 1, 2 represented as:  
- 0: [1, 2]  
- 1: [0, 2]  
- 2: [0, 1]  
This graph has 3 vertices and 3 edges, satisfying the complete graph condition as `3 * (3 - 1) / 2 = 3`.

Here is the Python code for the solution:  
```python  
def is_complete_graph(adj_list):  
    n = len(adj_list)  
    edge_count = 0  
    for neighbors in adj_list:  
        edge_count += len(neighbors)  
    edge_count //= 2  
    expected_edges = n * (n - 1) // 2  
    return edge_count == expected_edges  
```  
This function first counts the number of edges by summing the lengths of each vertex's neighbor list and then checks if that count matches the expected number of edges in a complete graph.

The time complexity of this solution is O(n + e), where `n` is the number of vertices and `e` is the number of edges. This arises because we traverse the adjacency list once to count the edges. The space complexity is O(n) for storing the adjacency list itself. Given that we're only iterating through the graph once and performing constant-time operations, this is optimal for the problem constraints.

1. **Empty Graph**: An empty graph (no vertices) should return `True` since it vacuously satisfies the condition of completeness.  
2. **Single Vertex**: A graph with a single vertex (e.g., {0: []}) should also return `True` as there are no pairs of vertices to be disconnected.  
3. **Disconnected Graph**: If any vertex has an adjacency list that doesn't connect it to all other vertices, the function should return `False`.  
4. **Duplicate Edges**: If there are duplicate edges in the adjacency list representation, we need to ensure they are counted only once. The adjacency list should be structured to avoid duplicates.

Validate graph complete

Grafana Labs

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

Grafana Labs 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