查找此有向圖中的所有路徑

Question

我最近發現了圖和算法，並試圖解決涉及兩種不同類型頂點的特定問題：用戶和實體。詳情如下：

• 該圖是針對
• 我試圖找到一個所有路徑到B
• A總是用戶
• B可以是用戶或實體
• 如果B被用於搜索的用戶，最大深度爲3層的邊緣
• 如果B是一個實體，最大深度爲2層的邊緣
• 我不能穿過其從用戶的出站的任何邊緣，除非在U ser是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;