JAVA圖形/ DFS實現

Question

我有一個小的困境，我想用被告知 -

我執行的圖形（定向），我希望把它額外的通用 - 這是圖形，其中T是數據在節點（頂點）。 要添加一個頂點到圖中將是 - add（T t）。該圖將把T包裹到一個頂點，該頂點將把T放在裏面。

接下來，我想，在圖上運行DFS - 現在，這裏是我的困境 - 我應該保持「訪問」標記的頂點（成爲會員），或在運行DFS啓動一些地圖（地圖頂點 - >狀態）？

保持頂點不是通用的（頂點不應該熟悉DFS算法和實現）。但是創建地圖（頂點 - >狀態）非常耗費空間。

您認爲如何？

非常感謝！

Answer 1

如果您需要運行算法，特別是更復雜的算法，您將很快發現您將不得不將所有類型的數據與頂點相關聯。有一個通用的方法來存儲數據與圖形項目是一個好主意，當然，讀取和寫入數據的訪問時間應該是O（1），理想情況下。簡單的實現可以是使用HashMap，對於大多數情況來說，它具有O（1）的訪問時間，但是該因子相對較高。

對於yFiles Graph Drawing Library，他們添加了一種機制，數據實際上存儲在元素本身，但您可以根據需要分配儘可能多的數據插槽。這與管理每個元素的Object[]以及將數據數組中的索引用作「映射」類似。如果圖形沒有改變，另一種策略是將元素的索引與元素本身（只是整數）一起存儲，然後使用該索引來索引到一個數組中，其中對於每個「數據圖」一個數組的大小的元素數量。這兩種技術都可以很好地擴展並提供最佳的訪問時間，除非您的數據真的很稀疏（只有部分元素實際需要存儲數據）。

的「Object[]在元素」的方法：

• 在你的頂點和邊緣種類，添加Object[]類型的字段是包私有。
• 實現一個Map接口，提供T getData(Vertex)和void setData(Vertex, T），該接口可以由HashMap<Vertex,T>但一個我實際上暗示僅存儲被用於索引到所述Object[]陣列在一個整數index被備份的
• 一個實施頂點。
• 在您的圖表類中，添加一個方法createMap，用於跟蹤已使用索引和空閒索引，並創建上述類的新實例，其getter和setter實現使用Vertex類的包專用字段實際訪問數據

「一個陣列」的方法：

• 包專用整型字段添加到您的頂點類
• 保持同步的整數字段與圖表中的頂點的順序 - 第一個頂點有索引0等
• 在替代地圖實現中，您最初將分配一個T[]，其大小爲 的頂點數。
• 在getter和setter實現中，獲取Vertex的索引並使用它訪問數組中的值。

對於DFS算法我會選擇「一個陣列」 -approach，你可以使用一個byte []（或者「訪問」是所有需要你甚至可以用一個BitSet）的空間效率和如果圖形已連接，則可能會爲DFS中的所有頂點填充數據。這應該比基於HashMap的方法執行得更好，並且不需要裝箱和拆箱來將數據存儲在Object[]中。