實現無向加權圖

Question

我想知道什麼是實現無向加權圖的有效方式。我想在它上面執行Prims和Kruskal算法。我知道鄰接名單，但不會浪費記憶;例如。讓假設我有兩個頂點A和B與重量「X」的邊連接，所以我需要在相鄰列表中添加兩個條目：

A,B,x 
B,A,x 

我缺少的東西？

Answer 1

鄰接列表是實現圖的內存有效方式，而不是鄰接矩陣。

其實你在這裏有兩個選擇。

• 如果你想要更少的時間和更多的記憶，你應該做你寫的東西。
• 如果你想要更多的時間和更少的內存，你可以實現你的邊緣A,B,x其中A>B。但是，在獲取任何頂點的相鄰頂點時，您會花費大量時間。

這是你的電話。但是如果你處理的節點數不到上百萬，第二顆子彈並不是首選。

Answer 2

因爲圖是無向我想你需要的節點A和B

之間只有一個 邊緣