加权有向图的Prim算法

Question

我正在学习最小生成树。我研究了Prim的加权有向图算法。

算法简单

• 您有两组顶点：已访问和未访问
• 将所有边的距离设置为无穷远
• 从未访问集合中的任意顶点开始并探索其边
• 在所有边中，如果目标顶点没有被访问，并且如果边的权重小于目标顶点的距离，则用该边的权重更新目标顶点的距离
• 选择距离最小的未访问顶点，然后再进行一次，直到所有顶点都访问完

相信通过以上算法，能够在所有的生成树中找到代价最小的生成树，即最小生成树。

顶点是{v1,v2,v3,v4,v5}，边的权
(x,y):w=>
(v1,v2):8
(v1,v3):15
(v1,v4):7
(v2,v5):4
(v4,v5):7

(v4,v5):7

首先我探索v1，它有v2,v3,v4的边，所以图变成
顶点v1被访问，并且（顶点，距离）=>
(v2,8)
(v3,15)
(v4,7)

现在v4有最小的距离，即7所以我探索v4，它有v5的边，所以发生以下修改
顶点v4被访问，并且（顶点，距离）=>(v5,7)

在所有的v5中，距离最小，也就是7，所以我探索v5，它没有任何边，所以我只标记它已访问

v5顶点被访问

现在，困惑从这里开始

Answer 1

首先我要提到的是，Prim的算法只适用于无向图，所以如果我们认为图是无向的，这是算法在您的情况下的一步一步的进展：

你应该考虑到在有向图中找到最小生成树是不可能的，然而对于有向图，最接近MST的概念是最小代价树形。