如何利用普里姆算法找到如下圖的最小重量生成樹

Question

Prim算法

查找最小生成樹算法。

• 首先選擇權重最小的任意邊緣，將其放入生成樹中。
• 繼續向樹中已經存在的最小權重的樹邊添加樹，從不形成樹中已有邊的簡單電路。
• 停止添加n - 1個邊。

我知道你必須從節點A開始。同時給出一個 列表中添加節點和/或邊的順序。

但我不知道確切的步驟來找到最小權重生成樹。

Answer 1

選擇從所有未訪問的邊緣甲

A - B = 2

A - E = 2

A - F = 5

查找最便宜的：A - 乙

從A和B中選擇所有未訪問的邊緣

A - E = 2

A - F = 5

乙 - C = 1

乙 - E = 2

乙 - F = 4

查找最便宜的：B - C

從A，B和C中選擇所有未訪問的邊緣

A - E = 2

A - F = 5

乙 - E = 2

乙 - F = 4

Ç - d = 4

Ç - 電子= 1

查找最便宜的：C - 電子

選擇從A，B，C中的所有未訪問的邊緣和E

A - E = 2

A - F = 5

乙 - E = 2

乙 - F = 4

ç - d = 4

ë - d = 3

ë - F = 1

查找最便宜的：電子 - ˚F

節點d是唯一的未訪問過的節點，因此它可以是; D -E或C-D.

最便宜= E - d：3

現在所有的節點都被訪問，刪除未使用的邊緣

最小重量生成樹會是什麼樣子this