最小树形图和朱刘算法
好久没写博客了,不过修了好多以前文章的锅。
描述
给出一张 \(n\) 个点 \(m\) 条带权边的有向图,钦定一个根 \(r\),求以 \(r\) 为根的最小有向生成树(Minimum Directed Spanning Tree,MDST,也即最小树形图)。
有向生成树(DST)即要求边是从父亲连向儿子。
下面给出的算法可以在 \(O(n\times m)\) 的复杂度内求解,另外存在更优的算法。
好久没写博客了,不过修了好多以前文章的锅。
给出一张 \(n\) 个点 \(m\) 条带权边的有向图,钦定一个根 \(r\),求以 \(r\) 为根的最小有向生成树(Minimum Directed Spanning Tree,MDST,也即最小树形图)。
有向生成树(DST)即要求边是从父亲连向儿子。
下面给出的算法可以在 \(O(n\times m)\) 的复杂度内求解,另外存在更优的算法。