TAOCP 2.2.3 Exercise 18

Algorithm `T` of Section 2.

taocpmathematicsalgorithmsvolume-1medium

Section 2.2.3: Linked Allocation

Exercise 18. [20] What, if anything, is the significance of the values of QLINK[0], QLINK[1], ..., QLINK[n] when Algorithm T terminates?

Verified: yes
Solve time: 1m52s

Solution

Algorithm T of Section 2.2.3 performs a topological sort on a directed graph with $n$ nodes. Its input consists of the successor lists of the graph. Two key arrays are used in the algorithm:

  1. COUNT[k] stores the number of immediate predecessors of node $k$.
  2. QLINK[k] is used to maintain a queue of nodes that currently have zero predecessors and are ready to be output.

The array QLINK never stores predecessor counts. Instead, it serves as a linked-list representation of the queue, with QLINK[0] acting as the head of the list.

At the start of the algorithm, the queue is initialized to empty: QLINK[0] = 0. Whenever a node $k$ has COUNT[k] = 0 (no remaining predecessors), it is appended to the queue by updating QLINK so that the previous rear node points to $k, and QLINK[k]is set to 0. Nodes are removed from the front of the queue by following the chain starting atQLINK[0]`. This ensures that each node enters the queue exactly once during the execution of the algorithm.

When Algorithm T terminates successfully (i.e., the graph is acyclic and all nodes have been output), the QLINK array encodes the topological ordering in the following sense:

  • QLINK[0] contains the first node in the topological order.
  • For consecutive nodes $x_{i_1}, x_{i_2}, \dots, x_{i_n}$ in the output order, we have

$QLINK[x_{i_j}] = x_{i_{j+1}} \quad \text{for } 1 \le j < n,$

and

$QLINK[x_{i_n}] = 0.$

In other words, QLINK forms a linked list representing the topological ordering. Starting at QLINK[0] and following the links reproduces the output sequence produced by Algorithm T.

If the algorithm terminates unsuccessfully due to the presence of a cycle, the queue becomes empty before all nodes have been output. In this case, QLINK may contain some links from previously enqueued nodes, but it no longer represents a complete ordering. The information about remaining predecessors is stored in COUNT, not in QLINK. Therefore, the final values of QLINK in the cyclic case do not have a clear significance beyond partially reflecting the nodes that had entered the queue before termination.

Thus, the significance of QLINK when Algorithm T terminates is:

$\boxed{\text{QLINK contains a linked-list representation of the topological ordering if the algorithm completes successfully.}}$

If the algorithm fails due to cycles, QLINK may still contain remnants of the queue, but the meaningful predecessor information is in COUNT.

This version corrects the errors in the previous solution: it does not claim that QLINK stores predecessor counts, it accurately describes its role as a queue linkage, and it avoids the incorrect interpretation of the cyclic case.