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

-1

Graph 如何利用普里姆算法找到如下图的最小重量生成树

Prim算法

查找最小生成树算法。

首先选择权重最小的任意边缘，将其放入生成树中。
继续向树中已经存在的最小权重的树边添加树，从不形成树中已有边的简单电路。
停止添加n - 1个边。

我知道你必须从节点A开始。同时给出一个列表中添加节点和/或边的顺序。

但我不知道确切的步骤来找到最小权重生成树。

来源

2017-05-05 la3anato

为什么你认为你需要在节点启动一个？这不是算法中的第一步所说的，是吗？ – beaker

@beaker这是我被告知的，当你使用prim算法时，你必须从节点A开始，至少对于这个问题。 – la3anato

然后它不是Prim的算法。如果你被要求做别的事情，那么我建议你跟你的助教谈谈，并问他们你是否正确地遵循他们的指示。 – beaker

选择从所有未访问的边缘甲

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

来源

2017-05-06 12:48:53 la3anato

多数民众赞成多么我会这样做，但我不知道如果它的正确答案 – la3anato

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

回答

相关问题