问题标签 [adjacency-list]

我正在我的系统中设计访问控制列表。其中将有一个组和帐户树，如下所示

在上面的树中'所有用户''管理员''特权成员是组。我想创建一棵树来存储上述信息。在邻接表遍历中，读操作成本很高，而在 Mptt 遍历中，写操作成本很高。对于 ACL，什么应该更重要，读或写。我认为 read 会被经常使用，但想在这里听取聪明人的意见。在 cake php acl 中，他们使用了 mptt。

我正在玩（出于兴趣）在一个简单的邻接列表中检索节点树，并使用局部变量进行递归查询。

到目前为止我的解决方案很有趣，但我想知道（这是我唯一的问题）为什么 MySQL 拒绝使用 anyINDEX来优化这个查询。MySQL不应该能够通过使用查找最近的孩子INDEX吗？

我很好奇为什么 MySQL 没有。即使我使用FORCE INDEX执行计划也不会改变。

这是到目前为止的查询，5是父节点的 ID：

在 SQLfiddle 尝试实时示例

请注意，原因不能是小数据集，因为当我指定FORCE INDEX (id)orFORCE INDEX (parent_id)或FORCE INDEX (id, parent_id)...时行为不会改变

文档说：

您还可以使用 FORCE INDEX，它的作用类似于 USE INDEX (index_list)，但另外假设表扫描非常昂贵。换句话说，仅当无法使用给定索引之一来查找表中的行时，才使用表扫描。

一定有一些东西使查询无法使用索引，但我不明白它是什么。

免责声明：我知道在 SQL 中存储和检索分层数据有不同的方法。我知道嵌套集模型。我不是在寻找替代实现。我不是在寻找嵌套集。

我也知道查询本身很疯狂并且会产生错误的结果。

我只想（详细）了解为什么 MySQLINDEX在这种情况下不使用 an 。

我以多种方式问过这个问题，首先是：

当您有邻接列表时，顺序是否重要？假设我有邻接列表 {1, 2, 5} 是否等同于 {2, 1, 5}？或者顺序是否意味着什么，因此这两个列表不等价？

我收到了几个答案，包括仅在图形是定向的并且顺序表示与顺时针相邻节点排列有关的情况下才重要..？我也被认为没有关系，但是他更希望根据权重（如果使用）对其进行排序，例如互联网的排序方式 - 页面排名算法。尽管我认为我传达了要点，但我不认为要准确地解释这些回答中的任何一个。任何想法表示赞赏。

此外，我已经改进了我的问题，如果得到回答，我认为会给我我所追求的确切答案：

假设我有一个有向图的邻接矩阵：

0 0 1 0

0 0 1 1

1 1 0 1

0 1 1 0

我被告知等效的邻接列表如下，并假设我的老师故意以这种方式列出它，而不是一些任意的重新排序 - 特别是如最后一个列表所示：

{ 2 }

{ 2, 3 }

{ 0, 1, 3 }

{ 2, 1 }

最后一个列表是 { 2, 1 }！等效邻接矩阵中的什么提醒我它应该是 { 2, 1 } 而不是 { 1, 2 }？

我有一个 Edge 类，它存储：源（顶点）、目标（顶点）和权重。

我有一个 Vertex 类，它存储：名称、x 坐标、y 坐标和 Ed​​ge[] 相邻列表。

我还有一个 Graph 类，它存储两个 ArrayList：边和顶点。

当前，当绘制顶点/节点和边时，它会分别自动添加到顶点和边列表中。

现在我想使用这两个数组列表填充 Edge[] 相邻列表，但我不知道该怎么做。如果有人能给我指点或概述代码的外观，我将不胜感激。

谢谢你。

在邻接列表表中，给定节点的 id，我如何找到它的关联根节点？

笔记：

该表包含多棵树，因此我不能简单地搜索 null parentId。

更多信息：

这是我目前所拥有的，对此有任何问题或改进吗？

我目前正在开发一个应用程序，以在我的最后一年项目的图表中找到最大集团。我已经完成了大部分项目，并且刚刚开始测试应用程序。

该应用程序当前使用邻接列表作为输入，我想知道是否有人知道邻接列表随机生成器，以便我可以测试我的应用程序？

非常感谢

我在使用此数据结构模型的类别中有一个表。还可以使用另一个表来显示类别分支的路径：

我想要的是获得任何项目的父母名单。例如如果我搜索“狗”得到“狗，吉祥物”，如果我搜索“杜宾”应该得到“杜宾，狗，吉祥物”

我试过这个......但它是相反的，我的意思是寻找父母得到叶子：

显然得到：

但我想从“杜宾”中得到：

可以从叶子咨询吗？

我们正在使用 mysql。假设我们有一个 Adjacency List 模型表。（我知道它没有被规范化。）例如，具有以下字段的人员表：

我们还有一张桌子，里面有一些用户。例如，

假设工资信息是保密的。因此，一些用户可以从某个分支看到工资信息。

例如，角色 b1 可以查看/编辑老板 1 及以下的所有工资。角色 b2 可以查看/编辑老板 2 及以下的所有工资。角色 sd 可以查看/编辑 slvdrvr1 和 slvdrvr2 及以下的所有工资。因此，我们需要设置一个用户-人员权限表来实现这一点。

Personnel 表很大，有数万行。

我的问题是我们如何设置一个我们可以轻松维护和查询的权限表？

例如，选项 1：我们可以为每个人设置角色权限。但是，权限表会很大。

选项2：我们只能为父节点设置角色权限。但是，每次用户想要查看一定数量的记录时，我们都必须为每条记录查找权限，一直到我们有设置的地方。

用户数约为数百。角色数量少于 100。

如果不清楚，请向我提问。提前致谢。

我正在编写代码来从边列表中创建一个矩阵。

然而，当我运行上述代码时，我得到了一个不在输入数据中的“幻影边缘”，这继续搞砸了我的程序的其余部分。边是矩阵中的 9,2，或元素代码形式的 8,1。

矩阵中的所有元素都预先初始化为 0。

这是与矩阵有关的输入数据：

以下是处理输入的函数：

*不应该存在的条目，不在输入数据中

我有两个实体，post这category是一个1:n关系。

我有一个包含两列的参考表post_id，category_id

表categories有一id列，一status列，一parent_id列

如果一个类别是另一个类别（n 深度）的子类别，则它parent_id不为空。

如果一个类别在线，则其状态为 1，否则为 0。

我需要做的是找出帖子是否可见。

这需要：

Foreach 类别加入到帖子跟踪它的树到根节点（直到类别具有parent_id== null），如果这些类别中的任何一个具有status0 则该路径被认为是离线的。

如果任何路径在线，则认为该帖子可见，否则将其隐藏。

我能想到的唯一方法（作为半伪代码）是：

但这可能最终会成为很多 sql 查询，有没有更好的方法？