CODEWITHSUNDEEP
javaalgorithmgraph
Sricharan
Sricharan

Reputation: 1

Best Way to create Adjacency List in java?

In general, to create Adjacency list of n node in java, we need to create an extra loop to fill the list with empty list like below-

for(int i=0;i<n;i++)
    adj.add(new ArrayList<>());

Now we had to had to add the elements,but because of this extra loop its wasting the time. Is there any other best way to create the adjacency list??????

Upvotes: 0

Views: 1703

Answers (1)

Matt Timmermans
Matt Timmermans

Reputation: 59184

If I need to make a compact representation of a graph, and I can get the neighbors for each vertex in sequence, I often do it like this:

//Concatenated adjacency lists for each vertex in order
ArrayList<Integer> adjList = new ArrayList<>();

//For each vertex, the end of its adjacency list in adjList
ArrayList<Integer> adjListEnds = new ArrayList<>();

for (int i=0; i<num_vertexes; ++i) {
    for (int adj : getNeighbors(i)) {
        adjList.add(adj);
    }
    adjListEnds.add(adjList.size());
}

Now, to get the neighbors of any vertex:

int s = vertex>0 ? adjListEnds.get(vertex-1) : 0;
int e = adjListEnds.get(vertex);
for (int i = s; i<e; ++i) {
    processNeighbor(vertext, adjList.get(i));
}

Of course, if you want it to be really compact, then you should use something like an array list that holds primitive ints instead of Integers. Sometimes I roll my own. Sometimes I use gnu trove.

Upvotes: 1

Related Questions