它是如何工作的?
Coddy Prim 算法:图算法 课程的第 3 课,共 9 课。
为每个顶点维护一个布尔值 inTree。开始时,树中只有顶点 0。前沿边是恰好有一个端点在树中的所有边,称为横跨边。
分步过程:
- 在所有横跨边中,选取权重最小的一条。
- 将它位于树外的端点加入树中,并将它的权重加到总和中。
- 重复此过程,直到树包含所有
n个顶点(需要n - 1条边)。
如果某一时刻不存在横跨边,但仍有顶点在树外,那么该图是不连通的。
示例,边为 [0,1,1, 1,2,2, 2,3,3, 0,3,4]:从 0 开始,选取 0-1(1),然后选取 1-2(2),再选取 2-3(3),总和为 6。
亲手试试
这节课没有代码挑战。
这节课包含一个小测验。开始学习即可作答,并记录你的进度。
Prim 算法:图算法中的所有课
自己练习: C 在线编译器