Graph Algorithms • BFS Based

Topological Sort (Kahn's)

Kahn's algorithm uses a BFS strategy to find a topological ordering. It works by maintaining the in-degree of each node and iteratively processing those with zero dependencies.

Try Interactive Simulator

In-Degree

The number of incoming edges to a node. A node with 0 in-degree is a "source" and can be processed immediately.

Dependency

When a node is processed, it's "removed" from the graph, reducing the in-degree of all its neighbors.

The Queue

A queue stores all nodes whose in-degree has become 0, ensuring we process them in a valid topological order.

Cycle Detector

If we can't process all nodes because none have 0 in-degree, the remaining nodes must form a cycle.

Loading Lab...

Graph Algorithms • BFS Based

Topological Sort (Kahn's)

Kahn's algorithm uses a BFS strategy to find a topological ordering. It works by maintaining the in-degree of each node and iteratively processing those with zero dependencies.

Try Interactive Simulator

In-Degree

The number of incoming edges to a node. A node with 0 in-degree is a "source" and can be processed immediately.

Dependency

When a node is processed, it's "removed" from the graph, reducing the in-degree of all its neighbors.

The Queue

A queue stores all nodes whose in-degree has become 0, ensuring we process them in a valid topological order.

Cycle Detector

If we can't process all nodes because none have 0 in-degree, the remaining nodes must form a cycle.

Topological Sort Kahns

Topological Sort Kahns

Topological Sort (Kahn's)

In-Degree

Dependency

The Queue

Cycle Detector

Topological Sort (Kahn's)

In-Degree

Dependency

The Queue

Cycle Detector