0

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

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

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

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

我认为我需要对所有路径算法进行某种变体，但我不太确定。另外，不确定我应该看 DFS 还是 BFS。

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

有任何想法吗？谢谢！

4

1 回答 1

2

听起来您正在遍历某种 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;
于 2012-12-06T00:54:34.047 回答