1

我需要制定一个算法来验证图中是否存在从节点x到节点的道路y。图中的边具有一系列附加的权限（如r, w, e等）。我的算法需要有|e| + |v|复杂性。我只能通过与它们之前的节点的边缘具有作为参数给出的特定权限集的节点。

例如，如果我有一组权限：r, w, e, g并且我将这些权限随机分布在边缘上，并且我将权限集作为我的搜索方法的参数：e, g，我只能通过边缘具有权限的节点e,g。

|e| + |v|如果 DFS 算法具有正确的时间复杂度，我该如何在时间复杂度上做到这一点，|e| + |v|并且我还需要搜索边缘是否具有所需的权限集，我认为这会增加复杂性。

4

1 回答 1

2

您需要应用广度优先搜索（与 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 以位向量的形式实现，因此与集合一样快。

于 2013-10-05T09:13:10.620 回答