algorithm - 如何将强连通分量减少到一个顶点?
问题描述
来自https://algs4.cs.princeton.edu/42digraph/
- 有向图中的可达顶点。设计一个线性时间算法来确定一个有向图是否有一个可以从其他每个顶点到达的顶点。
Kosaraju-Sharir 算法为我们提供了强连通分量。Java 代码可以在这里看到。将每个 SCC 减少到一个顶点,一个外度为零的顶点可以相互到达。
问题是,似乎每个人都在谈论减少 SCC 而没有提供细节。这样做的有效算法是什么?
解决方案
以下是我自己的问题的 Java 解决方案。对于图形表示,它使用edu.princeton.cs:algs4:1.0.3
来自https://github.com/kevin-wayne/algs4。如本文所述,似乎有用于图形收缩的通用算法;但是,就我的目的而言,以下内容就足够了。
/**
* 43. <b>Reachable vertex.</b>
* <p>
* DAG: Design a linear-time algorithm to determine whether a DAG has a vertex that is reachable from every other
* vertex, and if so, find one.
* Digraph: Design a linear-time algorithm to determine whether a digraph has a vertex that is reachable from every
* other vertex, and if so, find one.
* <p>
* Answer:
* DAG: Consider an edge (u, v) ∈ E. Since the graph is acyclic, u is not reachable from v.
* Thus u cannot be the solution to the problem. From this it follows that only a vertex of
* outdegree zero can be a solution. Furthermore, there has to be exactly one vertex with outdegree zero,
* or the problem has no solution. This is because if there were multiple vertices with outdegree zero,
* they wouldn't be reachable from each other.
* <p>
* Digraph: Reduce the graph to it's Kernel DAG, then find a vertex of outdegree zero.
*/
public class Scc {
private final Digraph g;
private final Stack<Integer> s = new Stack<>();
private final boolean marked[];
private final Digraph r;
private final int[] scc;
private final Digraph kernelDag;
public Scc(Digraph g) {
this.g = g;
this.r = g.reverse();
marked = new boolean[g.V()];
scc = new int[g.V()];
Arrays.fill(scc, -1);
for (int v = 0; v < r.V(); v++) {
if (!marked[v]) visit(v);
}
int i = 0;
while (!s.isEmpty()) {
int v = s.pop();
if (scc[v] == -1) visit(v, i++);
}
Set<Integer> vPrime = new HashSet<>();
Set<Map.Entry<Integer, Integer>> ePrime = new HashSet<>();
for (int v = 0; v < scc.length; v++) {
vPrime.add(scc[v]);
for (int w : g.adj(v)) {
// no self-loops, no parallel edges
if (scc[v] != scc[w]) {
ePrime.add(new SimpleImmutableEntry<>(scc[v], scc[w]));
}
}
}
kernelDag = new Digraph(vPrime.size());
for (Map.Entry<Integer, Integer> e : ePrime) kernelDag.addEdge(e.getKey(), e.getValue());
}
public int reachableFromAllOther() {
for (int v = 0; v < kernelDag.V(); v++) {
if (kernelDag.outdegree(v) == 0) return v;
}
return -1;
}
// reverse postorder
private void visit(int v) {
marked[v] = true;
for (int w : r.adj(v)) {
if (!marked[w]) visit(w);
}
s.push(v);
}
private void visit(int v, int i) {
scc[v] = i;
for (int w : g.adj(v)) {
if (scc[w] == -1) visit(w, i);
}
}
}
在下图中运行它会产生如图所示的强连接组件。简化 DAG 中的顶点 0 可以从其他每个顶点到达。
我在任何地方都找不到的是我上面介绍的那种细节。诸如“嗯,这很容易,你这样做,然后你再做其他事情”之类的评论在没有具体细节的情况下被抛出。
推荐阅读
- elasticsearch - Elasticsearch 6.4.2 无法启动
- ios - iOS:添加时区而不更改/转换时间值
- json - 将字符串数组从 curl 转换为文件中的分隔新行
- php - 我无法使用 docker 配置环境变量
- html - CSS对象适合:包含;在布局中保持原始图像宽度
- mysql - MySQL字符串日期时间转换
- python - Python:试图将一个简单的字符串连接成一个 URL
- ruby-on-rails - 调试出错报错 libicui18n.so.62: no such directory of file
- android-permissions - 谷歌审查短信权限问题
- reactjs - 我可以使用 react native 开发 pwa