通过指针数组实现树的优点？

Question

最近学习了通过struct实现树，比如

struct Node{
     Node *parent;
     vector<Node*> child;
     Node(void):parent(nullptr){}
}

我认为这是实现树的一种非常直接的方法， 并且在结构中包含更多用于处理的内容也更容易。

但是，我注意到在很多人的代码中， 他们更喜欢使用数组而不是指针。 我可以理解二叉树的这一点，因为它也很容易通过数组来实现 ，但为什么在其他更复杂的图表上？

Answer 1

从 Skiena:2008:ADM:1410219 和 Cormen:2001:IA:580470 比较 图 的邻接矩阵和邻接列表得出：

• 如果两个节点 (x, y) 具有连接边
，则邻接矩阵可以更快地进行测试
• 邻接表可以更快地找到给定节点的度数（邻居的数量）。
• 具有 m 个节点和 n 个边的图消耗 m + n space 如果使用邻接列表实现，而 n^2 用于邻接矩阵。
• 邻接矩阵使用稍微较少的大图内存。
• 边 insertion/deletion 在使用邻接矩阵时在 O(1) 中执行。
• 遍历使用邻接表实现的图在 Θ(m + n) 和矩阵 Θ(n^2)
中执行

如果一个图有很多顶点但边很少，邻接矩阵会消耗过多的内存。

所以一般来说，邻接表的性能更好。