【十二】二分图


二分图指的是,把图中所有的点划分成两个集合。集合内部不存在边,边只存在两个集合之间。这个有点像鞋带的就是二分图。二分图的一个性质:一个图是二分图,当且仅当图中不包含奇数环(指环中的边的数量是奇数)。因为,我们很可以推测出当存在一个奇数环,我们不可能把一个点划分到两个集合中。图下就矛盾了。该点不能同时

【十一】最小生成树


最小生成树,指的属于该生成树的任意一个点,到生成树其他任意的点距离最短或权重最小或代价最小。普利姆算法(Prim)算法思想用dist维护距离最小生成树集合的最短距离,每次选择dist中,未在集合中且距离集合最短的点。然后,把这个点加入集合,用这个点更新其他点到集合的距离。整理的思想根dijkstra