向圖對戰關聯數組

Question

我已經讀了有向圖。我設法得到了一個在我的應用程序中工作的抽象圖形數據類型，但我並沒有覺得它非常直觀，並且正在考慮用一個普通的多維數組替換它。

我的圖是稀疏和非循環。每個頂點都可以從一個特定的「主」頂點到達。如果它是一棵樹，這個主頂點將是'根'。它是一個社交網絡，這個主頂點將是'我'。

雖然我的圖可以具有頂點成千上萬它具有有限的深度：任意兩個節點之間的最大距離爲3層的邊緣。

底層數據表示是鄰接表。一個小例子是這樣的：

Head | Tails 
-------------- 
    1 | 2, 3, 4 
    2 | 5 
    3 | 5 
    4 | 5 
    5 | 6 

如果我用一個普通的多維數組，而不是我的圖形數據類型，它會是這個樣子：現在

$me[1][2][5][6] 
$me[1][3][5][6] 
$me[1][4][5][6] 

，主我希望能夠用這個圖表做的事情是：

1. 導航它作爲一個層次結構。我意識到某些子頂點將具有多個類別（例如＃5），但這正是我想要的特定用例。對於這一點我看不出數組和圖之間有什麼真正的區別。
2. 萊它作爲一個列表（按字母順序排列，根據頂點名），沒有重複。我可能會做一個DFS，在我去的時候標記訪問過的頂點，以避免多次探索它們。但據我所見，這可以使用圖形或陣列來實現，並且成本相同。
3. 對任何給定的一對點進行「所有路徑」分析。因爲我想要'所有路徑'（也就是說，我不是簡單地檢查可達性），在我看來，我必須遍歷整個圖形，並且再次看到圖形上沒有數組優勢。

我的感覺是我失去了一些東西，但我不能把它放在手指上。你可以嗎？？？任何想法，建議，見解或建議都會受到感謝......（順便說一句，我使用的是PHP，數據源是關係數據庫，但我認爲這不會有什麼真正的區別）。

謝謝！

Answer 1

看起來您的數據結構過於複雜。如果表示一個有向圖作爲一個多維陣列中，它幾乎總是尺寸的兩個，使得

$array[$x][$y] 

是一個布爾值，該值是TRUE，如果且僅當存在從節點$ X的邊緣到節點$ Y在圖中。在你的例子中，如果是例如

$array[1][2] = TRUE 
$array[1][5] = FALSE 

但是對於稀疏圖，使用這種布爾矩陣表示法通常不是很好。通常情況下，您將有一個一維數組，將每個節點映射到一組邊，例如邊。

$array[1] = { 2, 3, 4 } 

其中{...}表示某種無序的集合數據結構，其可以是例如，二叉搜索樹或散列集（散列表）。

該數據結構使您可以快速找到其中有給定節點，這是圖形算法的關鍵特徵弧的節點。

有時候你也希望能夠向後遍歷你的圖形;在這種情況下，您可能會有另一個將節點映射到其前任列表的陣列。需要理解

Answer 2

一件事是，一個向圖（或有向圖）是一種概念，而一個關聯數組是數據結構。

有向圖概念的實例可以存儲在許多不同的數據結構，其中你可以找到最常見的對這個wikipedia page。

我不知道你與你的多維數組做什麼......存儲的所有路徑？你最終會面臨N³空間的複雜性，並且會造成麻煩。基於樹的結構至少會更有效率。

我們要與您的圖形做的事情：

1. 導航作爲一個層次。基本的圖形概念不允許在層次結構中上升，但是您也可以輕鬆存儲反轉圖形（尤其是使用基於矩陣的表示形式時，只需使用3個值而不是2個 - 前進，後退和無）。
2. 奠定它作爲一個清單，根據名稱。您必須將該名稱存儲在某個地方（無論是在側面地圖中還是在頂點對象中），但不應該比根據名稱對其他東西進行排序更困難。
3. 做一個 '所有路徑' 分析。通過DP和路徑的共享表示，您可能會擺脫線性複雜性（在路徑數量方面）。