The chapter suggests an alternative algorithm for linearization (topological sorting), which repeatedly removes source nodes from the graph (page 101). Show that this algorithm can be implemented in linear time.
solution:
Another algorithm for topological sorting.
We will keep an array $\mathbf {in}[u]$ which holds the indegree (number of incoming edges) of each node. For a source, this value is zero. We will also keep a linked list of source nodes.
(Set the $\mathbf{in}$ array.)
for all $u\in V$: $\mathbf{in}[u]\gets 0$
for all edges $(u,w)\in E$: $\mathbf{in}[w]\gets \mathbf{in}[w]+1$(Check for sources.)
$L\gets \text{empty linked list}$
for all $u\in V$:
if $\mathbf{in}[u]$ is $0$: add $u$ to $L$for $i=1 \text{ to } |V|$:
Let $u$ be the first node on $L$; output it and remove it from $L$.
(Remove $u$; update indegrees.)
for each edge $(u,w)\in E$:
$\mathbf{in}[w]\gets \mathbf{in}-1$
if $\mathbf{in}[w]$ is $0$: add $w$ to $L$.
I understand it until the last part. Can someone go over the "for $i=1 \text{ to } |V|$" block of the solution?