CODEWITHSUNDEEP
javaalgorithmgraphcomplexity-theory
matteo deotto
matteo deotto

Reputation: 35

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

My problem is to find a better algorithm to fill the adjacency list.

specs:

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)

my naive code whit complexity O((v+1)*v/2) ≈ O(n^2) is

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 is the array of vertex

adj is the adjacency list

AdjList.inserisci(Vertex t) add a vertex t into adjacency list O(1)

Vertex.eMaggiore(Vertex t) returns true in this > t O(1)

exist an algorithm whit complexity of O(v) or O(v*log()v)?

Upvotes: 1

Views: 408

Answers (1)

templatetypedef
templatetypedef

Reputation: 373482

In the worst case, the graph you're trying to build has Θ(|V|2) edges in it (the total number of edges is 0 + 1 + 2 + ... + |V|-1 = |V|(|V| - 1) / 2), so any algorithm that explicitly builds the adjacency list for the graph will necessarily have to do Ω(|V|2) work in the worst-case simply because that many edges need to be added.

Since there's a nice pattern to the edges here, you could conceivably create some sort of lazily-evaluated adjacency list that only creates the edges when they're needed, though that's a separate question.

Upvotes: 1

Related Questions