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??????
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.
narray lists is not going to take much time unless you are talking of the order of millions. Your algorithm to process the graph needs to be efficient.