java - 我对邻接列表到底是什么以及优先级队列是什么感到困惑。 - java

Question

我对什么是邻接列表和什么是优先级队列有点困惑。

我将使用数组列表创建邻接列表。我感到困惑的是邻接列表中保存的内容。

邻接列表是否用于显示所指向的内容？

例如，您有以下数据:

u v weight
1 4   6
2 5   7
3 7   1
1 3   2
1 2   5
2 2   9

对于邻接列表，它看起来像这样吗:

1 --->4---->3---->2
2 --->5---->2
3 --->7

其中每个相同的“u”(即u列下有三个1)都指向相应的“v”

Answer 1

图中节点的邻接列表为您提供了该节点的邻居的所有节点。基本上，邻接列表是节点表达“我可以从我自己开始到达这些其他节点”或“这是我连接到的节点”的方式。一个更具体的例子是，如果您想象一个城市(我们称之为 Graphville)有通往邻近其他城市的道路。那么 Graphville 就是节点，从 Graphville 可以直接到达(即不经过其他城市)的所有城市的列表将在 Graphville 的邻接列表中。

优先级队列是一种类似于常规队列的数据结构，不同之处在于每个元素都有一个与其关联的“优先级”。通常，优先级队列中优先级较高的元素先于优先级较低的元素处理。