0

如果我决定使用“邻接矩阵”表示来表示图形，我怎么知道矩阵的大小应该是多少？

我见过的所有代码示例，都假设给了Graph对象大小来初始化矩阵，但我不清楚这个大小是从哪里来的。
我的意思是我假设要构建一个图形，该图形的数据是从文件中加载的，最好的方法是在您读取文件时创建图形（到目前为止是吗？）。
使用列表的替代表示非常容易。
但是在matrix实际加载文件之前，我们不知道顶点的数量。我不相信我们首先读取文件（可能包含数百万个顶点）然后构建图形。在我看来，这就像双重处理。

那么通常/最好的方法是什么？

注意：我知道使用列表的好处，但是由于大多数文档都说在密集图上，使用矩阵是可以接受的（但不适用于稀疏），我试图了解使用matrix表示的程序是如何正确实现的。

4

3 回答 3

1

the usual/best way is given in the comments: you reallocate and copy. if you scale the size each time (eg double) the amortized (average) cost comes out as O(n), as far as i remember. this is how, for example, python has lists that grow to be any size you need. it's completely standard/common.

[i'm not really posting for points here; just frustrated that the answers in comments are what you need, but that you may not be paying attention to them or understanding them]

于 2012-05-18T21:37:34.940 回答
1

如果输入格式在您的控制之下，您可以很好地估计大小。在下面的示例中，所有值都具有固定长度（6 个字符），左侧填充 0。这意味着每行的大小为 22 个字节。当您将文件大小除以 22 时，您会得到矩阵大小的近似值。如果图是完整的，则文件大小等于nxn，其中 n 是顶点数。

例子：

000001 000020 000030
000800 000001 000040
      etc...

另一种解决方案是每次超过大小时将矩阵大小加倍。摊销的计算成本会很小。另一方面，内存可能是个问题。

于 2012-05-18T18:18:36.350 回答
1

如果您一开始没有顶点数，我相信您只能使用样板编号初始化矩阵。假设输入文件仅包含表单行，x y z这意味着从x到到的边y具有（可选）成本z。请注意，输入文件中的行数是图形的边数，假设文件不包含其他内容。n(n-1)/2由于您已经假设它是一个密集图，因此还假设它是一个完整图，其边数等于n顶点数。有了这些信息，您就可以得出足够接近的顶点数近似值。例如，如果输入文件中的边数正在1000000求解 n*(n-1)/2 = 1000000我们得到的方程n约等于1415。将矩阵初始化为1415*1415数组应该很好地覆盖你。

当然，所有这些都是基于这样一个事实，即您有足够快的方法来读取输入文件中的行数。

于 2012-05-17T21:45:54.937 回答