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

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) 两个节点是否有连接边
• 邻接表可以更快地找到给定节点的度数(邻居的数量)。
• 与 n^2 相比，如果使用邻接表实现，具有 m 节点和 n 边的图会消耗 m + n 空间 用于邻接矩阵。
• 邻接矩阵对大图使用稍微较少的内存。
• 使用邻接矩阵时，边插入/删除的执行时间为 O(1)。
• 遍历使用邻接表实现的图在 Θ(m + n) 和矩阵 Θ(n^2)
中执行

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

所以一般来说，邻接表表现得更好。