查找樹中的常見子樹

請考慮下面的這個概念圖，僅用於演示目的。查找樹中的常見子樹

Abc  Foo 
    \  / \ 
     \ / Foo2 
     Bar  \ 
    / \  Foo3 
    Bar2 Bar3  \ 
    / \   Foo4 
    X Y

在上面的樹中，有一個獨特的「路徑」，Foo-> Bar-> Bar2-> X。此路徑與Abc-> Bar-> Bar2-> X不同。顯然，在上述表示中丟失了這些信息，但考慮我已存儲了所有單獨的唯一路徑。

但是他們這樣做，共享路徑「酒吧，> Bar2-> X」的某些部分。

的算法我想要麼找到或實現的目的是，我想這彙總信息，所以我不能存儲各個路徑。但更重要的是，我試圖找到所有這些共同的路徑，並賦予它們權重。因此，例如，在上述情況下，我可以濃縮有關「Bar-> Bar2-> X」的信息，並說它發生了兩次。很明顯，我會要求它適用於所有情況。

是的，最終的想法是能夠快速問「給我一個從Foo所有不同的路徑」。在這個例子中，只有1，Foo-> Bar-> Bar2-> X。 Foo-> Bar-> Bar2-> Y和Foo-> Bar-> Bar3不存在。該圖僅用於查看目的。

任何想法？

來源

2012-03-04 halivingston

http://stackoverflow.com/questions/1685239 http://stackoverflow.com/questions/6673994 – 2012-03-04 10:29:10

你在談論一個「樹」，是指那些邊緣真的執導？整個「樹」如何存儲？ – 2012-03-04 11:18:17

所以這只是一個起點，我希望別人會幫我填，但我會考慮他們作爲字符串，並期待在公共子路徑，共同的子問題，這在過去一直看着頗有幾分。關閉我的頭頂，我可能會顛倒每個路徑/字符串，然後從那裏構建一個trie結構，因爲通過計算給定節點下面的鍵的數量，您可以看到結尾路徑被使用了多少次......有可能一個更好，更有效的方法，但應該有效。任何人有想法把它們當作字符串來對待？

來源

2012-03-04 07:45:33 hackartist

嗯我必須考慮一個trie，這是有道理的... – halivingston 2012-03-04 15:43:44

您可以分別存儲每條獨特的路徑。要回答「如何調用Foo」等問題，可以使用散列表的形式創建索引。

作爲替代方案，你可以嘗試使用DAWG，但我不知道它有多少會在你的情況有所幫助。

來源

2012-03-04 16:48:09 svick

查找樹中的常見子樹

回答

相關問題