我以前从未听说过这个，或者我可能以其他方式听说过？
上下文是，对于邻接列表，列出与u相邻的所有顶点的时间是Θ(deg(u))。
类似地，判断(u,v)∈ E的时间是O(deg(u))。
如果邻接表的实现是一个数组，那么我假设在数组中找到u将是常数时间。
如果所有相邻顶点都链接到u，那么我相信O(n)列出或找到所有顶点需要时间，其中 n 是相邻顶点的数量。
这本质上是什么Θ(deg(u))意思？

我想使用 json 对象创建一个邻接列表。我想以以下格式为邻接列表实现 json 对象。

我的疑问是，我是否可以动态地将值添加到坐标列表中，例如JSONobj.node3[0]={x4,y4}？或者有没有更好的方法从对象声明之外向 JSONobj 添加值？

我有两个包含一些字段的结构：struct MyNodeData 和 struct MyEdgeData。当我使用 VertexList 作为 vecS 创建图形时，访问顶点的描述符等没有问题。例如：

但我通常需要从我的图中添加/删除边和顶点。所以我想使用 setS 或 listS 作为 VertexList，而不是 vecS，因为使用 vecS，当我们删除其中一个索引时，索引会失效！问题是，如果我将 VertexList 定义为 setS 或 listS，我将无法像以前那样浏览顶点/边列表并访问那里的描述符！

简而言之，我的问题是：由于使用 listS 或 setS 作为顶点容器的 adjacency_list 不会自动提供此 vertex_id 属性，如何将其添加到上面的代码中？

这是邻接列表的SO 帖子。但是我看不出与单链表有什么区别？这里还有一篇维基百科文章说，如果我有一个不是路径图的图，那么它是一个非常广泛的列表中的所有边（图，离散数学类型）。如何编码邻接列表？

我有一个简单的三级树，当前存储为邻接列表：

它是只读的，我经常需要知道任何给定类别的根类别。所以我想添加一个 root_id 列并将其持久化以避免混乱的 WHERE 子句、CTE 等。

我的第一次尝试是：

但UPDATE不能处理产生多行的连接。（此查询仅针对 2 级类别；我会为第三级执行类似的查询。）

我知道答案涉及将连接变成子查询，但我不能同时考虑自连接和子查询。我们使用的是 PostgreSQL 9.0，所以我没有可写的 CTE（尽管我很好奇这个 CTE 的外观）。

这样做的正确方法是什么？

考虑一个基本的邻接表；由 Node 类表示的节点列表，具有属性id、parent_id和name。顶级节点的 parent_id = 无。

将列表转换为无序 html 菜单树的 Pythonic 方式是什么，例如：

• 节点名称
• 节点名称
  • 子节点名称
  • 子节点名称

一段时间以来，我一直在思考如何最好地处理 SQL 中的层次结构。由于邻接列表的局限性和 MPTT/嵌套集的复杂性，我开始考虑简单地将关键路径存储为一个简单的node_key/node_key/...字符串。我决定整理一下这三种技术的优缺点：

创建/删除/移动节点所需的调用次数：

• 邻接 = 1
• MPTT = 3
• Path = 1（将旧节点路径替换为包含该路径的所有节点的新节点路径）

获取树所需的调用次数：

• 邻接 = [子级别数]
• MPTT = 1
• 路径 = 1

获取节点/祖先路径所需的调用次数：

• 邻接 = [超层数]
• MPTT = 1
• 路径 = 0

获取子节点数量所需的调用次数：

• 邻接 = [子级别数]
• MPTT = 0（可以从右/左值计算）
• 路径 = 1

获取节点深度所需的调用次数：

• 邻接 = [超层数]
• MPTT = 1
• 路径 = 0

需要的数据库字段：

• 邻接 = 1（父）
• MPTT = 3（父、右、左）
• 路径 = 1（路径）

结论

存储路径技术在每个用例中都使用与其他技术相同或更少的调用，除了一个。通过这种分析，存储路径显然是赢家。更不用说，它实现起来要简单得多，人类可读等等。

所以问题是，存储路径不应该被认为是比 MPTT 更强大的技术吗？为什么存储路径不是一种更常用的技术，为什么您不在给定实例中通过 MPTT 使用它们？

另外，如果您认为此分析不完整，请告诉我。

更新：

以下是 MPTT 可以开箱即用的至少 2 件存储路径解决方案无法做到的事情：

1. 允许计算每个节点的子节点计数，而无需任何额外的查询（如上所述）。
2. 对给定级别的节点施加命令。其他解决方案是无序的。

我无法以正确的顺序创建相邻列表。我认为 CreateAdjList(void) 方法存在一些问题。我没有主意了。请给我一些提示。基本上我有图并在连接的边上创建邻接列表。

实际程序输出 - 错误顺序。我以尊敬的方式附加了输出列表。

输入：

我的实际输出显示顺序错误。如果您查看节点，正确的顺序应该是 2 ->3->6->5

我正在尝试使用邻接列表来表示图形，但我遇到了指针问题。

我正在尝试构建的实际上很简单。1 --> 1,2 。但是我写的代码不起作用。可能是什么问题呢？

编辑：好的，我更正了NULL。预期的输出是 1 -->> 1,2 。具有 2 个节点 1 的图指向自身和值为 2 的下一个节点。我的问题是当我在获取列表 1 --> 1,2 后创建图时；看起来我有 3 个不同的节点。我的意思是稍后当我将节点的值从 1 更改为 3 时，我得到 3 --> 1,2 但由于我应该只有 2 个节点，所以在我进行更改后所需的输出应该是 3 --> 3,2。