vka*_*l11 0 algorithm graph subgraph directed-acyclic-graphs
是否存在一种算法来查找跨越DAG的最大权重,该DAG在有向图中弱连接,其中每个切割具有弱连接的集合(从一个集合到另一个集合至少有一个有向路径)？或者这是一个NP难题？关于这个主题的上一个问题没有指定https://mathoverflow.net/questions/31864/algorithms-for-maximum-weighted-spanning-connected-dag-directed-acyclic-graph弱或强连接,所以我想成为更确切.
小智 5
希望这不会太晚.对于上述案例,Kruskal和Prim很容易失败.考虑一个2节点图:A - > B(权重10),B - > A(权重6),B - > A(权重6)(是:从B到A的两条边;图中没有任何内容)排除了!).Kruskal会首先选择A - > B边缘并卡住.Prim会选择B中的一条边到A,然后卡住.最大 加权非循环子图是包含从B到A的边的一个.它是一个子图,它是非循环的!
最好的拉维