22-4 Reachability

Let \(G = (V, E)\) be a directed graph in which each vertex \(u \in V\) is labeled with a unique integer \(L(U)\) from the set \(\\{1, 2, \ldots, |V|\\}\). For each vertex \(u \in V\), let \(R(u) = \\{v \in V: u \leadsto v \\}\) be the set of vertices that are reachable from \(u\). Define \(\min(u)\) to be the vertex in \(R(u)\) whose label is minimum, i.e., \(\min(u)\) is the vertex \(v\) such that \(L(v) = \min \\{L(w): w \in R(u) \\}\). Give an \(O(V + E)\)-time algorithm that computes \(\min(u)\) for all vertices \(u \in V\).

1. Compute the component graph \(G^{\text{SCC}}\) (in order to remove simple cycles from graph \(G\)), and label each vertex in \(G^{\text{SCC}}\) with the smallest label of vertex in that \(G^{\text{SCC}}\). Following chapter 22.5 the time complexity of this procedure is \(O(V + E)\).

2. On \(G^{\text{SCC}}\), execute the below algorithm. Notice that if we memorize this function it will be invoked at most \(V + E\) times. Its time complexity is also \(O(V + E)\).

C++
1
2
3
4
5
REACHABILITY(u)
    u.min = u.label
    for each v ∈ Adj[u]
        u.min = min(u.min, REACHABILITY(v))
    return u.min

3. Back to graph \(G\), the value of \(\min(u)\) on Graph \(G\) is the value of \(\min(u.scc)\) on Graph \(G^{\text{SCC}}\).

Alternate solution: Transpose the graph. Call \(\text{DFS}\), but in the main loop of \(\text{DFS}\), consider the vertices in order of their labels. In the \(\text{DFS-VISIT}\) subroutine, upon discovering a new node, we set its \(\text{min}\) to be the label of its root.

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