java 邻接表的Java实现
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/14783831/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Java implementation of adjacency list
提问by Jw123
I have a n*m matrix with integer value at each node and its an undirected graph. I want to build an adjacency list for it. How do I do that? Any help is much appreciated.
我在每个节点都有一个带有整数值的 *m 矩阵及其无向图。我想为它建立一个邻接表。我怎么做？任何帮助深表感谢。
回答by Sumeet
Here is a simple implementation for creating adjacency list.According to the problem:
下面是一个创建邻接表的简单实现。根据问题：
There will be n linked lists each of variable size.
将有 n 个链表，每个链表的大小各不相同。
First Initialize an ArrayList of linked lists of integers:
首先初始化一个整数链表的ArrayList：
ArrayList<LinkedList<Integer>> adj_list = new ArrayList<LinkedList<Integer>>();
Then simply add linked lists by repeating following code:
然后通过重复以下代码简单地添加链表：
adj_list.add(new LinkedList<Integer>());
If you are using it to represent graph,then no of linked lists=no of vertices.So you must repeat the above line n(no of vertices) times.
如果你用它来表示图形，那么没有链表=没有顶点。所以你必须重复上面的行n（没有顶点）次。
Say now you want to add numbers 3,4,5 to your first linked lists.Do the following:
现在假设您想将数字 3、4、5 添加到您的第一个链表中。执行以下操作：
adj_list.get(0).add(3);
adj_list.get(0).add(4);
adj_list.get(0).add(5);
It simply means there is an edge in your graph from vertex 0 to 3,4,5.
它只是意味着图中从顶点 0 到 3,4,5 有一条边。
回答by Gene
First your description seems to be of an adjacency matrix except you're saying mby n. Adjacency matrices are always square, so we must assume m==n. The matrix elements are the edge weights.
首先，您的描述似乎是一个邻接矩阵，除非您说的是mby n。邻接矩阵总是方阵，所以我们必须假设m==n。矩阵元素是边权重。
An adjacency list representation of a graph is (usually) an array adjof sets of pairs. The set adj[i]contains pair <j, w>iff there is a directed edge i--w-->j, i.e. from vertex ito jwith weight win the represented graph.
图的邻接表表示（通常）是一adj组对的数组。该集合adj[i]包含对<j, w>如果有一个有向边i--w-->j，即从顶点i到在所表示的图中j具有权重w。
With this definition, it's clear you must start with nempty adjacency sets adj[i]and then iterate over the matrix elements m[i][j] = w. For each of these add <j, w>to adj[i].
有了这个定义，很明显你必须从n空的邻接集开始，adj[i]然后遍历矩阵元素m[i][j] = w。对于这些中的每一个，添加<j, w>到adj[i].
The java code for this is pretty trivial, so I won't write it. The type for a graph represented with adjacency lists is something like ArrayList<HashMap<Integer, Integer>> adjacencies. The pairs <j,w> in adj[i]are mappings j -> wstored in the hash table adjacencies.get(i). The code to create such an adjacency will be adjacencies.get(i).put(j, w).
这个java代码很琐碎，我就不写了。用邻接表表示的图的类型类似于ArrayList<HashMap<Integer, Integer>> adjacencies. 这些对<j,w> in adj[i]是j -> w存储在哈希表中的映射adjacencies.get(i)。创建这种邻接的代码将是adjacencies.get(i).put(j, w).
This method allows you to iterate over the vertices adjacent to iby iterating over keys in the hash table adjacencies.get(i), look up the weight of a given edge i--w-->jwith w = adjacencies.get(i).get(j), and so on for all the usual graph operations.
这种方法允许你遍历相邻顶点i通过哈希表遍历键adjacencies.get(i)，查找一个给定边的权重i--w-->j与w = adjacencies.get(i).get(j)，等所有常用的图形操作。
