22.4 Topological sort

22.4-1

Show the ordering of vertices produced by $\text{TOPOLOGICAL-SORT}$ when it is run on the dag of Figure 22.8, under the assumption of Exercise 22.3-2.

Our start and finish times from performing the $\text{DFS}$ are

$$ \begin{array}{ccc} \text{label} & d & f \\ \hline m & 1 & 20 \\ q & 2 & 5 \\ t & 3 & 4 \\ r & 6 & 19 \\ u & 7 & 8 \\ y & 9 & 18 \\ v & 10 & 17 \\ w & 11 & 14 \\ z & 12 & 13 \\ x & 15 & 16 \\ n & 21 & 26 \\ o & 22 & 25 \\ s & 23 & 24 \\ p & 27 & 28 \end{array} $$

And so, by reading off the entries in decreasing order of finish time, we have the sequence $p, n, o, s, m, r, y, v, x, w, z, u, q, t$.

22.4-2

Give a linear-time algorithm that takes as input a directed acyclic graph $G = (V, E)$ and two vertices $s$ and $t$, and returns the number of simple paths from $s$ to $t$ in $G$. For example, the directed acyclic graph of Figure 22.8 contains exactly four simple paths from vertex $p$ to vertex $v: pov$, $poryv$, $posryv$, and $psryv$. (Your algorithm needs only to count the simple paths, not list them.)

The algorithm works as follows. The attribute $u.paths$ of node $u$ tells the number of simple paths from $u$ to $v$, where we assume that $v$ is fixed throughout the entire process. First of all, a topo sort should be conducted and list the vertex between $u$, $v$ as $\{v[1], v[2], \dots, v[k - 1]\}$. To count the number of paths, we should construct a solution from $v$ to $u$. Let's call $u$ as $v[0]$ and $v$ as $v[k]$, to avoid overlapping subproblem, the number of paths between $v_k$ and $u$ should be remembered and used as $k$ decrease to $0$. Only in this way can we solve the problem in $\Theta(V + E)$.

An bottom-up iterative version is possible only if the graph uses adjacency matrix so whether $v$ is adjacency to $u$ can be determined in $O(1)$ time. But building a adjacency matrix would cost $\Theta(|V|^2)$, so never mind.

SIMPLE-PATHS(G, u, v)
    TOPO-SORT(G)
    let {v[1], v[2]..v[k - 1]} be the vertex between u and v
    v[0] = u
    v[k] = v
    for j = 0 to k - 1
        DP[j] = ∞
    DP[k] = 1
    return SIMPLE-PATHS-AID(G, DP, 0)

SIMPLE-PATHS-AID(G, DP, i)
    if i > k
        return 0
    else if DP[i] != ∞
        return DP[i]
    else
       DP[i] = 0
       for v[m] in G.adj[v[i]] and 0 < m ≤ k
            DP[i] += SIMPLE-PATHS-AID(G, DP, m)
       return DP[i]

22.4-3

Give an algorithm that determines whether or not a given undirected graph $G = (V, E)$ contains a cycle. Your algorithm should run in $O(V)$ time, independent of $|E|$.

(Removed)

22.4-4

Prove or disprove: If a directed graph $G$ contains cycles, then $\text{TOPOLOGICAL-SORT}(G)$ produces a vertex ordering that minimizes the number of "bad" edges that are inconsistent with the ordering produced.

This is not true. Consider the graph $G$ consisting of vertices $a, b, c$, and $d$. Let the edges be $(a, b)$, $(b, c)$, $(a, d)$, $(d, c)$, and $(c, a)$. Suppose that we start the $\text{DFS}$ of $\text{TOPOLOGICAL-SORT}$ at vertex $c$. Assuming that $b$ appears before $d$ in the adjacency list of $a$, the order, from latest to earliest, of finish times is $c, a, d, b$.

The "bad" edges in this case are $(b, c)$ and $(d, c)$. However, if we had instead ordered them by $a, b, d, c$ then the only bad edges would be $(c, a)$. Thus $\text{TOPOLOGICAL-SORT}$ doesn't always minimizes the number of "bad" edges

22.4-5

Another way to perform topological sorting on a directed acyclic graph $G = (V, E)$ is to repeatedly find a vertex of $\text{in-degree}$ $0$, output it, and remove it and all of its outgoing edges from the graph. Explain how to implement this idea so that it runs in time $O(V + E)$. What happens to this algorithm if $G$ has cycles?

(Removed)