0

我想生成一个巨大的加权无向图,由一个巨大的邻接矩阵 AJM 表示。所以对于 i 和 j 的循环,

AJM[i][j] = AJM[j][i]

AJM[i][i] = 0

权重在区间内生成为随机双数,例如 [0.01, 10.00]。如果我有 10k 个顶点,那么矩阵将是 10k x 10k 的双类型条目,如果我存储它,这将是内存中的一大块。

现在我想为想要的边数设置一个阈值 E,并忽略所有权重大于某个阈值 T 的边(T 由 E 确定,E 是用户定义的),只需存储权重低于的最小 E 边向量中的 T 供以后使用。你能给我一些建议如何以有效的方式实现这一目标吗?最好避免对整个邻接矩阵进行任何形式的存储,只需使用流式结构即可。所以我想知道我应该如何生成矩阵并进行阈值处理?

我想需要写入和读取文件,对吧?

一种方法是,在对文件进行某种操作后,我设置阈值 E 并执行以下操作:

我从矩阵中一个一个地读取元素,所以我没有读入整个矩阵(你能展示几行 C++ 代码来实现这个吗?),并将其权重插入最小堆,存储其相应的边缘索引在一个向量中。当堆的大小达到 E 时我停止,这样边缘索引的向量就是我想要的。

你认为这是正确的做法吗?还有其他建议吗?请指出我在这里可能遇到的任何错误。太感谢了!

4

1 回答 1

0

如果不需要保留原始阈值图,那么听起来有一种简单的方法可以为自己节省大量工作。给定顶点数 (V=10,000),边数 (E) 是用户可配置的。只需随机选择顶点对,直到您拥有所需数量的边。我是否错过了一个明显的原因,为什么这不等同?

于 2013-09-18T11:50:20.833 回答