我有40亿（四个十亿）边的无向图。他们是在一个大的文本文件作为对节点ID的表示。我想计算该图的连通组件。不幸的是，一旦你与边缘到内存中的节点ID加载这个时间比RAM的128GB我有更多的可用。
是否有发现连接组件是实现相对简单的出核心算法？甚至更好，可以将其与Unix命令的工具和现有的（蟒蛇）库拼凑起来？
根据您所提供的问题，你在评论中提供的答案的描述，我觉得这样做可能是使用像@dreamzor描述的一种方法最简单的方法。下面是答案的更充实出的版本。
其基本思想是将数据转换成适合存储一个更加压缩的格式，运行这些数据定期连接组件的算法，然后将其解压。注意，如果所分配的每个节点一个32位的数字ID，然后来存储所有节点所需的总空间是至多（假设你存储每个边缘的两个副本）四个十亿节点和八个十亿边缘的空间中，这是十二十亿的32位整数，只有周围的空间48GB，下方的内存阈值空间。
要开始，写一个脚本，在边缘文件读取，（按照它们出现的顺序顺序地也许）一个数字ID分配给每个节点。有此脚本写这个映射到一个文件，并为它去，编写使用节点而不是字符串名称的数字ID的新边文件。当你完成，你就会有一个名字的文件映射到的ID名和比以前占用空间更少的边缘文件。你在你能适应所有节点名称到内存中的评论中提到，所以这一步应该是很合理的。请注意，您不必存储在内存中的所有边缘 - 您可以通过节目流他们 - 所以这不应该是一个瓶颈。
接下来，编写一个程序，读取边缘文件 - 而不是名称的文件 - 到内存中，发现使用任何合理的算法（BFS或DFS将是巨大的在这里）连接的部件。如果你小心你的内存（使用类似C或C ++这里将是一个良好的通话），这应该合身舒适到主存储器。当你完成后，写出所有集群通过数字ID的外部文件。现在，您可以通过ID的所有CC的列表。
最后，写一个程序，在ID读取到节点从名字文件映射，然后在簇ID流并写出在每个集群中的所有节点的名称到最终文件。
这种方法应该是比较容易实现，因为核心思想是让你使用现有的算法，但只是改变图形的表现更高效的内存。巨大的图表（维基百科）打交道时，我已经在过去使用这样的方法之前，它的美丽，甚至工作的系统上比你更少的内存。
你只能容纳顶点作为他们的“颜色”（一个int值），然后通过文件运行的阵列，而无需加载整个组的链接，标记有颜色的顶点，如果没有顶点是彩色一个新的，同样的颜色如果一个人是有色，另一种是没有了，最低的两种颜色，与重绘阵列中的所有其它顶点被涂上最高的颜色，如果两者都有色在一起。伪代码示例：
int nextColor=1;
int merges=0;
int[] vertices;
while (!file.eof()) {
link=file.readLink();
c1=vertices[link.a];
c2=vertices[link.b];
if ((c1==0)&&(c2==0)) {
vertices[link.a]=nextColor;
vertices[link.b]=nextColor;
nextColor++;
} else if ((c1!=0)&&(c2!=0)) {
// both colored, merge
for (i=vertices.length-1;i>=0;i--) if (vertices[i]==c2) vertices[i]=c1;
merges++;
} else if (c1==0) vertices[link.a]=c2; // only c1 is 0
else vertices[link.b]=c1; // only c2 is 0
}
如果你选择用于存储顶点的颜色小于32位的，则可能需要首先检查是否nextColor刷爆，具有（在合并发布）的颜色未使用的阵列，并跳过着色一组新的两个顶点的如果没有颜色可以使用，然后重新运行该文件读取过程中，如果全部都使用的颜色和发生的任何mergings。
更新：由于顶点是不是真的，但整数，而不是字符串，你也应该有地图串的同时，解析该文件为int。如果你的字符串按长度的限制，你可能适合他们都到内存中的哈希表，但我会通过创建将拥有所有的字符串另一个文件预先处理文件“S1”替换为“1”，“S2 “与‘2’等，其中‘S1’，‘S2’是什么名称出现在文件中的顶点，这样的数据将被压缩，以对整数的列表。如果你在以后处理类似的数据（也就是你的图形没有太大变化，而含有大部分顶点相同的名称，存储与从名字到整数，以缓解进一步的预处理环节的“元数据”的文件。