我有一個 DAG，其中一條邊表示兩個節點之間的依賴關系，一個節點表示要在機器上執行的任務。有多臺機器。對于每個（任務，機器）對，都有一個估計的運行時間。現在，我想將此 DAG 分成一個森林，以便森林中的每個子圖都表示自己是一個“完整”的 DAG，并由拓撲級別的有序排序表示。“完整”是指從任何根節點開始的子圖具有它在原始 DAG 中的所有路徑。我得到了一個無序的List<Task> tasks地方Task是一個類，表示 DAG 中的任務節點。每個任務都有一個包含所有父級的串列和一個包含所有子級的串列。我將如何天真地進行：遍歷所有節點 v，執行 dfs 以使子圖以 v 為根，在每次迭代中檢查是否可以合并兩個子圖，因為它們有一個共同的父節點。這可以更快地完成嗎？
uj5u.com熱心網友回復：
使用遍歷子鏈接和父鏈接的深度優先搜索將圖形分成組件。然后您可以對每個組件進行拓撲排序。兩種演算法都是 O(N E)（對于 N 個節點和 E 條邊）；這可能是 O(N2)，但對于依賴關系數量通常很少的典型依賴關系圖，它可能更接近 O(N)。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/482722.html
上一篇：添加/洗掉節點后確定關節點