騎士的最短路徑圖的數據結構和算法

Question

我@Knight's Shortest Path Chess Question

我明白的答覆是在以前的stackflow後一個問題「OK，這是一個圖形的問題，和它的稀疏矩陣是像」：

(a1,b3)=1, 
(a1,c2)=1, 
    ..... 

其中描述了現有的邊緣。但是我仍然不知道這個圖的數據結構應該是什麼樣的（它是一個鄰接矩陣嗎？表示爲'稀疏矩陣'，還是別的？），以便Dijkstra算法很容易使用它。

http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm。

從算法描述看，如果圖數據結構是一組頂點，並且有可用的鄰點頂點信息，那麼看起來很方便。但我們如何實現這一目標？

任何人都可以幫助寫出該圖的示例數據結構，並解釋一下如何將它方便地鏈接到Dijkstra算法？

謝謝，

Answer 1

圖爲非常稀疏的（64個頂點，每一頂點具有至多8個邊緣）從而鄰接矩陣是一種浪費IMO。

這個更好的結構將adjacency list：

v1->v2,v3,v4,v5 
v2->v1,... 
... 

的想法的確持有Set<Vertex>，併爲Vertex類型有場：List<Vertex> neighbors，其中將包含所有的頂點的鄰居頂點。

在這種情況下，不需要額外的重量信息 - 因爲圖表未加權。

另外 - Dijkstra的算法在這裏是多餘的。同樣，該圖未加權 - 因此尋找最短路徑的更簡單（編程和理解）和更快（運行時）算法對於未加權圖是BFS。

Answer 2

由於只有64個圖塊，因此可以方便地將鄰接矩陣放入64位64位整數數組中。當然它很稀疏，但它也很小，所以如果它存在的話（指針與單個比特相比是相當大的），浪費也會很小。

從位向量提取指數列表也特別容易當它是稀疏，但你甚至不需要說 - 你可以讓前面bitvectors，而不是一個隊列，並「已訪問」設置可能是一個單一的位向量。

編輯：好吧其實你可能仍然需要它，如果您使用的伎倆，但隨後依然是它只是需要一對夫婦的快速操作，如bitscan和x &= x -1。