Menu
CoddyTech

它是如何工作的?

Coddy Prim 算法:图算法 课程的第 3 课,共 9 课。

为每个顶点维护一个布尔值 inTree。开始时,树中只有顶点 0。前沿边是恰好有一个端点在树中的所有边,称为横跨边。

分步过程:

  1. 在所有横跨边中,选取权重最小的一条。
  2. 将它位于树外的端点加入树中,并将它的权重加到总和中。
  3. 重复此过程,直到树包含所有 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。

亲手试试

这节课没有代码挑战。

quiz icon自我测试

这节课包含一个小测验。开始学习即可作答,并记录你的进度。

Prim 算法:图算法中的所有课

自己练习: C 在线编译器