在有向图中寻找边缘不相交路径的最大数量

Question

如何在有向图中找到最大数量的边缘不相交路径。该图未加权。 假设图就像是跟随...

1 - 2 , 1 - 3 , 4 - 1 , 5 - 1

所以没有在图中，两个边分离路径，4->1->2和5->1->3

我如何解决使用匹配算法的问题？

我的问题是...假设我有一个有向图（可能包含循环）。 如果我在一个节点上放置一个'警卫'，它就可以开始它的旅程。 即使是其他警卫已经去过的城市，警卫也可以多次访问任何城市。 目标是找到保护所有节点的最小数量的警卫。

Answer 1

计数的所有路径：

• 开始在图中为您提供边缘的列表中的所有边缘。
• 虽然仍然有可用边缘，请继续提取路径并对它们进行计数。

提取的路径：

• 删除第一个（或任何）可用的边缘，并呼吁它当前的路径。
• 尝试将当前路径的开始或结束与可用边的结束或开始匹配。
• 如果没有可用边匹配，则此路径结束。
• 如果可用边可以延长路径，则将其添加到当前路径中，从可用边列表中删除该边并继续尝试延长路径。