鄰接矩陣vs有向加權圖的鄰接列表

Question

作爲一個練習，我必須建立一個satnav系統，計劃從位置到位置的最短和最快的路線。它的速度必須儘可能快，而不要使用太多的內存。

我無法決定使用哪種結構來表示圖。我知道一個矩陣對於稠密圖更好，而對於稀疏圖，列表會更好。我更傾向於使用列表，因爲我假設添加頂點將是此程序中最重要的部分。

我只想得到一些你們家的意見。如果我將一個典型的路線圖看作一個以不同位置爲節點並且道路爲邊緣的圖形。你會認爲它稀疏或密集？在這種情況下哪種結構看起來更好？

Answer 1

我會去列表，因爲它只有1次投資。關於它的好處是它能夠比矩陣更快地遍歷所有相鄰的頂點，這是大多數最短路徑算法中重要且最常見的步驟。

所以矩陣是O（N）鄰接表只去O（k）其中k是相鄰頂點的數目。