线性时间的算法，使强连接图 [英] Linear time algorithm to make a graph strongly connected

问题描述

我们有一个弱非循环有向图。

We have a weakly acyclic digraph.

此外，我们将得到一个集合A，其中认为有G的顶点度的零和一组B，其认为有出度为零的顶点。 （A的尺寸更小那么B的大小）。

Also we are given a set A which holds vertices of G that have in-degree zero and a set B which holds vertices that have out-degree zero. (size of A is smaller then size of B).

在最重要的是，我们也知道，如果在A和B的项目有一个特定的顺序（如A = A1，A2，...，我和B = B1，B2，......，BN）一个DFS开始在AI访问BI（1≤我≤M）。

On top of that, we also know that if items in A and B have a particular order (e.g. A = a1, a2, ..., am and B = b1, b2, ... , bn) a DFS started at ai visits bi (1≤ i ≤ m).

是否有可能设计出一个线性时间算法，这使得摹加入到它尽可能少的边缘尽可能强连通？

Is it possible to design a linear time algorithm which makes G strongly connected by adding to it as few edges as possible?

推荐答案

添加弧b <子>Ĵ - >一个<子> J + 1 对于j = 1，...， M-1和圆弧b <子>Ĵ - >一个<子> 1 对于j = M，...，N

Add arcs b_j -> a_j+1 for j = 1, ..., m-1 and arcs b_j -> a₁ for j = m, ..., n.

将所得的图形是强烈连接，因为一个和b的是从<子>强连通通过加入的弧和路径我为b <子>我和，对于每个节点x中，存在I，J，使得存在从一个<子>我 x和在从x原图的路径在原始图中的路径与b <子>Ĵ

The resulting graph is strongly connected because the a's and b's are strongly connected by the added arcs and the paths from a_i to b_i and, for every node x, there exist i, j such that there exists a path in the original graph from a_i to x and a path in the original graph from x to b_j.

我们不能使用更少的圆弧，因为传出弧必须被添加到每个B <子> 1 ，...，B <子> N 的

We cannot use fewer arcs, because an outgoing arc must be added to each of b₁, ..., b_n.

这篇关于线性时间的算法，使强连接图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！