Topological Sort Using Kahn's Algorithm BFS in DSA C - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind Kahn's Algorithm for Topological Sort?

Kahn's Algorithm uses BFS and repeatedly removes nodes with zero incoming edges, adding them to the sorted order until all nodes are processed.

beginner

In Kahn's Algorithm, what does a node with zero in-degree represent?

A node with zero in-degree has no dependencies and can be safely added next in the topological order.

intermediate

Why does Kahn's Algorithm detect cycles in a graph?

If after processing all nodes with zero in-degree, some nodes remain unprocessed, it means a cycle exists because those nodes still have dependencies.

beginner

What data structure is primarily used in Kahn's Algorithm to manage nodes with zero in-degree?

A queue is used to store and process nodes with zero in-degree in FIFO order.

intermediate

How does Kahn's Algorithm update the in-degree of nodes during processing?

When a node is removed from the queue, the in-degree of its neighbors is decreased by one. If any neighbor's in-degree becomes zero, it is added to the queue.

What is the first step in Kahn's Algorithm for topological sorting?

A Sort nodes alphabetically

B Find all nodes with zero in-degree and add them to a queue

C Remove edges randomly

D Start DFS from any node

Kahn's Algorithm begins by finding all nodes with zero in-degree to start processing them.

What does it mean if after running Kahn's Algorithm, not all nodes are included in the topological order?

A The graph has a cycle

B The graph is disconnected

C The graph is empty

D The graph is fully sorted

If some nodes remain unprocessed, it means a cycle exists, preventing a full topological sort.

Which data structure is used to keep track of nodes with zero in-degree in Kahn's Algorithm?

A Queue

B Stack

C Set

D Linked list

A queue is used to process nodes in the order they become free of dependencies.

How is the in-degree of a node defined?

A Number of edges going out from the node

B Number of neighbors

C Number of nodes in the graph

D Number of edges coming into the node

In-degree counts how many edges point to the node.

What happens when a node's in-degree becomes zero during Kahn's Algorithm?

A It is deleted from the graph

B It is ignored

C It is added to the queue for processing

D It is marked as visited but not processed

Nodes with zero in-degree are ready to be processed and added to the queue.

Explain step-by-step how Kahn's Algorithm performs a topological sort on a directed graph.

Think about how dependencies are removed one by one.

How does Kahn's Algorithm help in detecting cycles in a directed graph?

Focus on what happens when no nodes can be processed next.