邻接表的Java实现

Question

我有一个n*m矩阵，每个节点都有整数值，它是一个无向图。我想为它建立一个邻接表。我该怎么做？任何帮助都是非常感谢的。

Answer 1

以下是为问题创建邻接list.According的简单实现：

将有n个链表，每个链表的大小可变。

首先初始化整数链表的ArrayList：

ArrayList<LinkedList<Integer>> adj_list = new ArrayList<LinkedList<Integer>>();

然后，简单地通过重复以下代码来添加链表：

adj_list.add(new LinkedList<Integer>());

如果你用它来表示图，那么vertices.So的链接点的数目你必须重复上面的n(顶点数目)行n次。

现在假设您想要将数字3、4、5添加到第一个链接的lists.Do中，如下所示：

adj_list.get(0).add(3);
adj_list.get(0).add(4);
adj_list.get(0).add(5);

这仅仅意味着在你的图中有一条从顶点0到3,4,5的边。

Answer 2

首先，您的描述似乎是邻接矩阵，除非您说的是m by n。邻接矩阵总是正方形的，所以我们必须假设是m==n。矩阵元素是边权重。

图的邻接表表示(通常)是一组配对的数组adj。集合adj[i]包含对<j, w>当且仅当存在一个有向边i--w-->j，即从顶点i到在所表示的图中具有权w的j。

有了这个定义，很明显您必须从n空邻接集合adj[i]开始，然后迭代矩阵元素m[i][j] = w。对于其中的每一个，将<j, w>添加到adj[i]。

这方面的java代码非常琐碎，所以我就不写了。用邻接表表示的图的类型类似于ArrayList<HashMap<Integer, Integer>> adjacencies。对<j,w> in adj[i]是存储在哈希表adjacencies.get(i)中的映射j -> w。创建这种邻接关系的代码将是adjacencies.get(i).put(j, w)。

这种方法允许您通过迭代哈希表adjacencies.get(i)中的键来迭代与i相邻的顶点，使用w = adjacencies.get(i).get(j)查找给定边i--w-->j的权重，依此类推执行所有常见的图操作。