我有一个有向图 G，有 N 个顶点，其中 k 个标记为“终端”。我想用从 v 可达的一组终端顶点标记每个顶点 v。我可以在空间 (R+r)N 中这样做吗，其中 R 是从 G 的节点可达的终端顶点的平均数量，r是一个小常数吗？
为了使这个更具体，数据结构大致如下所示:
struct Node{
bool isTerminal(); // True if this is a terminal node
vector<Node*> successors() ; //return the successors of this node
set<Node*> reachable_terminals; //the value to compute
bool done; //initially false
}
我们想要一个函数
void set_reachables(vector<Node> &); // the "&" means "pass by reference" in C++
它采用表示 G 中顶点的 Node vector ，并将 G 中每个节点的“reachable_terminals”成员设置为从该节点可达的终端。
具体来说，N 约为 100,000,00，k 约为 150。平均分支因子约为 3，从任何特定顶点最多只能到达约 1000 个顶点。 (通常最多可以从任何 v 到达十个终端顶点)。
现在，如果 G 是非循环的，则可以使用简单的深度优先搜索。这是导致问题的周期。此外，如果空间不是问题，我可以计算并存储每个节点的前任节点，然后从终端节点向后工作，但这会占用太多空间(请注意，节点 v 的后继节点不与 v 一起存储，而是计算出来的必要时在运行中)，并且我希望不必为每个节点多次计算 successors()。
我正在使用 C++，但任何算法描述都可以。
编辑:请注意，非循环情况下的 DFS 使用如下算法工作:
void set_reachables(vector<Node>&v){
for(auto & node:v) node.visit();
}
set<Node*> Node::visit(){
if (node.isTerminal()) reachableTerminals.insert(this);
if (done) return reachableTerminals;
for(auto&node:successors())
reachableTerminals=set_union(reachableTerminals,node.visit());
done=true;
return reachableTerminals;
}
显然，如果图是循环的，该算法将失败。
最佳答案
由于平均分支因子是常数，E = O(V)，其中E是边数，V是顶点的数量。反转图中的所有边。现在，从每个终端顶点开始执行 DFS，并相应地标记从终端顶点可达的所有顶点。这将在 O(kE) 时间内解决您的问题。虽然这不会达到您要求的复杂性，但考虑到您的图表上还有其他严格的稀疏性条件，这可能就足够了。 (当然，不是一般情况下，但我猜你的情况下你可能有更多的结构给其他人。)
关于c++ - 有限空间内的图可达性，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/24967434/