用Java生成基于数组的图

Question

我需要使用整数数组生成一个图。图的边保持为边[e][2]，其中e是边的数量。我需要我的图是连接的，也就是说，你应该能够从所有节点遍历到所有节点。

edges[0]＝{0,5}表示连接节点0和节点5的边。你能建议一个算法吗？

请记住，我将生成具有数百万个节点的图，因此如果算法复杂度不太高会更好。

Answer 1

如果每个节点都直接连接到每个节点，则不要存储所有边；）

如果每个节点都可以从其他节点访问，但不一定直接访问，则使用邻接矩阵。如果需要使用整数数组，这是最简单的方法。

如果矩阵是稀疏的，我会以不同的方式存储它。最佳编码取决于您希望将其用于何种图形算法。维基百科上关于稀疏矩阵的文章）列出了主要的稀疏矩阵。