Topological Sort on graph

Question

Given a directed acyclic graph (DAG), implement a function to perform a topological sort and return a linear ordering of its vertices such that for every directed edge from vertex A to vertex B, vertex A comes before vertex B in the ordering. The input will be represented as an adjacency list, and the output should be a list of vertices in topologically sorted order.

Codemia · Accepted Answer

To solve the problem of topological sorting for a directed acyclic graph (DAG), we can utilize the Kahn's algorithm or Depth-First Search (DFS) approach. Here, I'll focus on Kahn's algorithm because it effectively uses the concept of in-degrees to identify the order of vertices. The main idea is to track the number of incoming edges (in-degrees) for each vertex. If a vertex has no incoming edges, it can be added to the sorted order and its neighbors' in-degrees are updated accordingly. This approach is particularly suitable for this problem because it clearly handles the dependencies between vertices, ensuring that we only add a vertex to the ordering once all its prerequisites have been added.

1. **Initialize In-Degree Count**: Create a dictionary to count the in-degrees of each vertex in the graph. For example, given a graph represented as `{'A': ['B', 'C'], 'B': ['D'], 'C': ['D'], 'D': []}`, the in-degrees would be `{'A': 0, 'B': 1, 'C': 1, 'D': 2}`.
2. **Queue for Vertices with 0 In-Degree**: Use a queue to store all vertices with an in-degree of 0. Initially, this will contain only vertex 'A'.
3. **Process the Queue**: While the queue is not empty, do the following:
   - Dequeue a vertex and add it to the topological order.
   - For each neighbor of this vertex, reduce its in-degree by 1. If any neighbor's in-degree becomes 0, enqueue that neighbor.
4. **Check for Cycles**: If the topological order contains all vertices, return it; otherwise, a cycle exists, and a topological sort is not possible.

For instance, starting with `{'A': ['B', 'C'], 'B': ['D'], 'C': ['D'], 'D': []}`, we would first enqueue 'A', then process it to enqueue 'B' and 'C', leading to a final output like `['A', 'B', 'C', 'D']`.

Here’s the implementation in Python:

```python
from collections import deque, defaultdict

def topological_sort(graph):
    # Step 1: Initialize in-degrees and the queue
    in_degree = defaultdict(int)
    for vertex in graph:
        for neighbor in graph[vertex]:
            in_degree[neighbor] += 1
    
    queue = deque([v for v in graph if in_degree[v] == 0])
    top_order = []
    
    # Step 2: Process the queue
    while queue:
        vertex = queue.popleft()
        top_order.append(vertex)
        for neighbor in graph[vertex]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
                
    # Step 3: Check if topological sort is possible
    if len(top_order) == len(graph):
        return top_order
    else:
        return []  # Return empty list if there's a cycle
```
This implementation ensures that we return a valid topological sort for any DAG represented as an adjacency list.

The time complexity of Kahn's algorithm is O(V + E), where V is the number of vertices and E is the number of edges. This is because we process each vertex and each edge exactly once. The space complexity is O(V) for storing in-degrees and the queue. Given the constraints of the problem, this complexity is efficient and manageable for typical graph sizes.

1. **Empty Graph**: If the graph is empty, the function should return an empty list, as there are no vertices to sort.
2. **Single Vertex**: A graph with a single vertex should return that vertex in the list since there are no edges.
3. **Disconnected Graph**: For a graph with multiple disconnected components (e.g., `{'A': ['B'], 'C': []}`), the algorithm should still return a valid topological order including all vertices, e.g., `['A', 'C', 'B']`.
4. **Cycle Detection**: Although the problem specifies a DAG, if a cycle were mistakenly included, the function should correctly return an empty list to indicate that a topological sort is not possible.

Topological Sort on graph

Anthropic

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

Anthropic 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