我们可以使用二叉搜索树表示图吗？

Question

我目前正在处理一些图形数据结构问题，并且确实遇到了邻接矩阵和列表，以在计算机内存中表示一个图形，但是如果我们可以使用BST来存储图形的边缘，然后插入，这件事就在我的脑海中震撼了并且搜索两者都可以在n天内完成，任何人都可以告诉我是否可以这样做吗？谢谢。

Answer 1

我们可以用BST表示图吗？

取决于您所称的图形。 BST也是图。但是，当您谈论整个图形时，您无法使用BST表示它。为什么？

1. BST中的一个节点将只有两个子节点，其中图中的一个节点可以连接到任意数量的节点。邻接矩阵可以通过在每个节点上排一行并表示其与其他节点的连接状态来表示这种连接。
2. 树只能表示层次结构，其中图，连通性不必是层次结构。

Answer 2

这个问题有点误导。我想你想说：

如果边缘存储在

set]中，则可以进行快速（log n）设置操作以进行添加/删除。

实际上是在软件中，顶点对象拥有一组naybors或Edge。

这是时空选择的问题。邻接矩阵（如果不是太稀疏，则顶点很多，边缘很少）既紧凑又规则，例如用于向量运算或学生解。