टोपोलॉजिकल सॉर्ट कैलकुलेटर

टोपोलॉजिकल सॉर्ट (Topological Sort) क्या है?

Topological sort (also called topological ordering) is a linear ordering of the vertices of a directed acyclic graph (DAG) such that for every directed edge u → v, vertex u appears before vertex v in the ordering. Unlike standard sorting, topological sort is about dependency order, not numerical or alphabetical comparison.

Topological sort only exists when the graph has no directed cycles. If a cycle exists — say A → B → C → A — there is no consistent ordering because A must precede B, B must precede C, and C must precede A, which is impossible simultaneously.

निर्देशित अचक्रीय ग्राफ (DAG)

A directed acyclic graph (DAG) is a graph in which every edge has a direction and there are no directed cycles. DAGs naturally arise whenever you model dependencies: task A must complete before task B can start. The edges represent "must come before" relationships.

Common examples include: course prerequisites (Calculus before Differential Equations), software build dependencies (compile library before linking executable), recipe steps (chop ingredients before cooking), and spreadsheet cell formulas (compute D1 = A1 + B1 before E1 = D1 * 2).

काह्न एल्गोरिथम (Kahn's Algorithm)

Kahn's algorithm, published by Arthur B. Kahn in 1962, is the most intuitive approach. It works by repeatedly removing nodes that have no dependencies:

1. Compute in-degree for each node (number of incoming edges).
2. Initialize queue with all nodes having in-degree 0 (no dependencies).
3. While queue is not empty: dequeue node u, append to result, and for each neighbor v of u, decrement in-degree[v]. If in-degree[v] becomes 0, enqueue v.
4. Cycle check: if result contains all nodes, the graph is a DAG. Otherwise, remaining nodes form a cycle.

Time complexity: O(V + E) where V is the number of vertices and E is the number of edges. This is optimal since every vertex and edge must be examined at least once.

DFS-आधारित टोपोलॉजिकल सॉर्ट

The DFS-based approach uses depth-first search and records each node's finish time — the moment DFS fully explores all descendants. Nodes with higher finish times come earlier in the topological order. A cycle is detected when DFS encounters a back edge — an edge pointing to an ancestor in the current DFS path (a "gray" node in the three-color marking scheme).

Both Kahn's and DFS-based approaches have the same O(V + E) complexity, but they produce different valid orderings for the same graph (when multiple orderings exist).

टोपोलॉजिकल सॉर्ट के अनुप्रयोग

कितने वैध क्रम मौजूद हैं?

A graph can have multiple valid topological orderings. For a chain A → B → C → D, there is exactly one valid ordering. But for a "diamond" A → B → D, A → C → D, both [A, B, C, D] and [A, C, B, D] are valid. The count of valid orderings depends on the graph structure and grows quickly — counting all orderings is a #P-complete problem. This calculator enumerates all orderings for small graphs (up to 7 nodes).

चक्र का पता लगाने का विवरण (Cycle Detection)

In Kahn's algorithm, a cycle is detected when the result contains fewer than V nodes after the queue empties. The remaining nodes are involved in cycles — each has at least one incoming edge from another cycled node, so no node in the cycle ever reaches in-degree 0. In DFS-based detection, encountering a "gray" node (currently being processed) during traversal signals a back edge and thus a cycle.