2018 UESTC 图论培训B课程有哪些内容？
- 内容介绍
- 文章标签
- 相关推荐
本文共计797个文字，预计阅读时间需要4分钟。
B+-+天才金钱vs学霸周+大概念意：设定顶点和具有权重的边，求问最小生成树是否唯一。+思路分析：找出组成最小生成树所需的最少边数，以及可以构成最小生成树的边数，二者进行比较即可。“
B - 天才钱vs学霸周
大概题意：给定顶点和带有权值的边，求问最小生成树是否唯一。
思路分析：找出组成最小生成树需要的边数，以及可以构成最小生成树的边数，二者进行比较即可。
核心代码：
1.
结构体 node 记录边的相关信息。而 find 自然就是并查集的了，还有就是比较边的权值大小。
2.
Kruskal 算法。首先将每一个节点都设置为自己的根节点，其次就是将所有的边按权值大小进行排列。由于是找到最小生成树，那么遍历一遍即可。首先的 cnt1 是用来记录相同权值而且可以构成最小生成树的边数，注意如果不是同一个根节点，那么就记录下来；第二个则是找最小生成树的了，cnt2 用来记录最小生成树的边，其中的 pre[ u ]= v ，是将前驱节点改变，因为是加入到树中，如果 cnt2 == n-1 的话，就可以直接退出了。
本文共计797个文字，预计阅读时间需要4分钟。
B+-+天才金钱vs学霸周+大概念意：设定顶点和具有权重的边，求问最小生成树是否唯一。+思路分析：找出组成最小生成树所需的最少边数，以及可以构成最小生成树的边数，二者进行比较即可。“
B - 天才钱vs学霸周
大概题意：给定顶点和带有权值的边，求问最小生成树是否唯一。
思路分析：找出组成最小生成树需要的边数，以及可以构成最小生成树的边数，二者进行比较即可。
核心代码：
1.
结构体 node 记录边的相关信息。而 find 自然就是并查集的了，还有就是比较边的权值大小。
2.
Kruskal 算法。首先将每一个节点都设置为自己的根节点，其次就是将所有的边按权值大小进行排列。由于是找到最小生成树，那么遍历一遍即可。首先的 cnt1 是用来记录相同权值而且可以构成最小生成树的边数，注意如果不是同一个根节点，那么就记录下来；第二个则是找最小生成树的了，cnt2 用来记录最小生成树的边，其中的 pre[ u ]= v ，是将前驱节点改变，因为是加入到树中，如果 cnt2 == n-1 的话，就可以直接退出了。