1. 首頁
  2. 問答
  3. 稀疏圖和密集圖之間的區別是什麼？

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

2012-09-26 108 views
34

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

來源

2012-09-26 Geek

+5

（http://en.wikipedia.org/wiki/Dense_graph）有足夠的信息 – Imposter

回答

26

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

來源

2012-09-26 10:00:05 CAMOBAP

+1

我認爲如果一個包含n個頂點的圖被認爲是稀疏的，如果它具有O（n）或更少的邊。 –

+1

相反，具有n個頂點的曲線圖是緻密的，如果邊緣的數目爲O（n^2） – JayJay

9

從here：

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

來源

2012-09-26 10:01:27 Ryhan

3

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

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

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

來源

2012-09-26 10:02:04 bobah

28

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

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

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

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

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

來源

2012-09-26 10:04:54 ElKamina

1

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

來源

2017-02-17 00:07:29 harrypotter0

+0

稀疏圖的幾個例子是：其中的交叉點是頂點和道路交通 和道路網絡是邊緣。對於這樣的網絡，道路的數量並不顯着大於交叉點的數量（換言之，E〜= c * V，其中c在2-3的範圍內）。 儘管在許多情況下真實世界的圖很稀疏，但有可能創建高度密集的加權圖，其邊緣權重表示某種關係 - 例如，如果兩個人同時訪問同一商店，則邊緣權重較大或者在同一家咖啡店喝咖啡。 – harrypotter0

+0

另一個例子可能是採用稀疏圖形的「子圖」來表示一個高度關聯人羣。 – harrypotter0

相關問題

 相關問題