问题标签 [adjacency-list]

我正在尝试使用 Boost 的 adjacency_list 类型，但我无法理解文档。

假设我定义了一个名为 State 的类，并为美国的每个州实例化一个实例：

我想将这些输入到 boost::adjacency_list 中，顶点是状态，边缘是边界。对于我上面列出的状态，我认为图表将包含以下数据：

我了解如何将整数放入图中，我考虑只是制作一个状态数组并将它们的数组索引插入到图中，但似乎我应该只能说：

但这当然行不通。请帮忙！

编辑：
这是一个几乎正是我需要的例子。

我读过很多人讨论嵌套列表，但我想知道如何在 PHP 中遍历邻接列表/树。

我有一张桌子：id、title、parent_id

我已将所有记录选择到一个名为 $pages 的数组中。

然后使用这个php：

这类作品，但我最终会重复任何子菜单，例如

• 家
  • 消息
    • 子新闻
  • 文章
    • 文章
• 消息
  • 子新闻
• 文章
  • 文章
• 子新闻
• 文章

我尝试将当前 id 添加到通过函数传递的数组中，然后使用 in_array 检查它是否存在，但这样做我并不高兴。

任何帮助将非常感激。

我需要解析整个树，所以不能选择 parent 作为 0

我有一个使用邻接列表模型存储层次信息的表。（使用自引用键 - 下面的示例。此表可能看起来很熟悉）：

将上述数据“展平”成这样的最佳方法是什么？

每一行都是通过层次结构的一个“路径”，除了每​​个节点都有一行（不仅仅是每个叶子节点）。category_id 列代表当前节点，“lvl”列是它的祖先。当前节点的值也必须在最右边的 lvl 列中。lvl1 列中的值将始终表示根节点，lvl2 中的值将始终表示 lvl1 的直接后代，依此类推。

如果可能，生成此输出的方法将使用 SQL，并且适用于 n 层层次结构。

我有许多不同的项目存储在不同的 MySQL 表中，我想将它们放入树层次结构中。使用邻接表模型，我可以为每个表添加一个 parent_id 字段，并使用外键关系链接这些表。

但是，我想使用嵌套集/修改的预序树遍历模型。数据将在严重偏向于读取的环境中使用，并且我希望运行的查询类型支持这种方法。

问题是我在嵌套集上的所有信息都假设您只有一种类型的项目，存储在一个表中。我能想到的解决方法是：

• 树中有多个外键字段，每个表/项目类型一个。
• 在树结构中存储项目表的名称以及项目 ID。

至少可以说这两种方法都不优雅，那么有没有更好的方法呢？

我在遗留系统上有一个邻接列表，我想递归查询（需要获取小计等）。

我可以在 MySQL 中创建一个触发器，将其存储在单独的表中，或者将给定集合的“嵌套集等效”存储在同一个表的单独列中吗？

我的套餐是这样的：

我要这个：

我想从 MySQL 中提取菜单项。

我可以从 id=1 到 4 中提取数据并通过“...where parentid=1”等显示。但是这只会拉出顶层。

但我也想提取所有数据，包括每个菜单（主菜单）的子菜单。

谁能告诉我如何在 MySQL 中为此编写查询？

提前致谢。

我正在使用邻接列表来表示有向加权图，并且基于此SO question 提供的示例代码，我创建了以下内容：

我无法使该isConnected方法正常工作。我是否使用了错误的数据结构来表示此处的图形（Map<String, LinkedHashSet<HashMap<String, Integer>>>）？hashmap 将保存连接节点的名称和到它的距离：

1. 基本上如何检查节点是否属于给定基本节点的邻接列表？我认为问题归结为在结构上正确迭代adjacent Set<HashMap<String, Integer>> ，还是我的推理错误？
2. 在我的第二种方法 adjacentNodes(String node)中，我返回一个链接列表，其中包含连接节点的映射（在一个集合结构中）及其距离。我如何有效地迭代以查看任何给定节点的所有连接？

我正在寻找一个 Django 树库并尽我所能避免嵌套集（它们是维护的噩梦）。

邻接列表模型的缺点一直是无法在不诉诸多个查询的情况下获取后代。Postgres 中的 WITH 子句似乎是解决这个问题的可靠方法。

有没有人看过任何关于 WITH vs. Nested Set 的性能报告？我认为嵌套集仍然会更快，但只要它们处于相同的复杂性级别，我就可以吞下 2 倍的性能差异。

Django-Treebeard 让我很感兴趣。有谁知道他们在 Postgres 下运行时是否实现了 WITH 子句？

有没有人根据 WITH 子句从嵌套集切换？

convertToList：将邻接矩阵转换为邻接列表。

printList：遍历邻接矩阵并为每条边打印一条消息。

问题：一些边被复制。我不确定创建列表数组或遍历邻接矩阵以打印它时是否有问题。有什么建议么？

下面是带有边 (0, 1) 和 (3, 2) 的 5 个顶点的程序输出图片。矩阵是正确的。邻接表不是。边 (0, 1)、(1, 1) 和 (2, 3) 不应重复。

对于 C++ 中的图问题，邻接列表或邻接矩阵哪个更好？各自的优点和缺点是什么？