0
$\begingroup$

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)?

$\endgroup$
1
$\begingroup$

Since the relation is transitive, in the worst case you have $\frac{|V|(|V|-1)}{2}$ edges and so, if you want to add all edges of the graph in the list, you cannot achieve better than $O(|V|^2)$

PS: This problem is similar to an Algorithm project in my University, what a coincidence! ( ͡° ͜ʖ ͡°)

$\endgroup$
  • 1
    $\begingroup$ maybe we are from the same university $\endgroup$ – matteo deotto Jun 29 '17 at 18:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.