algorithm - 在此有向图中查找所有路径

Question

我最近发现了图形和算法，并试图解决涉及两种不同类型顶点的特定问题:用户和实体。详情如下:

• 图是有向的
• 我正在尝试找到从 A 到 B 的所有路径
• A 始终是用户
• B 可以是用户或实体
• 如果 B 是用户，则搜索的最大深度为 3 条边
• 如果 B 是实体，则最大深度为 2 条边
• 我不能遍历从用户出站的任何边，除非用户是 A

虽然图有两种类型的顶点，但它不是二部图。

到目前为止，我已经设法创建了一个图形对象，它包含一个顶点索引的邻接列表数组。邻接表基于链表。

我想我需要对“所有路径”算法进行某种变体，但我不太确定。此外，不确定我是否应该查看 DFS 或 BFS。

我在 PHP 工作，这使事情变得复杂，因为大多数示例都是用 Java 编写的。我真正想要的是伪代码。

有什么想法吗？谢谢!

Answer 1

听起来您正在遍历某种 LDAP 实现。如果您需要通用算法，只需使用 DFS，因为它更容易编码。除非深度会改变，否则这样做有点矫枉过正。

最通用的方式

 dfs(A,B):
     return dfs(A,B,1);

 dfs_(u,B,depth):
     if u == B:
          return u;

     if (u is User and depth > 3) or (u is Group and depth > 2):
          return None;       

     out = [];
     for children of thing:
          return max( dfs_(children,depth+1) ) # take the non-null one
     out.append(u);
     return out;