java - 有没有更快的算法来构造这个图的邻接表？

Question

我的问题是找到一个更好的算法来填充邻接表。

规范:

G = (V , E ) //the graph
V ={w} //vertex in this case each vertex is an array     
E={⟨u,v⟩| u,v ∈V ∧ u>v} // edge only if u > v
u > v only if  foreach i u̸=v ∧ u[i]≥v[i]. // (u>v and v>w => u>w)

我天真的代码复杂度 O((v+1)*v/2) ≈ O(n^2) 是

private void riempiAdj() {
    for(int i=0;i<nodi.length;i++)
        for(int j=i+1;j<nodi.length;j++)
            if(nodi[i].eMaggiore(nodi[j]))
                nodi[i].adj.inserisci(nodi[j]);     
}

nodi 是顶点数组

adj是邻接表

AdjList.inserisci(Vertex t) 将顶点 t 添加到邻接表 O(1)

Vertex.eMaggiore(Vertex t) 在这个 > t O(1)

中返回 true

是否存在复杂度为 O(v) 或 O(v*log()v) 的算法？

Answer 1

在最坏的情况下，您尝试构建的图形中有 Θ(|V|²) 条边(边的总数为 0 + 1 + 2 + ... + |V|-1 = |V|(|V| - 1)/2), 因此任何显式构建图邻接表的算法都必须执行 Ω(|V|²) 在最坏的情况下也能正常工作，因为需要添加很多边。

由于这里的边有一个很好的模式，您可以想象创建某种延迟计算的邻接列表，它只在需要时创建边，尽管这是一个单独的问题。