data-structures - 术语:非 TreeMap ？

Question

我是数据结构的新手，对术语有疑问。是否有非树状图的术语？

我意识到双向/无向图本质上是非树状的。那是合适的词吗？我问是因为树似乎是图的一个常见子类别，我认为可能有一个术语表示所有不属于该子类别的图。

P.s.:请随意破解上面的任何白话。喜欢关于数据结构的一般适当术语的提示。

Answer 1

我不认为非 TreeMap 有一个通用的术语(除了“非 TreeMap ”本身)。

Trees是连通的、非循环的、有向图，带有一些额外的规则，例如每个节点(根节点除外)只有一个父节点。某些类型的树具有其他附加规则，这些规则在其他类型的图中并不常见(例如节点的子节点的顺序具有重要意义)。根据非 TreeMap 违反了哪些限制，您可能会对其进行不同的描述。

没有完全连接的树状图可以描述为“森林”。一个森林有多个根节点，每个根节点锚定一个不相交的子树。

如果你有一个包含多个根节点的图，但它们的后代重叠(这样一个给定的子节点可能有多个父节点)，你有一个“multitree”。如果堂兄弟或其他亲戚之间没有婚姻，人类家谱可能是一棵多树。

下一个更通用的术语可能是“directed acyclic graph”或“DAG”。 DAG 比多树更通用，因为祖先节点可能通过多条路径连接到后代节点。人类家谱树更恰本地称为 DAG，因为足够远的亲属通常被允许结婚生子(但没有人可以成为他们自己的祖先)。有许多算法设计用于 DAG，因为禁止循环可以为许多有用的应用程序(例如路径查找)提供更好的性能。

更一般的还是“directed graph”或“digraph”，它放宽了循环限制。一种常见的有向图数据结构是邻接表(从一个节点到另一个节点的弧列表)。

除了“图形”之外，我认为没有比这更通用的术语了。如果你有一个特定的图形应用程序，可能会有一个专门的术语来描述你将使用的图形类型(可能还有算法甚至库代码)，但你需要具体询问。