在兩個節點之間創建專用路徑的算法

Question

我有一些文本說明該序列遵循特定順序。一些文本因遍歷線索而改變。我的目標是爲每個頁面生成靜態頁面，並通過鏈接進行互連。

問題是解決一個工具的問題，該工具將爲印刷書籍（顯然是靜態的）生成文本。所以想象一下，你正在閱讀例1中所示的一本書（在下圖中）。最初，您在節點A中，並且此頁面的文本是「轉到頁面B或頁面C」。選擇節點C，接着F→B→E→H，你會看到節點H中的一個內容，它應該與你看到的是否被A→B→D遍歷的內容不同 - > H，例如。因爲它是一本印刷書籍，所以我需要複製一些路徑，以便根據所遍歷的路徑更改某些節點的內容。

實施例：

在本例中，我有橫動兩種可能性：

A -> B -> D 
A -> C -> D 

預期結果：

Page 1: A (link to page 2 and 3) 
Page 2: B (link to page 4) 
Page 3: C (link to page 5) 
Page 4: D 
Page 5: DD' 

這個簡單的例子，生成5頁，一旦頁面4有一部分文本應該是d只顯示讀數是否通過第3頁。

爲了模擬這個問題，我選擇了使用圖論。爲了更好地理解，我在下面的圖中畫了一個問題的兩個例子，我試圖解決：

注意，紅色虛線邊實際上不是邊緣。當訪問節點Y後，給定節點X的內容發生變化（讀取「如果到達X的路徑經過Y，則節點X的內容發生變化」），這些都是我用來表示的方式。

我讀了很多關於圖，遍歷策略（BFS和DFS）以及其他一些主題。我的目標是開發一種算法，以某種方式重新排列給定的圖形，以便生成前面提到的頁面。我沒有發現解決這個問題的任何已知問題，但我相信它應該已經存在。我的研究沒有發現任何有用的東西，所以我試圖自己解決。

我成功的方法是遍歷圖找到一個包含依賴於其他節點的內容的節點。找到該節點後，查找從依賴節點到當前節點的所有路徑。遍歷這些路徑，複製包含多個傳入邊的所有節點，刪除先前的連接並將當前節點與複製的節點連接，依此類推，直到消耗路徑的所有節點。這種算法效果很好，但這種方法效率不高，並且對於長文本可能會很慢。

我的問題是：你知道任何其他更好的方法來解決這個問題嗎？有沒有可以解決這類問題的理論或已知算法？

在此先感謝。

Answer 1

做一個DFS，當你看到一個訪問過的節點時，複製它，打破你剛纔訪問過的鏈接，並將新節點標記爲已訪問，並繼續從這個節點接收dfs。這種方法不會多次訪問節點，因此是最快的（這意味着它會訪問H1只是2次而不是n或k次）。

這在輸出圖形上是線性的。也就是說，如果輸出圖具有V'頂點和E'邊，則其順序爲O（V'+ E'）。你不可能達到更好的效果，因爲你必須至少訪問一次輸出圖中的所有內容。

Answer 2

我假設這些紅色邊緣的規則是stactic。將多個內容保存在一個節點中，而不是複製它。現在顯示的內容取決於到達它的路徑，在每一步我們都可以檢查DFS的「堆棧」以查看到達它的路徑。堆棧將爲我們提供到達它的確切路徑（但請注意，它不會詳細說明路徑是否訪問了父母的其他後代）。然後我們比較我們已經擁有的靜態規則並顯示內容。

時間複雜度分析（最差的情況）： 在DFS的每一步我們都按照規則檢查整個堆棧。堆棧的最大長度可以是h（其中h是樹的高度）。因此時間複雜度爲O（（V + E）* h）。或者，如果路徑訪問了父項的其他被繼承者（例如分析路徑A-> B-> E，如果它很重要D已經被刪除），那麼您可以在數據結構上自己引入紅色邊規則。再次保留節點中的多個內容。在決定要顯示哪些內容時，只需檢查是否已經訪問了「源自該頂點的紅色邊緣」的「端點」。現在使用規則來顯示適當的內容