graph - 有向邻接表

Question

我以多种方式问过这个问题，首先是：

当您有邻接列表时，顺序是否重要？假设我有邻接列表 {1, 2, 5} 是否等同于 {2, 1, 5}？或者顺序是否意味着什么，因此这两个列表不等价？

我收到了几个答案，包括仅在图形是定向的并且顺序表示与顺时针相邻节点排列有关的情况下才重要..？我也被认为没有关系，但是他更希望根据权重（如果使用）对其进行排序，例如互联网的排序方式 - 页面排名算法。尽管我认为我传达了要点，但我不认为要准确地解释这些回答中的任何一个。任何想法表示赞赏。

此外，我已经改进了我的问题，如果得到回答，我认为会给我我所追求的确切答案：

假设我有一个有向图的邻接矩阵：

0 0 1 0

0 0 1 1

1 1 0 1

0 1 1 0

我被告知等效的邻接列表如下，并假设我的老师故意以这种方式列出它，而不是一些任意的重新排序 - 特别是如最后一个列表所示：

{ 2 }

{ 2, 3 }

{ 0, 1, 3 }

{ 2, 1 }

最后一个列表是 { 2, 1 }！等效邻接矩阵中的什么提醒我它应该是 { 2, 1 } 而不是 { 1, 2 }？

Answer 1

通常，不，邻接列表中的顺序无关紧要。

...除非明确说明。

由于各种原因，实现可能使列表实际排序：由于图形的创建方式，或者因为您希望以某种顺序处理顶点的邻居。但从概念上讲，顺序并不重要。

我相信在您的情况下，答案{2,1}是否，与{1,2}. 也许你的老师一开始写错了（比如{2,3}），改正后没有改变顺序。或者他/她想让你去思考订单是否重要。不确定，除非你问老师。

Answer 2

邻接表中节点的值是一个集合。集合是无序的。因此 {1,2} 与 {2,1} 相同。