如何做一個toposort;創建度數

我正在爲學校作業建立一個圖表結構。它目前表示爲一個鄰接表：我使用的是一個hashmap，其中的鍵是圖的節點（頂點），值是邊的列表（包含源節點和目標節點指針的對象以及「權重」）與關鍵節點相關聯。如何做一個toposort;創建度數

我的下一個任務是編碼拓撲排序，但我卡住了。我認爲最好的開始方式是給我的每個節點對象一個整數域用於indegree（通向節點的邊的數量），但是我不能想出一種方法將它分配給所有節點給我已經有的東西。

有什麼建議嗎？

來源

2012-11-24 Haskell

我建議你也創建節點的概念。除了你是Edge對象之外，你還可以使用Node對象，更好的建模功能總能幫助你更快地解決你的問題。由於可以在Node實例中存儲其他信息，因此使用Node定義的HashMap具有Integer鍵將有所幫助。

但是，如果你想/需要保持你當前的結構，爲了知道有多少邊導致給定節點，你必須遍歷HashMap入口集的不同值（根據你所說的將邊緣的列表），看看哪些邊有你正在尋找有一個目標節點，這些信息都必須存儲在輔助結構雖然節點（例如有另一個地圖）

來源

2012-11-24 01:07:55 pabrantes

感謝您的答覆！我應該進一步說明，我確實已經有一個Node對象;這些節點是我的HashMap中的關鍵。 – Haskell

那麼你爲什麼不執行以下操作：還可以創建圖表的概念，即物體內部有你已經有了HashMap中也含有作爲它的一部分的API方法addEdge（SRC節點，節點DST，INT重量）。每次調用addEdge創建一個邊緣對象，並插入到你的HashMap的時候，你遞增DST Node對象，讓你知道很多邊緣的方式在該節點內到達現場。 – pabrantes

太棒了！謝謝，我現在有一個有效的拓樸排序。 – Haskell

如何做一個toposort;創建度數

回答

相關問題