給它一個圖形和一棵生成樹，一個transmuter是一個從它衍生出來的輔助圖形，可以加速原始圖形上的某些操作。它是由Tarjan發明的：爲給定的圖形及其生成樹構建一個transmuter
Robert E. Tarjan. Applications of Path Compression on Balanced Trees. Journal of the ACM, 26(4):690–715, 1979.
Robert E. Tarjan. Sensitivity Analysis of Minimum Spanning Trees and Shortest Path Trees. Information Processing Letters, 14(1):30–33, 1982.
我發現自己需要一個transmuter。不幸的是，我無法訪問這兩個文件。有人可以知道transmuter和/或有權訪問這些文件詳細介紹transmuter和構建它的算法嗎？
http://www.cs.princeton.edu/courses/archive/fall03/cs528/handouts/applications%20of%20path%20compression.pdf從http://scholar.google.com/scholar?q=%22Applications+of+Path+Compression+on+Balanced+Trees.%22從http://www.informatik.uni-trier.de/~ley/db/journals/jacm/jacm26.html#Tarjan79
不幸http://scholar.google.com/scholar?q=%22Sensitivity+Analysis+of+Minimum+Spanning+Trees+and+Shortest+Path+Trees.%22沒有PDF鏈接。如果有其他文件可能有所幫助，請參閱http://www.informatik.uni-trier.de/~ley/db/indices/a-tree/t/Tarjan:Robert_Endre.html。
謝謝安德魯。這可能是迄今爲止我能得到的最好結果。如果沒有人能夠給出算法本身的解釋，我會等待一會兒再接受你的答案。 – edwardw
你想要這些文件還是隻討論如何構建一個圖並在其上運行最小生成樹？你也想要關於壓縮的二叉搜索樹的信息嗎？ B-Trees可能是你正在尋找的東西（http://en.wikipedia.org/wiki/B-tree）。 –
文件將做。但是不，我對構建一個圖形和一棵生成樹不感興趣。我想知道如何構建一個transmuter，這也是一個圖表。我編輯了這個問題來闡明我的意圖。 – edwardw
以下是有點誤導。我沒有編輯權限。 「有人可以知道數據結構和/或有權訪問這些文件，詳細闡述一下關於transmuter和構建它的算法嗎？」。此外，ACM文章不是免費的，我認爲免費發行它們打破了版權法？ –