algorithm - 在有向图中找到最大边不相交路径数

Question

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

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

所以图中有两条边不相交的路径，4->1->2并且5->1->3

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

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

Answer 1

计算所有路径：

• 从图中的所有边开始作为可用边的列表。
• 虽然仍有可用的边，但请继续提取路径并计算它们。

提取路径：

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