您需要应用广度优先搜索(与 DFS 不同,它会找到最短路径)稍微修改它以仅考虑具有所需权限的节点。
这是伪代码,我相信你可以把它翻译成Java:
procedure BFS(G,v):
create a queue Q
create a set V
enqueue v onto Q
add v to V
while Q is not empty:
t ‹ Q.dequeue()
if t is what we are looking for:
return t
for all edges e in G.adjacentEdges(t) do
u ‹ G.adjacentVertex(t,e)
if u is not in V and t.hasRights(allowedRights):
add u to V
enqueue u onto Q
return none
它与维基百科上的不同之处仅在于检查t.hasRights(allowedRights)
条件。
使用 Java HashSet,可以在 O(1) 时间内轻松检查一组权限,不会增加 BFS 算法的 E+V 复杂性(假设可用权限的数量是恒定的)。
在每个节点中存储一组权限,然后检查是否所有需要的权限都在集合中(HashSet.contains(Object)为 O(1))。
此外,您可以将您的权利表示为enum
并使用EnumSet来存储正确的集合。EnumSet 以位向量的形式实现,因此与集合一样快。