最大加权生成弱连通DAG的算法

Question

是否有一种算法可以找到在有向图中弱连接的最大权重跨越 DAG，其中每个切割都有弱连接的集合(从一个集合到另一个集合至少有一条有向路径)？或者这是一个NP难题？关于此主题的上一个问题没有指定 https://mathoverflow.net/questions/31864/algorithms-for-maximum-weighted-spanning-connected-dag-directed-acyclic-graph弱连接或强连接，所以我想更精确。

Answer 1

希望这还不算太晚。对于上述案例，很容易让 Kruskal 和 Prim 都失败。考虑一个 2 节点图:A --> B(权重 10)，B --> A(权重 6)，B --> A(权重 6)(是的:从 B 到 A 的两条边；图中没有定义排除了!)。 Kruskal 会先选择 A --> B 边然后卡住。 Prim 会选择从 B 到 A 的边之一，然后卡住。最大。加权无环子图是包含从 B 到 A 的两条边的子图。它是一个子图，并且是无环的!

最佳拉维