c - 设置孪生指针的最有效算法

Question

在无向简单图 G = (V, E) 的邻接表表示中，每条边 (u, v) 都有两个邻接表条目:[v] 在 u 的邻接表中，[u] 在v 的邻接列表。这些被称为彼此的孪生。孪生指针是从邻接表条目到它的孪生指针的指针。如果|E| =米和|V| = n，并且内存大小不是约束，在每个邻接表的每个条目中设置孪生指针的最有效算法的时间复杂度是多少？

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

---

我的尝试:

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

Can you give most efficient algorithm to set the twin pointer in each entry in each adjacency list?

Answer 1

由于内存在这里不是约束，首先我们将创建一个数据结构来存储每个邻接表的邻接条目的地址。为了更快地检索，我们将创建一个大小为 (n2) 的二维指针数组，它将指向图中的邻接项。如果u和v之间有一条边，那么我们的数据结构A[u][v]就包含了u的邻接表中v的邻接表项的地址。否则它可以为 NULL。更清晰的图片，请引用下面给出的图片。