圖形表示

給定圖形，我怎麼能表示它使用形式矩陣？我已經閱讀了很多教程，文章，幻燈片等，但我無法把我的頭圍繞它，我只需要那麼一點點的推動。圖形表示

alt text http://i39.tinypic.com/10xu4hv.png

2010-04-14 Carlos

每個字母數字組合是在你的圖形，即一個節點，從A0，A1，A2，...到F5，F6，F7。你的圖有48個（你的迷宮中有8列6行）節點，所以你需要一個48×48的矩陣。如果將它視爲布爾值，則除了兩個節點之間存在連接的位置（例如，兩個節點之間的連接）之外，您將設置所有字段爲false。 A0到A1意味着A0行在A1列中有一個真值，反之亦然（因爲你的圖是無向的）。

來源

2010-04-14 02:10:09

好的，非常感謝。你認爲在這種情況下使用鄰接列表會更好嗎？ Cuz 48x48似乎有點多餘（鏡像）並且效率低下。 – Carlos 2010-04-14 02:16:53

而這個矩陣本質上是對稱的，所以任何操作（和存儲，當然）只能在其中一個半部上完成。 – ysap 2010-04-14 02:18:34

每個頂點的度數最多爲4，因此鄰接列表將更有效。 – polygenelubricants 2010-04-14 02:22:33

下面是我對迷宮的第一水平線嘗試：

A0 A1 A2 A3 A4 A5 A6 A7 
A0 0 1 0 0 0 0 0 0 
A1 1 0 0 0 0 0 0 0 
A2 0 0 0 1 0 0 0 0 
A3 0 0 1 0 0 0 0 0 
A4 0 0 0 0 0 1 0 0 
A5 0 0 0 0 1 0 0 0 
A6 0 0 0 0 0 0 0 0 
A7 0 0 0 0 0 0 0 0

所以你可以從這個，你要和一個對稱矩陣，最終看到因您的邊緣，而且無向大自然其人口稀少。

編輯：矩陣VS列表

爲adjacency list的Wikipedia條目對每個算法的優點一些好點。

編輯：

Wikipedia entry for Adjacency Matrix：+）

來源

2010-04-14 02:17:50

感謝您的努力夥伴。我很困惑，因爲我這樣做的方式不對稱，所以我很確定它是錯的。但是當我想到A1 .... F7的想法時，我簡直無法相信它。當我問羅伯特時，在這種情況下矩陣或鄰接表中，你認爲什麼會更好？ – Carlos 2010-04-14 02:21:12

由於您的圖形的性質，低度和無向，我會認爲邊緣清單將是一個不錯的選擇。你想應用於數據結構的算法也應該影響你的決定。 – 2010-04-14 02:26:00

嘿，好友對不起，我錯誤地投票了，它不讓我取消投票，由於某種原因，我猜是因爲編輯，你可以編輯你的文章中的任何東西，我可以給你回報表決/投票。謝謝你，對不起。 – Carlos 2010-04-16 19:15:47

另一種方法是爲具有2點boolean矩陣命名Hor和Ver分別跟蹤水平和垂直運動的可能性。

Hor Matrix：尺寸：6x9
[X,YZ]表示從[X,Y]水平運動，以[X,Z]對實際板的方法可行。
-1表示邊界

例如：[A,01]是true，所以是[F,-10]。但[B,23]是false。

-10 01 12 23 34 45 56 67 7-1 
A 
B 
C 
D 
E 
F

同樣

Ver Matrix：尺寸：7x8
[XY,Z]表示從[X,Z]垂直移動的，以[Y,Z]對實際板的方法可行。
Capital o表示邊界。
示例：[DE,0]是true，因此[BC,7]也是如此。但是[CD,0]是false。

0 1 2 3 4 5 6 7 

OA 
AB 
BC 
CD 
DE 
EF 
FO

來源

2010-04-14 02:29:29 codaddict

回答

相關問題