如何在 运行 内存不足的情况下存储加权图的信息？
How do I store information for weighed graph without running out of memory?
所以我有一个关于城市和道路的任务。城市之间的每条道路都有它的价格。有很多城市，其中一些城市与价格不同的道路相连。我如何存储这些信息？
从文件中读取信息，然后将其放入二维数组中。 numbers{0} 和 numbers{1} 包含两个相连城市的编号，而 numbers{2} 是道路的价格。
所以这个数组的索引是城市的编号，索引下的数字是价格。
int[,] graph = new int[cities, cities];
for (int i = 0; i < roads; i++)
{
numbers = ReadFromFile(input);
graph[numbers[0] - 1, numbers[1] - 1] = numbers[2];
graph[numbers[1] - 1, numbers[0] - 1] = numbers[2];
}
它可以工作，但是它必须通过的大部分测试都失败了。原因是在某些时候它必须为 5000 个城市存储 5000 * 5000 个值并且它耗尽了内存。我该怎么做才能避免这种情况？我考虑过其他选择，但没有想到比这个更好的选择。
A snapshot
假设每个城市都通过 3 条或更少的不同道路与其他城市相连。对于每条道路，您需要存储 3 个项目（来源、目的地和成本）假设一个项目需要 4 个字节的存储空间。
5000 * 5000 * 3 * 4 = 3 * 10^8
那是 300 MB 的存储空间。
任何现代计算机存储这个应该没有问题 - 现在内存通常以千兆字节为单位。
您的电脑有问题！
在执行任何其他操作之前，尝试将项目转换为在 x64 体系结构中工作，而不是“Any CPU”或“Win32”。这可能会消除一些内存问题。
理想情况下，您应该使用“稀疏数组”或“稀疏矩阵”。网上有一些项目，但它们可能很笨重。下一个最好的办法是使用字典和两个一维数组而不是大矩阵来模拟稀疏数组。
字典以Tuple<int, int>为键（两个整数是一个单元格的坐标）和道路价格作为值（如果只有一条道路可以连接两个城市则值为int，对于多个两个城市之间的道路 List<int>).
两个一维数组用于查找字典中的非空单元格。每个坐标一个数组，因此两者的大小均为 5000，它们包含一个 List<int> 列表，其中包含另一个轴中存在非空单元格的所有坐标。根据您的搜索算法，您可能只需要一个这样的数组，例如用于 x 轴（不需要另一个用于 y 轴）。
所以我有一个关于城市和道路的任务。城市之间的每条道路都有它的价格。有很多城市，其中一些城市与价格不同的道路相连。我如何存储这些信息？ 从文件中读取信息，然后将其放入二维数组中。 numbers{0} 和 numbers{1} 包含两个相连城市的编号，而 numbers{2} 是道路的价格。 所以这个数组的索引是城市的编号，索引下的数字是价格。
int[,] graph = new int[cities, cities];
for (int i = 0; i < roads; i++)
{
numbers = ReadFromFile(input);
graph[numbers[0] - 1, numbers[1] - 1] = numbers[2];
graph[numbers[1] - 1, numbers[0] - 1] = numbers[2];
}
它可以工作，但是它必须通过的大部分测试都失败了。原因是在某些时候它必须为 5000 个城市存储 5000 * 5000 个值并且它耗尽了内存。我该怎么做才能避免这种情况？我考虑过其他选择，但没有想到比这个更好的选择。 A snapshot
假设每个城市都通过 3 条或更少的不同道路与其他城市相连。对于每条道路，您需要存储 3 个项目（来源、目的地和成本）假设一个项目需要 4 个字节的存储空间。
5000 * 5000 * 3 * 4 = 3 * 10^8
那是 300 MB 的存储空间。
任何现代计算机存储这个应该没有问题 - 现在内存通常以千兆字节为单位。
您的电脑有问题！
在执行任何其他操作之前，尝试将项目转换为在 x64 体系结构中工作，而不是“Any CPU”或“Win32”。这可能会消除一些内存问题。
理想情况下，您应该使用“稀疏数组”或“稀疏矩阵”。网上有一些项目，但它们可能很笨重。下一个最好的办法是使用字典和两个一维数组而不是大矩阵来模拟稀疏数组。
字典以Tuple<int, int>为键（两个整数是一个单元格的坐标）和道路价格作为值（如果只有一条道路可以连接两个城市则值为int，对于多个两个城市之间的道路 List<int>).
两个一维数组用于查找字典中的非空单元格。每个坐标一个数组，因此两者的大小均为 5000，它们包含一个 List<int> 列表，其中包含另一个轴中存在非空单元格的所有坐标。根据您的搜索算法，您可能只需要一个这样的数组，例如用于 x 轴（不需要另一个用于 y 轴）。