基於相鄰節點計算節點值的圖算法

Question

我想要製作一個圖算法，該算法根據相鄰節點的每個值更新/計算節點f(n)的值作爲f(n)值的函數。

• 該圖被指示。
• 每個節點都有最初的f（n）值。
• 每條邊都沒有成本（0）。
• 每個節點的值是其當前值的最大值和每個相鄰節點的值（有向圖，因此相鄰節點是節點具有傳入邊的節點的值）。

更正式，

f(n) = max(f(n),max_i(f(n_i))), where i from neighbor 1 to neighbor k. 

我可以想像這樣的一些方法，但是我不知道什麼延長 他們是最佳的。

任何人都可以請給出建議和評論（你認爲 你的建議是最佳的）還是建議我可以適應任何現有的圖算法？

Answer 1

要求：

1. 在每種Strongly Connected ComponentV在圖中，在該SCC所有頂點的值具有相同的最終得分。
   「證明」（準則）：通過在此SCC中進行傳播，您可以將所有分數迭代設置爲在此SCC中找到的最大值。

2. 在DAG中，每個頂點的值是max{v,parent(v) | for all parents of v}（定義），並且可以在從開始到結束的單次迭代中找到分數。
   「證明」（準則）：沒有「後沿」，所以如果你知道所有父母的最終值，你就知道每個頂點的最終值。通過歸納（基礎是所有來源） - 你可以得到一個事實，即一次迭代足以確定最終得分。

3. 此外，已知表示 圖g的SCC的圖G'是DAG。

從以上我們可以得出一個簡單的算法：在圖

1. Fing頭最大的SCC（可以用Tarjan algorithm完成），並創建SCC圖表。讓它成爲G'。請注意，G'是一個DAG。
2. 對於每個SCC V：設置f'(V) = max{v | v in V}（直觀上 - 將每個SCC的值設置爲此SCC中的最大值）。
3. Topological sort圖G'。
4. 根據（3）中的拓撲排序進行單遍歷 - 並根據其父項計算G'中每個頂點的f'（V）。
5. 設置f(v) = f'(V)（其中v是在SCC V）

複雜性：

1. 的Tarjan和創建G'是O(V+E)
2. 尋找f」被在的大小也是線性的圖 - O(V+E)
3. 拓撲排序運行在O(V+E)
4. 單次遍歷 - 線性：O(V+E)
5. 給出最終得分：線性！

所以上面的算法是在圖形的大小線性 - O(V+E)