稀疏圖和密集圖之間的區別是什麼？

Question

我正在閱讀如何在計算機內存中表示圖形。我認爲它是理想的用鄰接矩陣表示鄰接表和稠密圖的稀疏圖。但我想了解稀疏圖和密集圖的主要區別？

Answer 1

密集圖是一個圖中的邊數接近最大邊數。 稀疏圖形是一個圖形，其中邊緣的數量接近邊緣的最小數量。稀疏圖可以是disconnected graph。

Answer 2

從here：

非正式地，用相對少的條邊的圖是稀疏的，並且與許多邊的圖是緻密的。定義（稀疏圖）：稀疏圖是G =（V，E）的圖，其中| E | = O（| V |）。定義（稠密圖）稠密圖是G =（V，E）的圖，其中| E | =Θ（| V | ）。

Answer 3

主要圖形積分特徵是頂點數V和邊數E.這兩個關係決定圖形是稀疏還是密集（維基頁面here）。

選擇圖表內存表示的全部理論是關於確定最佳訪問時間與內存佔用情況的權衡，考慮主題領域和使用細節。

除非不能容忍內存佔用，否則通常需要O（1）訪問時間（並因此將圖存儲爲密集的鄰接矩陣），在這種情況下，您可以選擇最合適的稀疏矩陣表示here）。

Answer 4

由於名稱表示稀疏圖是稀疏連接（例如：樹）。通常邊的數量在O（n）中，其中n是頂點的數量。因此，鄰接列表是優選的，因爲它們需要每個邊緣的恆定空間。

密集圖密集連接。這裏的邊數通常是O（n^2）。因此鄰接矩陣是優選的。

爲了進行比較，讓我們假設圖有1000個頂點。

無論圖形是稠密還是稀疏，鄰接矩陣都需要存儲1000^2 = 1,000,000個值。

如果圖形最小連接（即它是一棵樹），則鄰接列表需要存儲2,997個值。如果圖形完全連接，則需要存儲3,000,000個值。

Answer 5

在數學中，密集圖是其中邊的數量接近最大邊數的圖。相反，只有少量邊的圖是稀疏圖。稀疏圖和密集圖之間的區別是相當模糊的，並且取決於上下文。