c++ - 如何在完整图的每条边上精确迭代一次？

Question

我想设置完整图中所有边的权重([a][b] = [b][a] = 随机整数)。为此，我编写了这段代码:

for (i = 0; i < n; i++)
{
    for (int j = 1; j < n; j++)
    {
        if (i != j)
        {
            w = std::rand() % 58 + 3;
            cout << i << ":" << j << " weight " << w << endl;
            graph[i][j] = graph[j][i] = w;
        }
    }
}

这里，n 是顶点的数量。不幸的是，这不是我想要的。我试图为每条边准确分配一个权重，但这段代码为大多数边分配了两个权重。例如，下面是上述代码中 n = 4 的示例输出:

0:1
0:2
0:3
1:2
1:3
2:1
2:3
3:1
3:2

请注意，0:3 和 3:0 都列出了，因此边上会有两个不同的权重。我只想列出这些边:

0:1
0:2
0:3
1:2
1:3
2:3

我怎样才能做到这一点？

Answer 1

做你想做的事情的标准方法 - 遍历所有对而不重复 - 是像这样更改 for 循环上的索引:

for (i = 0; i < n; i++)
{
    for (int j = i + 1; j < n; j++) // <--- Change here
    {
         ...
    }
}

这将正确地遍历所有不同节点对一次。它通过强制对中的第一个分量小于第二个分量来实现。

希望这对您有所帮助!