查找不包含负循环的强连通子图

作者: 狗头军师
发布时间: 2025-02-05 01:09:29 (15天前)

2 条回复

1#
回复此人
v-star*위위 | 2020-08-24 15-44

这是一个幼稚的解决方案，它有合理的机会找到在多项式时间内没有负循环的强连通生成子图。但是强调不能保证找到一个。将所有权重变为负数。现在，使用福特-贝尔曼或弗洛伊德-沃歇尔来寻找一个负周期。在原始图中，这实际上是一个正周期。现在，我们在循环中选择一个顶点，然后将其他顶点收缩到该顶点。连接到/来自已移除顶点的边被表示沿该边并围绕循环行进至我们保留的边的边替换。如果最终在两个顶点之间具有多个边，则仅保留最佳的一个。在新的，较小的图形上重复该练习。此算法在保证的多项式时间内运行（每次迭代均在多项式时间内运行，并删除至少一个顶点）。如果它设法将图缩小到一个点，那么您只需向后走，发现实际上找到了一个没有负周期的强连接的生成图。但是，如果这样做失败，则不能保证没有一个。您只是没有找到它。

编辑

登录后才能参与评论