Prim的算法通過鄰接矩陣

Question

我想使用Prim的算法來優化輸水管道問題。當存在與相鄰頂點相鄰的邊時，我非常困惑如何初始化鄰接矩陣。我認爲每當邊緣存在時都要加重。然而，w（Vi，Vj）本身看起來是一個權重矩陣。那麼，爲什麼我首先需要A {Vi，Vj}。

我所要做的就是編寫一個算法方法，然後繼續編寫程序。請建議如果以下是好的？

1. 設置鄰接矩陣A {Vi，Vj}。這裏Vi包含所有訪問過的節點，而Vj包含所有訪問過的Vi的相鄰節點。下面的矩陣將存儲所有通過一定距離與相鄰的一對房屋連接的房屋。我很困惑THA

   爲各個VI：= 1到n做//聖維特是第i個頂點，其存儲一對房子 爲每個VJ：= 1到n做// Vjth是相鄰對房子的一些重量 如果（Vi和VJ之間存在邊緣），那麼 設置 A {VI中，VJ}以w（六，VJ） 否則如果（邊緣不Vi和VJ之間存在）那麼 Set A [Vi，Vj]：= 0

2. 計算最小生成樹。

3. 輸出：顯示所需的總輸水管道。

Answer 1

在您的問題中的圖算法中，如果給出權重，除了權重外，通常不會顯式編碼鄰接關係。相反，該圖被認爲是完整的圖（即evey頂點與任何其他頂點相鄰），但是對於初始圖中的非相鄰頂點u,v，權重被編碼爲「無窮大」，編碼爲最大值所使用的數據類型，在計算等中被識別的一些負值。使用這種方法，不可行邊將永遠不會被考慮到，因爲它們比初始問題的任何可行解決方案都更昂貴。