在圖上定義無效路徑

Question

我們正在研究一個規則有向圖適用於大多數情況的項目。但是在我們的圖表中，我們想要使某些路徑無效。例如，如果我們的圖是：

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

然後A-> B-> C是有效路徑但是A-> D-> C不是。我們可以在某個地方定義無效路徑並每次都進行驗證檢查，但這會導致重要的性能問題，因爲我們的應用程序高度依賴於圖形。

那麼，這種類型的情況是否有特殊的數據結構或算法？

感謝

Answer 1

你可以在from:list(to)每個節點存儲的映射，所以你知道，從A來的路徑不能去C，因爲它不是在節點列表中就可以去從C.如果你的深度大於1，那麼導致它的節點元組可以是一個密鑰而不是那個節點。這很像eBGP如何用於互聯網路由。

在另一個說明中，無論您決定如何使用數據結構，您都需要進行檢查。要麼是，要麼爲每種情況存儲多個圖表。