斯坦福GraphBase .gb格式

Question

我想输入我自己的图表与斯坦福GraphBase CWEB库一起使用。我在SGB网页上找到了this图的示例，并且大部分都能理解它。我不明白为什么顶点列表中有四个零行（“”，0 \ n），边界列表中有很多零行（0,0,0）。没有它们，图表似乎编译得很好，我看不到它们的目的。

Answer 1

额外的零线不是绝对必要的。它们包含在内，以便在加载图时，内存预先分配给可能稍后添加到图中的顶点和弧（例如，在图上运行的某些算法中）。这是为新顶点和边缘动态分配内存的替代方法。恰恰相反，该链接中的图形应该与需要空间用于图形上的额外节点和圆弧的算法结合使用。