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

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) returns true in this > t O(1)

存在一个复杂度为 O(v) 或 O(v*log()v)?[=16= 的算法]

Answer 1

在最坏的情况下，您要构建的图形中有 Θ(|V|²) 条边（边的总数为 0 + 1 + 2 + ... + |V|-1 = |V|(|V| - 1) / 2), 所以任何显式构建图邻接表的算法都必须做 Ω(|V|²) 在最坏的情况下工作只是因为需要添加很多边。

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

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

Is there a faster algorithm for constructing the adjacency list of this graph?

java

algorithm

complexity-theory

graph