求连通网的最小生成树的prim算法:集合VT,ET分别放顶点和边,初始确定集合VT,ET之后,接下来需要步骤重复()n-1次
时间: 2024-02-19 16:00:06 浏览: 35
最小生成树prim算法.pdf
在prim算法中,步骤需要重复n-1次,其中n为连通网中顶点的数量。具体步骤如下:
1. 从VT集合中选择一个顶点作为起始顶点,加入VT集合中。
2. 将与起始顶点相邻的所有边加入ET集合中。
3. 从ET集合中选择权值最小的边,并找到该边所连的顶点v。
4. 如果v已经在VT集合中,则继续选择下一条边;否则,将v加入VT集合中,并将与v相邻的所有边加入ET集合中。
5. 重复步骤3和步骤4,直到VT集合中包含了所有顶点,此时ET集合中包含的边就是连通网的最小生成树。
由于最小生成树包含n个顶点,因此需要重复n-1次步骤。每次选择一条边,因此总共需要选择n-1条边。
阅读全文