如何實現在C靜態圖

Question

我需要存儲一個圖表，遊戲的地圖用C編寫的遊戲服務器內

有圖有〜200個節點和3種邊緣可連接兩臺節點（這三種也可以重疊：例如，節點可以通過兩種不同類型的兩個邊連接）。一個節點的最大度是5-6個節點。

我想什麼有是有一種有效的方式來實現這種靜態結構，讓我做簡單的操作，如

• 是N1連接到N2？ （在確定性響應的情況下具有各種邊緣）
• n1連接到什麼？ （具有各種邊緣或特定的一種）

但是在多線程環境中，因爲會有很多依賴相同靜態圖形的遊戲實例。

由於圖不能被修改，並且該結構是衆所周知的我敢肯定有一些技巧來實現它在陰涼的方式使用最少的資源成爲可能。

我想避免使用STL或升壓現在..你有可能適應以及數據結構的任何線索？

（這不是一個過早的優化，但事實是，它會在VPS運行，我沒有太多的RAM既沒有CPU供電，所以我需要保持它緊）

編輯：只是因爲我忘了（和感謝，讓我意識到這一點）圖爲無向所以每邊是對稱的。在提前

感謝

Answer 1

許多答案是可能的。這個依賴於你節點相對較少的事實。這種方法的優點可能是無與倫比的性能。

的想法是代表你的圖形作爲一個200×200矩陣的字節，表示邊緣的每個條目。該字節爲您提供了256個不同的可能值，其中0顯然意味着「無連接」，任何非零位組合可以表示多達8種不同的邊緣類型。

讓該矩陣的「行」是起始節點和「列」是目的地。初始化結構，使得對於每個連接一個節點的邊，在開始/結束的交點處有一個值。該值可以是表示邊緣類型的位的組合。

要找出一個節點是否連接到另一個節點，只需查詢一個節點與另一個節點相交處的字節：如果那裏有一個非零值，則存在連接，並且該值將告訴您是什麼類型。

對於200個節點，這個數據結構將吃掉40KB，這相當適中。一旦超過1000個節點，它就不會很好地擴展。

只要沒有任何東西（除了一次性初始化）寫入這個結構，就會自然地線程安全，因爲它的狀態永遠不會改變。

Answer 2

自度是有限的，你可以通過只表示獲得非常不錯的表現節點由具有數組的數組構成指向其他節點的指針（每個邊類型都有一個數組）。無論你選擇的數據結構的

，就可以避免擔心多線程，如果你的圖形是隻讀的（正常爲多線程同步不訪問）。