存储在单个向量中的三角形邻接矩阵的正向和逆向索引

我有一张带有点的地图，我想知道每个点之间的距离。 （这可能称为无向循环图）。由于点很多，我的存储空间有限，所以阵列需要很密集。对于 4 个城市（n = 4），我需要 6 个索引来映射这 4 个城市：

Index #, City1 <> City2 
=========================
Index #0, 1 <> 2
Index #1, 1 <> 3
Index #2, 1 <> 4
Index #3, 2 <> 3 
Index #4, 2 <> 4
Index #5, 3 <> 4

Index total = 6
Cities = 4

或者用三角形来看：

(1-2)(1-3)(1-4)
(2-3)(2-4)
(3-4)

这（方向/边缘——所有道路都是双向的）。如果我有 260 个城市，我需要 33670 个索引，而不是 260x260 或 67600 个索引。例如：对于 4 个城市，索引 #4 是从 2 到 4 的距离（或“翻转”为 4 到 2）。
注意：上面是一个示例，其中 1 到每个其他城市，然后 2 到每个城市，除了 1, ... ，倒数第二个城市到最后一个城市（n-1 到 n）。其他“形状”可供讨论（例如相反的顺序或什至其他方案）。

如果我有 260 个城市，我如何知道从零开始的索引 #i 指的是哪些城市？我可以使用 2 个公式从索引中获取 city1 和 city2 并再次返回吗？ （例如：索引#33333 是 234 到/从 249）。

getIndex(city1, city2) // returns index
getCities(Index)       // returns city1, city2

用一些高中代数推导这些并不难。但计算它们是相当昂贵的。

Let (i,j)位于城市的边缘i >= 1到城市j > i然后让p >= 0是表示线性化三角矩阵的向量中的相应索引。然后

p = j * (j - 3) / 2 + i

根据这个公式，线性布局为：

(i,j) = (1,2)(1,3)(2,3)(1,4)(2,4)(3,4)...
  p   =   0    1    2    3    4    5 ...

例如。为了(1,2)我们有2 * (2 - 3) / 2 + 1 == 0正如你所期望的。而对于(2,4) it's 4 * (4 - 3) / 2 + 2 == 4.

要想走另一条路，

j = floor((3 + sqrt(8 * p + 1)) / 2)
i = p - j * (j - 3) / 2

For p == 0, j = floor((3 + sqrt(1)) / 2) == 2. Then i = 0 - 2 * (2 - 3) / 2 == 1. For p == 4, it's j = floor((3 + sqrt(33)) / 2) = 4, then i = 4 - 4 * (4 - 3) / 2 = 2.

平方根可能就是您不经常看到使用此技术的原因。请注意，整数平方根可以正常工作，在某些情况下可能比浮点数更快。

总而言之，使用指向长度不断增加的行的指针数组可能更快、更简单，并且几乎具有同样的存储效率。

Addition

事实证明毕竟有is消除平方根的一种方法。我们将三角形阵列切成两半，并将这些碎片拼成一个矩形。对于一个图表n = 5顶点：

j                             p = 0   1   2   3   4
=  ---                           -------------------
2 | a |                         | a $ j | i | h | g |                           
   -------                       ----===------------
3 | b | c |        is arranged: | b | c $ f | e | d |
   -----------                   -------------------
4 | d | e | f |                   5   6   7   8   9
   ---------------
5 | g | h | i | j |
   ---------------
i = 1   2   3   4

其中右侧是写成两行的向量。

现在对于奇数 n，

    { n*j + i - k,                     if j < n/2 + 2
    {    where k = 2*n+1
p = {
    { kk - (n*j + i)                   otherwise
    {    where kk = (floor(n/2)+4)*n

常数k and kk可以在创建数组时计算一次。

要走另一条路，让j' = floor(p/n) and i' = p mod n. Then

i = i' + 1,  j = j' + 2                 if j' <= i'
i = n - i',  j = n - j'                 othewise

我会让你算出偶数n case.

由于每种情况下都有 2 路分支，因此它们只比普通的 2d 数组索引贵一点。