最有效的双指针设置算法

Question

在无向简单图G= ( v，E)的邻接列表表示中，每个边(u，v)有两个邻接列表条目:u的邻接列表中的v和V的邻接列表中的u。孪生指针是从邻接列表项到其孪生项的指针。如果E=m和x= n，内存大小不是一个约束，那么在每个邻接列表中，在每个条目中设置双指针的最有效算法的时间复杂度是多少？

1. Θ(n^2)
2. M+n(Θ)
3. Θ(m^2)
4. Θ(n^4)

我的尝试：

官方的答案是m+n(Θ)。通过跟踪BFS或DFS中的父节点，可以设置双指针。

你能给出最有效的算法来设置每个邻接列表中每个条目中的双指针吗？

Answer 1

由于内存不是一个约束，首先我们将创建一个数据结构，用于存储每个邻接列表的邻接项的地址。为了更快地检索，我们将创建一个大小指针(n2)的2D数组，它将指向图中的邻接条目。如果u和v之间有边，则我们的数据结构Au在u的邻接列表中包含v的邻接项的地址，否则它可能为空。要获得更清晰的图片，请参考下面给出的图像。

Answer 2

要表示一个图，如果我们使用矩阵，那么现在设置双指针的最有效算法的时间复杂度将是O(n2).，如果我们使用邻接列表，它将是：

2(Edges + Vertices) = 2(m+n) = O(m+n).

因此，选项(B)是正确的答案。