如何将强连通分量减少到一个顶点?
How to reduce a strongly connected component to one vertex?
来自https://algs4.cs.princeton.edu/42digraph/
- Reachable vertex in a digraph. Design a linear-time algorithm to determine whether a digraph has a vertex that is reachable from
every other vertex.
Kosaraju-Sharir algorithm gives us the strongly connected components. Java code for that can be seen here。将每个 SCC 减少为单个顶点,出度为零的顶点可以相互可达。
问题是,每个人似乎都在谈论减少 SCC 而没有提供细节。这样做的有效算法是什么?
以下是针对我自己的问题的 Java 解决方案。对于图形表示,它使用 https://github.com/kevin-wayne/algs4. There appears to be general algorithms for graph contraction, as outlined in this paper 中的 edu.princeton.cs:algs4:1.0.3
;但是,就我的目的而言,以下内容就足够了。
/**
* 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 可以从所有其他顶点到达。
我在任何地方都找不到的是我上面介绍的那种细节。像 "well, this is easy, you do that, then you do something else" 这样的评论没有具体细节。
假设您已经有了计算 SCC
s 的方法以及常用的图、顶点和边方法。然后它只是创建一个新图,为每个 SCC 添加一个顶点代表,然后添加边代表。
对于边,您需要能够将原始顶点(边的目的地)映射到它在新图中的代表。您可以在第一遍中使用将顶点映射到它们的 SCC 的 Map<Vertex, SCC>
和将 SCC 映射到它们在新图中的代表性顶点的 Map<SCC, Vertex>
来建模。或者你直接有一个 Map<Vertex, Vertex>
将原始顶点映射到它们的代表。
这是一个Java解决方案:
public static Graph graphToSccGraph(Graph graph) {
Collection<SCC> sccs = SccComputation.computeSccs(graph);
Graph sccGraph = new Graph();
Map<Vertex, SCC> vertexToScc = new HashMap<>();
Map<SCC, Vertex> sccToRep = new HashMap<>();
// Add a representative for each SCC (O(|V|))
for (SCC scc : sccs) {
Vertex rep = new Vertex();
sccGraph.addVertex(rep);
sccToRep.put(scc, rep);
for (Vertex vertex : scc.getVertices()) {
vertexToScc.put(vertex, scc);
}
}
// Add edge representatives (O(|E|))
for (Vertex vertex : graph.getVertices()) {
Vertex sourceRep = sccToRep.get(vertexToScc.get(vertex));
for (Edge edge : vertex.getOutgoingEdges()) {
Vertex destRep = sccToRep.get(vertexToScc.get(edge.getDestination()));
Edge edgeRep = new Edge(sourceRep, destRep);
if (!sccGraph.contains(edgeRep)) {
sccGraph.addEdge(edgeRep);
}
}
}
return sccGraph;
}
图的大小(顶点和边的数量)的时间复杂度是线性,因此最佳。即Theta(|V| + |E|)
.
通常人们使用 Union-Find(参见 Wikipedia)数据结构来使这更简单并摆脱 Map
s。
来自https://algs4.cs.princeton.edu/42digraph/
- Reachable vertex in a digraph. Design a linear-time algorithm to determine whether a digraph has a vertex that is reachable from every other vertex.
Kosaraju-Sharir algorithm gives us the strongly connected components. Java code for that can be seen here。将每个 SCC 减少为单个顶点,出度为零的顶点可以相互可达。
问题是,每个人似乎都在谈论减少 SCC 而没有提供细节。这样做的有效算法是什么?
以下是针对我自己的问题的 Java 解决方案。对于图形表示,它使用 https://github.com/kevin-wayne/algs4. There appears to be general algorithms for graph contraction, as outlined in this paper 中的 edu.princeton.cs:algs4:1.0.3
;但是,就我的目的而言,以下内容就足够了。
/**
* 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 可以从所有其他顶点到达。
我在任何地方都找不到的是我上面介绍的那种细节。像 "well, this is easy, you do that, then you do something else" 这样的评论没有具体细节。
假设您已经有了计算 SCC
s 的方法以及常用的图、顶点和边方法。然后它只是创建一个新图,为每个 SCC 添加一个顶点代表,然后添加边代表。
对于边,您需要能够将原始顶点(边的目的地)映射到它在新图中的代表。您可以在第一遍中使用将顶点映射到它们的 SCC 的 Map<Vertex, SCC>
和将 SCC 映射到它们在新图中的代表性顶点的 Map<SCC, Vertex>
来建模。或者你直接有一个 Map<Vertex, Vertex>
将原始顶点映射到它们的代表。
这是一个Java解决方案:
public static Graph graphToSccGraph(Graph graph) {
Collection<SCC> sccs = SccComputation.computeSccs(graph);
Graph sccGraph = new Graph();
Map<Vertex, SCC> vertexToScc = new HashMap<>();
Map<SCC, Vertex> sccToRep = new HashMap<>();
// Add a representative for each SCC (O(|V|))
for (SCC scc : sccs) {
Vertex rep = new Vertex();
sccGraph.addVertex(rep);
sccToRep.put(scc, rep);
for (Vertex vertex : scc.getVertices()) {
vertexToScc.put(vertex, scc);
}
}
// Add edge representatives (O(|E|))
for (Vertex vertex : graph.getVertices()) {
Vertex sourceRep = sccToRep.get(vertexToScc.get(vertex));
for (Edge edge : vertex.getOutgoingEdges()) {
Vertex destRep = sccToRep.get(vertexToScc.get(edge.getDestination()));
Edge edgeRep = new Edge(sourceRep, destRep);
if (!sccGraph.contains(edgeRep)) {
sccGraph.addEdge(edgeRep);
}
}
}
return sccGraph;
}
图的大小(顶点和边的数量)的时间复杂度是线性,因此最佳。即Theta(|V| + |E|)
.
通常人们使用 Union-Find(参见 Wikipedia)数据结构来使这更简单并摆脱 Map
s。