使用鄰接列表和鄰接矩陣的圖的大小？

Question

假設有2個網頁，並且平均每個網頁具有2個超鏈接。考慮如果在頂點所代表的網頁之間存在超鏈接，那麼每個網頁具有一個頂點和兩個頂點之間的邊的有向圖。使用鄰接矩陣表示圖表需要多少太字節？使用鄰接列表？我的問題是列表和矩陣之間的主要區別是什麼？

Answer 1

要回答你的問題，「矩陣的列表表示和矩陣表示之間的主要區別是什麼？」

A 列表表示通常是一個元組列表，其中列表的每個元素是一個節點，元組是連接到它的節點。說，我們有3個節點A，B，C，所以我們將具有長度3的列表說存在從A一個節點 - >B，然後在第A位置元件，比方說第一個元素，將包含節點B 。假設還有一個從A - >C的鏈接，第一個元素將包含B和C。鄰接列表所需的總空間是（表示節點的空間）*（邊的數量）。

另一方面，矩陣表示是一個矩陣，通常實現爲一個二維數組，其中每個節點都列在行和列軸上。如果在2個節點之間存在鏈接，則在矩陣中標記該點。例如，如果我們有3個節點A，B,C，我們有一個3x3陣列array。讓我們把A =指數0，B =指數1，C =指數2，並假設我們有一個鏈接從A - >B，然後在1在array[0][1]填寫。如果我們的圖表沒有定向，我們還會在array[1][0]處添加一個1。所需的總空間是每個鏈接所需空間N^2倍的節點數（可以用1位，0或1來完成），因此總數= N^2。

一個列表很適合稀疏圖，因爲它不需要任何額外的存儲空間。也就是說，不存在的鏈接不代表任何事物。相比之下，如果我們的圖表非常密集，則表示更好，因爲每個可能的鏈接僅由1位（0或1）表示。從上面的示例中可以看出，列表表示所需的總空間是的邊數的函數，而矩陣表示的空間是節點數的函數。

現在想想你的具體問題。你會有多少個節點？總邊緣？這看起來稀疏或密集？