Unexpected Output from Implementing Topological Sorting in Python - Handling Cycles
I'm experimenting with I'm sure I'm missing something obvious here, but I'm trying to implement a topological sorting algorithm in Python using Kahn's Algorithm, but I'm running into an scenario when there are cycles in the graph... Instead of returning an behavior as I expected, it's just giving me an empty list. Here's what I have so far: ```python from collections import deque def topological_sort(vertices, edges): graph = {v: [] for v in vertices} in_degree = {v: 0 for v in vertices} for u, v in edges: graph[u].append(v) in_degree[v] += 1 queue = deque([v for v in vertices if in_degree[v] == 0]) sorted_list = [] while queue: node = queue.popleft() sorted_list.append(node) for neighbor in graph[node]: in_degree[neighbor] -= 1 if in_degree[neighbor] == 0: queue.append(neighbor) return sorted_list vertices = [1, 2, 3, 4] edges = [(1, 2), (2, 3), (3, 1)] # This introduces a cycle result = topological_sort(vertices, edges) print(result) # Expecting an behavior or indication of a cycle ``` I've checked and verified that my graph construction is correct, but when I run the code, `result` is just an empty list. I was under the impression that if a cycle exists, the algorithm should not be able to produce a valid topological sort. I've also looked into trying to detect cycles separately, but I'm unsure how to integrate that with this implementation. Could someone shed some light on how I can modify my algorithm to correctly handle cycles, maybe by raising an exception or returning a specific value? Also, are there any best practices for detecting cycles in a directed graph that I should consider? What am I doing wrong? For context: I'm using Python on Windows 10. The stack includes Python and several other technologies.