lea*_*ner 4 graph
有向图G的树状结构是有根树,使得存在从图中的根到每个其他顶点的有向路径.提供一种有效且正确的算法来测试G是否包含树枝及其时间复杂度.
我只能考虑从每个节点运行DFS/BFS,直到其中一个DFS覆盖所有节点.我想过使用最小生成树算法,但这也仅适用于非定向图
有没有其他有效的算法呢？
我发现了一个跟进问题,哪个状态有一个O(n + m)算法,任何人都可以帮助解决这个问题吗？
ral*_*aul 6
您正在寻找的是所谓的Edmond算法.最小生成树算法不适用于有向图,但这是一个想法.当图形指向并且树状结构是您上面描述的时候,MST问题变成了树状问题.
天真的复杂性是O(EV),就像Prim的无向MST问题算法一样,但我确信它的实现速度更快.
有关更多信息,请查看Wiki页面:
埃德蒙兹算法
归档时间：
11 年，10 月 前
查看次数：
1411 次
最近记录：
9 年，7 月 前