如何使用prims算法为以下图形找到最小权重生成树 [英] How to find a minimum weight spanning tree for the following graph using prims algorithm
问题描述
Prim的算法
>寻找最小生成树的算法。
- 首先选择最小的边将它放到生成树中。
- 继续向树中已经存在的最小权重的树边添加树，不会形成一个简单的电路，这些边已经存在
- 当添加n-1个边时停止。
我知道你必须从节点A开始。还要给出一个
顺序的列表，其中添加了节点和/或边。
但是我不确定精确的步骤来找到最小权重生成树。
选择A中所有未访问的边
$ b = b
A -E = 2
A -F = 5
寻找最便宜的：A - B
从A和B中选择所有未访问的边
A - E = 2
A - F = 5
B - C = 1
B - E = 2
B - F = 4
寻找最便宜的：B-C
b从A，B和C中选择所有未访问的边
A - E = 2
A - F = 5
B - E = 2
B - F = 4 p>
C - E = 1
从B，C和E中选择所有未访问的边缘$ b $ C $ E
A - E = 2
A - F = 5
B - E = 2
B - F = 4
C - D = 4
E - D = 3
E - F = 1
查找最便宜的：E-F
节点D是唯一未访问的节点，因此它可以是; D -E或C -D。
最便宜= E - D：3
现在所有节点都已经访问，删除未使用的边
最小权重生成树看起来像这
Prim’s Algorithm
An algorithm for finding a minimum spanning tree.
- Begin by choosing any edge with smallest weight, putting it into the spanning tree.
- Successively add to the tree edges of minimum weight that are incident to a vertex already in the tree, never forming a simple circuit with those edges already in the tree.
- Stop when n − 1 edges have been added.
I know that you must start at node A. Also by giving a list of the order in which nodes and/or edges are added.
But im not sure on the exact steps to find the minimum weight spanning tree.
Select all unvisited edges from A
A - B = 2
A - E = 2
A - F = 5
Find cheapest : A - B
Select all unvisited edges from A and B
A - E = 2
A - F = 5
B - C = 1
B - E = 2
B - F = 4
Find cheapest : B - C
Select all unvisited edges from A, B and C
A - E = 2
A - F = 5
B - E = 2
B - F = 4
C - D = 4
C - E = 1
Find cheapest : C - E
Select all unvisited edges from A, B, C and E
A - E = 2
A - F = 5
B - E = 2
B - F = 4
C - D = 4
E - D = 3
E - F = 1
Find cheapest : E - F
Node D is the only unvisited node, so it can either be; D -E OR C - D.
Cheapest = E - D : 3
Now all nodes have been visited, remove unused edges
Minimum weight spanning tree would look like this
这篇关于如何使用prims算法为以下图形找到最小权重生成树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
