Topological sort + cycle detection in directed graphs Quiz

Test your understanding of topological sorting, cycle detection in directed graphs, and compare Kahn’s algorithm with DFS approaches for tasks like build systems and scheduling. Sharpen your skills on dependency ordering and practical algorithm concepts with these essential questions.

1. Definition and Basics

   Which of the following best describes a topological sort of a directed acyclic graph (DAG)?

   1. A list of all shortest paths between every pair of vertices.
   2. A cyclic ordering of vertices.
   3. A linear ordering of vertices where for every directed edge u → v, u comes before v in the ordering.
   4. An adjacency matrix representation of the graph.

2. Cycle Detection

   Why is it impossible to perform a topological sort on a directed graph that contains a cycle?

   1. Because the algorithm will always terminate early.
   2. Because the presence of a cycle means some dependencies can never be ordered correctly.
   3. Because all cycles can always be sorted topologically.
   4. Because there will be at least one vertex with zero in-degree.

3. Algorithm Selection

   Which algorithm is commonly used for topological sorting that repeatedly removes nodes of zero in-degree from the graph?

   1. Kahn's algorithm
   2. Prim's algorithm
   3. Bellman-Ford algorithm
   4. Kruskal's algorithm

4. DFS Approach

   In the DFS-based approach to topological sorting, when should a node be added to the output list?

   1. Every time the algorithm revisits it.
   2. Before any of its neighbors are visited.
   3. When it is first visited.
   4. After all its descendants have been fully visited (post-order).

5. Practical Application

   If you are scheduling project tasks with dependencies, why might you use topological sorting?

   1. To ensure tasks are executed in an order that respects dependencies.
   2. To detect the shortest paths between tasks.
   3. To maximize resource usage regardless of dependencies.
   4. To randomly order all tasks.

6. Cycle Detection Mechanism

   How does the DFS method typically detect cycles when performing a topological sort?

   1. By checking if a node has already been fully visited.
   2. By using a recursion stack to keep track of nodes in the current path and detecting back edges.
   3. By examining the in-degree of each node.
   4. By sorting all nodes alphabetically.

7. Indegree Concept

   In Kahn's algorithm, what does a node having zero in-degree indicate during execution?

   1. The node forms a cycle with others.
   2. The node can be safely added to the sorted order as it has no dependencies left.
   3. The node has no outgoing edges.
   4. The node must be skipped in the current iteration.

8. Detecting Cycles with Kahn's Algorithm

   What does it mean if Kahn’s algorithm finishes with unprocessed nodes remaining in the graph?

   1. The graph is already sorted.
   2. There are unreachable nodes from the start node.
   3. All nodes have multiple parents.
   4. The graph contains one or more cycles.

9. Real-world Scenario

   In a build system where files depend on each other, what could a topological sort help determine?

   1. The memory required to store all files.
   2. The correct order in which files should be compiled.
   3. The total number of functions in each file.
   4. Which file contains syntax errors.

10. Algorithm Comparison

    Compared to the DFS approach, what is a key advantage of using Kahn’s algorithm for topological sorting?

    1. It always requires more memory.
    2. It can detect cycles directly by checking if all nodes are processed.
    3. It only works on undirected graphs.
    4. It produces shorter paths between vertices.