16
我將Lengauer和Tarjan算法與路徑壓縮結合起來，爲有數百萬節點的圖計算支配樹。該算法相當複雜，我不得不承認我沒有花時間去完全理解它，我只是使用它。現在我需要計算根節點的直接子節點的支配樹，並可能將圖形遞歸到某個深度，重複此操作。即當我計算根節點的孩子的支配樹時，我想假裝根節點已從圖中移除。遞歸計算支配樹的有效方法？
我的問題是，是否有一個有效的解決方案，使用已經在根節點的初始支配樹中計算出的直接支配者信息？換句話說，我不想從頭開始爲每個孩子，因爲整個過程非常耗時。
天真地說，它似乎必須是可能的，因爲在圖形中會有很多節點深處有idoms，只是在它們上方稍微有一些點，並且不受圖的頂部變化的影響。
順便說一句：奇怪的是，支配樹的主題是編譯器人「擁有」的，在經典圖論的書中沒有提及它。我使用的應用程序 - 我的FindRoots java堆分析器 - 與編譯器理論無關。
澄清：我在這裏討論有向圖。我所指的「根」實際上是具有最大可達性的節點。我更新了上面的文字，用「圖形」替換了「樹」的引用。我傾向於把它們當作樹木，因爲形狀是，主要是樹木狀的。該圖實際上是Java堆中的對象，並且您可以想象其具有合理的等級。我在做OOM泄漏分析時發現支配樹是有用的，因爲你感興趣的是「什麼使這個對象活着？」最終的答案就是它的統治者。統治者樹讓你<ahem>看到木頭，而不是樹木。但有時候有很多垃圾漂浮在樹的頂部，所以你有一個根，有成千上萬的孩子在它的正下方。對於這樣的情況，我想試驗一下計算樹根中每個直接子樹（在原始圖中）的支配樹，然後可能進入下一層，等等。 （我試圖不用擔心後面的鏈接的可能性:)
是的，這可能會有所幫助，謝謝。我擔心算法的其他部分，雖然它通常需要與dfs相同的時間順序，但有時會更糟（這也是爲什麼您肯定需要路徑壓縮）。 – 2008-10-31 10:52:36