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

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.

1
2
3
4
5
6
7
8
9

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)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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)

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用