问题标签 [adjacency-list]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
big-o - Θ(deg(u)) 是什么意思？
我以前从未听说过这个，或者我可能以其他方式听说过？
上下文是，对于邻接列表，列出与u相邻的所有顶点的时间是Θ(deg(u))。
类似地，判断(u,v)∈ E的时间是O(deg(u))。
如果邻接表的实现是一个数组，那么我假设在数组中找到u将是常数时间。
如果所有相邻顶点都链接到u，那么我相信O(n)列出或找到所有顶点需要时间，其中 n 是相邻顶点的数量。
这本质上是什么Θ(deg(u))意思？
javascript - 使用 json 对象的邻接列表
我想使用 json 对象创建一个邻接列表。我想以以下格式为邻接列表实现 json 对象。
我的疑问是，我是否可以动态地将值添加到坐标列表中，例如JSONobj.node3[0]={x4,y4}？或者有没有更好的方法从对象声明之外向 JSONobj 添加值？
c++ - 与 vecS 不同的 VertexList 的 adjacency_list
我有两个包含一些字段的结构：struct MyNodeData 和 struct MyEdgeData。当我使用 VertexList 作为 vecS 创建图形时，访问顶点的描述符等没有问题。例如：
但我通常需要从我的图中添加/删除边和顶点。所以我想使用 setS 或 listS 作为 VertexList，而不是 vecS，因为使用 vecS，当我们删除其中一个索引时，索引会失效！问题是，如果我将 VertexList 定义为 setS 或 listS，我将无法像以前那样浏览顶点/边列表并访问那里的描述符！
简而言之，我的问题是：由于使用 listS 或 setS 作为顶点容器的 adjacency_list 不会自动提供此 vertex_id 属性，如何将其添加到上面的代码中？
sql - SQL：在三级树中保留 root_id？
我有一个简单的三级树，当前存储为邻接列表：
它是只读的，我经常需要知道任何给定类别的根类别。所以我想添加一个 root_id 列并将其持久化以避免混乱的 WHERE 子句、CTE 等。
我的第一次尝试是：
但UPDATE不能处理产生多行的连接。（此查询仅针对 2 级类别；我会为第三级执行类似的查询。）
我知道答案涉及将连接变成子查询，但我不能同时考虑自连接和子查询。我们使用的是 PostgreSQL 9.0，所以我没有可写的 CTE（尽管我很好奇这个 CTE 的外观）。
这样做的正确方法是什么？
python - 在 Python 中从邻接列表构建菜单树
考虑一个基本的邻接表；由 Node 类表示的节点列表，具有属性id、parent_id和name。顶级节点的 parent_id = 无。
将列表转换为无序 html 菜单树的 Pythonic 方式是什么，例如：
- 节点名称
-
节点名称
- 子节点名称
- 子节点名称
sql - 在 SQL 中管理层次结构：MPTT/嵌套集 vs 邻接列表 vs 存储路径
一段时间以来，我一直在思考如何最好地处理 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 件存储路径解决方案无法做到的事情：
- 允许计算每个节点的子节点计数，而无需任何额外的查询（如上所述）。
- 对给定级别的节点施加命令。其他解决方案是无序的。
c - 创建邻接表
我无法以正确的顺序创建相邻列表。我认为 CreateAdjList(void) 方法存在一些问题。我没有主意了。请给我一些提示。基本上我有图并在连接的边上创建邻接列表。
实际程序输出 - 错误顺序。我以尊敬的方式附加了输出列表。
输入：
我的实际输出显示顺序错误。如果您查看节点，正确的顺序应该是 2 ->3->6->5
c - 链表创建
我正在尝试使用邻接列表来表示图形，但我遇到了指针问题。
我正在尝试构建的实际上很简单。1 --> 1,2 。但是我写的代码不起作用。可能是什么问题呢？
编辑：好的，我更正了NULL。预期的输出是 1 -->> 1,2 。具有 2 个节点 1 的图指向自身和值为 2 的下一个节点。我的问题是当我在获取列表 1 --> 1,2 后创建图时；看起来我有 3 个不同的节点。我的意思是稍后当我将节点的值从 1 更改为 3 时，我得到 3 --> 1,2 但由于我应该只有 2 个节点，所以在我进行更改后所需的输出应该是 3 --> 3,2。