java - 邻接表的Java实现

Question

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

Answer 1

下面是一个创建邻接表的简单实现。根据问题：

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

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

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

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

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

如果你用它来表示图形，那么没有链表=没有顶点。所以你必须重复上面的行n（顶点数）次。

现在假设您想将数字 3,4,5 添加到您的第一个链接列表中。执行以下操作：

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

它只是意味着您的图中从顶点 0 到 3、4、5 有一条边。

Answer 2

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

图的邻接表表示（通常）是一adj组对的数组。如果在表示的图中存在有向边，即从顶点到具有权重，则该集合adj[i]包含对。<j, w>i--w-->jijw

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

这个java代码很简单，我就不写了。用邻接表表示的图的类型类似于ArrayList<HashMap<Integer, Integer>> adjacencies. 这些对是存储在哈希表中的<j,w> in adj[i]映射。创建这种邻接的代码将是. j -> wadjacencies.get(i)adjacencies.get(i).put(j, w)

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