英文:
Best Way to create Adjacency List in java?
问题
一般来说，要在Java中创建n个节点的邻接表，我们需要创建一个额外的循环来用空列表填充该列表，如下所示-
for (int i = 0; i < n; i++)
adj.add(new ArrayList<>());
现在我们必须添加元素，但由于这个额外的循环，它会浪费时间。有没有其他更好的方法来创建邻接表？
英文:
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??????
答案1
得分: 1
如果我需要对图进行紧凑的表示，并且可以按顺序获取每个顶点的邻居，我通常会这样做：
// 顶点的连接邻接表按顺序连接在一起
ArrayList<Integer> adjList = new ArrayList<>();
// 每个顶点的邻接表在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());
}
现在，要获取任何顶点的邻居：
int s = vertex > 0 ? adjListEnds.get(vertex - 1) : 0;
int e = adjListEnds.get(vertex);
for (int i = s; i < e; ++i) {
processNeighbor(vertex, adjList.get(i));
}
当然，如果你希望它真正紧凑，那么你应该使用类似于保存原始int而不是Integer的数组列表。有时我会自己编写，有时我会使用GNU Trove。
英文:
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.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论