图通常使用邻接矩阵表示。各种来源表明可以避免初始化成本为 |V^2|。 (V 是顶点的数量)但我还没有弄清楚怎么办。
在 Java 中，只需声明矩阵，例如boolean adj [][]，运行时将自动用false初始化数组，这将在O(V^2 ) 成本(数组的维度)。
我误解了吗？是否有可能避免邻接矩阵初始化的二次成本，或者这只是取决于实现语言的理论上的东西？
最佳答案
这可以通过使用邻接矩阵的稀疏矩阵表示来实现，其中只分配“1”的位置而不是矩阵的每个元素(可能包含大量零)。你可能会发现 this thread也有用
关于java - 邻接矩阵的图形实现和初始化，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10570492/