有限空間中的圖可達性

Question

我有一個有N個頂點的有向圖G，其中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組頂點的向量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; 
} 

顯然，如果圖是循環的，該算法將失敗。

Answer 1

由於平均分支因子是一個常數，所以E = O(V)，其中E是邊數，V是頂點數。反轉圖形中的所有邊緣。現在，從每個終端頂點開始執行DFS，並相應地標記從終端頂點可到達的所有頂點。這在​​時間內解決了您的問題。雖然這並沒有達到您要求的複雜度，但考慮到您的圖表上還有其他嚴格的稀疏條件，這可能就足夠了。 （當然，不是一般的，但你猜對你的情況你可能有更多的結構給予其他人）。

Answer 2

你的問題是一個問題的變體，稱爲圖的傳遞閉包。升壓具有您可以使用一個實現：

http://www.boost.org/doc/libs/1_55_0/libs/graph/doc/transitive_closure.html

有在執行音符算法的高層次輪廓。