0

当我开始将图实现为邻接列表时，我注意到检查 v1 是否与 v2 相邻的运行时间是 O(V)

bool isAdjacent(int v1, int v2){    
    for(int i = 0; i < V; ++i){    
        if(this.graph[v1][i] == v2){ return true; }    
    }   
    return false;    
}

循环一直工作到 V（顶点数），所以它是 O(V)

我可以使用 HashSet 代替 ArrayList 或 vector 吗？

它是ArrayList< ArrayList<Integer> > graph;

或者Vector< Vector<Integer> > graph;

现在我想知道为什么我们不能创造

ArrayList<HashSet> 图；

这将使 bool isAdjacent(int v1, int v2); O(1) 因为在 HashSet 中搜索的顺序是 O(1) ？

如果 hashset 不能使用，因为它占用的内存比需要的多，那么二叉树呢？?

ArrayList< Binary_Tree > 图；

在这种情况下，搜索将比 O(lg V) 好于 O(V)

任何人都可以帮忙，为什么之前没有创建这个实现？

4

1 回答 1

0

是的，您可以（并且应该）为每个顶点使用 HashMap 来存储其邻居列表。

例如，对于 V1，创建以下 HashMap：

HashMap<Integer, Boolean> v1Adjacents = new HashMap<Integer, Boolean>();

在init您遍历每个顶点的相邻列表并对其进行更新时，很容易检查 V2 是否相邻：

if(v1Adjacents.get(V2) != null){
...
}
于 2013-09-22T08:18:58.923 回答