密集和稀疏運行時間

Question

我想製作一個程序，它可以在圖形中找到最短路徑。例如，我製作100個頂點和100個邊，然後再製作100個頂點和500個邊，並測量它們的運行時間。

我的問題是我該如何理解這是密集還是稀疏？

Answer 1

密度是圖中邊數與具有相同頂點集的完整圖中邊數的比值。

這兩個圖都相當稀疏，儘管第一個圖比較稀疏。

通常的曲線圖的密度用於決定使用什麼樣的數據結構來表示的曲線圖

• 一種adjacency matrix使得用於密集圖形感其中列舉出邊緣是​​不常見的操作。
• Edge lists對於稀疏圖或經常進行枚舉出站邊緣有意義。

雖然這是一個折衷。隨着頂點數的增加，鄰接圖佔用更多的內存，但獲取兩個頂點之間邊的列表很快。掃描所有外出邊緣速度很慢。

隨着頂點數量增加，邊緣列表佔用較少的內存，查找兩個頂點之間的邊更慢，但枚舉出邊更快。

Answer 2

不幸的是，「密集」和「稀疏」不容易適用於單個圖形。通常情況下，稀疏圖的邊緣密度爲o（n^2），密度圖的邊緣密度不是o（n^2）。但是，這不能應用於單個圖表，而只是一個大小增長到無限大的圖表族。你可以使用的「啓發式」是：如果我在n個頂點（或n個頂點上的一族圖）上有一個圖，我有c * n個邊（c是一個常數，相對較小），例如2n邊緣，或3n邊緣，或7n邊緣？如果是，那麼你有一個稀疏的圖。否則，我有類似1/2 n^2邊緣的東西嗎？或1/3 n^2邊緣？或1/10 n^2邊緣？如果是的話，它很密集。

在您的示例中，100個頂點和500個邊相當稀疏，因爲5 * n個邊看起來比1/200 n^2更「合理」。