问题标签 [adjacency-list]

我花了最后几个小时试图在网上找到这个问题的解决方案。我找到了很多关于如何从嵌套集合转换为邻接的例子......但很少有相反的例子。我发现的示例要么不起作用，要么使用 MySQL 过程。不幸的是，我不能为这个项目使用程序。我需要一个纯 PHP 解决方案。

我有一个使用以下邻接模型的表：

我想将其转换为下面的嵌套集表：

这是我需要的图像：

我有一个函数，基于这个论坛帖子（http://www.sitepoint.com/forums/showthread.php?t=320444）的伪代码，但它不起作用。我得到多行具有相同的左侧值。这不应该发生。

这是上述脚本的输出。

插入nested_table( id, lft, rgt, category) 值（NULL, '2', '5', 'Hard Cover' ）

插入nested_table( id, lft, rgt, category) 值( NULL, '2', '7', 'Large Format' )

插入nested_table( id, lft, rgt, category) 值( NULL, '1', '8', 'Books' )

插入nested_table( id, lft, rgt, category) 值( NULL, '1', '10', 'CD's' )

插入nested_table（id，，，， ）值（NULL lft，'10'，'13'，'Vintage'）rgtcategory

插入nested_table（id，，，， ）值（NULL，'1'，'14'，'杂志' lft）rgtcategory

插入nested_table（id，，，， ）值（NULL lft，'0'，'15'，'ROOT'）rgtcategory

正如你所看到的，有多个行共享“1”的 lft 值，“2”也是如此。在嵌套集中，left 和 right 的值必须是唯一的。下面是一个如何手动为嵌套集合中的左右 ID 编号的示例：

图片来源：Gijs Van Tulder，参考文章

我想从路径枚举列创建面包屑。

这是我拥有的数据集的示例。

https://spreadsheets.google.com/ccc?key=0AsGYQbeSAIgFdGRscFpsZFJpQUtfWGIwYWNUY2ktRHc&hl=en_GB&authkey=CPOuuogF

id woeid parent_woeid country_code name language place_type ancestry

祖先是枚举的路径，例如1/23424975/24554868/12602167/12696151英国布莱顿的路径。

我希望能够通过查询name列来检索面包屑，并获得所有的父母。

IE。World, Europe, England, [County], [Town], [Region], [Place]

([] = a placeholder)

数据永远不会改变，这就是该表使用邻接列表和路径枚举的原因。

我有一张表，其中包含世界上所有地理位置的位置及其关系。

这是一个显示层次结构的示例。您将看到数据实际上存储为所有三个

• 枚举路径
• 邻接表
• 嵌套集

数据显然也永远不会改变。以下是英格兰布莱顿地区的直系祖先的示例，其 woeid 为 13911。

表：（有 560 万行） 大图：httpgeoplanet_places : //tinyurl.com/68q4ndx

然后我有另一个名为entities. 此表存储我想映射到地理位置的项目。我存储了一些基本信息，但最重要的woeid是我存储了来自geoplanet_places.

最终该entities表将包含数千个实体。而且我想要一种能够返回包含实体的所有节点的完整树的方法。

我计划创建一些东西来促进基于地理位置的实体的过滤和搜索，并能够发现在该特定节点上可以找到多少实体。

所以如果我的表中只有一个实体entities，我可能会有这样的东西

`地球 (1)

英国 (1)

英格兰 (1)

东萨塞克斯 (1)

布莱顿霍夫城 (1)

布莱顿 (1)`

然后假设我有另一个位于德文郡的实体，然后它将显示如下内容：

地球 (2)

联合王国 (2)

英格兰 (2)

德文 (1)

东萨塞克斯 (1) ... 等

将说明每个地理位置“内部”有多少实体的（计数）不需要是活的。我可以忍受每小时生成我的对象并缓存它。

目的是能够创建一个界面，该界面可能一开始只显示具有实体的国家/地区。

所以喜欢

Argentina (1021), Chile (291), ..., United States (32,103),United Kingdom (12,338)

然后，用户将单击一个位置，例如 United Kingdom，然后将获得所有直接子节点，这些子节点是 United Kingdom 的后代，并且其中有一个实体。

如果英国有 32 个县，但最终只有 23 个县有实体存储在其中，那么我不想显示其他 9 个。它只是位置。

该站点恰当地展示了我希望实现的功能：http: //www.homeaway.com/vacation-rentals/europe/r5

你建议我如何管理这样的数据结构？

我正在使用的东西。

• PHP
• MySQL
• 索尔

我计划让钻取尽可能快。我想创建一个 AJAX 界面，搜索时会无缝。

我也很想知道您建议在哪些列上建立索引。

我在具有 ID 和 ParentID 的数据库中有一个邻接列表来表示树结构：

当然，在一条记录中，ParentID 永远不应与 ID 相同，但我还必须防止循环引用以防止无限循环。这些循环引用理论上可能涉及超过 2 条记录。（ a->b、b->c、c->a 等）

对于每条记录，我将路径存储在一个字符串列中，如下所示：

我现在的问题是：插入/更新时，有没有办法检查是否会发生循环引用？

我应该补充一点，我了解嵌套集模型等。我选择了存储路径的邻接方法，因为我发现它更直观。我让它与触发器和一个单独的路径表一起工作，它就像一个魅力，除了可能的循环引用。

我需要按级别显示类别树（每个级别上的所有树元素）。

我尝试使用嵌套集结构来实现它，但遇到了一个问题：没有简单的方法来获取父节点的 ID（无需单独查询数据库）。我应该改用邻接列表吗？

目标是尽可能快地显示，最好是对数据库进行一次查询。

我承认这是我的功课。任务声明说我必须编写一个程序来查找将由标准输入输入的图的拓扑顺序。然后我需要提交它以在教授的服务器上评分。

现在不是算法问题。这更像是一个技术问题。在我的计算机中，我使用 .NET 编译器 (csc)，而教授的评分机使用某种形式的单声道。

它运作良好，直到评分员说我得到 30/100。我的一个朋友建议我使用评分器的“手动输入系统”，所以我开始了，我让它为邻接列表创建了 100000 个列表的数组。

几秒钟后，评分员报告说我的程序崩溃了。

这对我来说有点奇怪和不安，但我还没有找到答案。同样，这个程序在我的电脑上运行得很好。

这是我的程序的一部分：

非常感谢您，我感谢您的每一个回复。

编辑：我再次查看了评分者的输出，看看我是否遗漏了什么，确实我做到了。它说“syscal：2”，但我只知道“程序没有正常退出”。

编辑#2：我尝试让程序尝试制作各种大小的列表数组，范围从 5000、10000 等，在 40000 之后，“手动输入系统”说程序得到了 System.OutOfMemoryException。进一步研究允许学生进入的评分器的各个部分，似乎教授错误地配置了他的评分参数并且给我们的记忆比宣布的要少。（他说“32MB”，但程序在大约 16MB 时崩溃）

我已经向他报告了这个错误，他（现在）正在调查它。

我正在做一个项目，我从 10-15 个不同的 IP 地址跟踪到某个 IP 地址。大多数跟踪路由在到达同一目的地的途中（跳跃）沿着某些常见的路由器。结果数据给了我一个图表。我认为表示这些数据的最佳方式是邻接表。是否有任何 C 库可以在其中获取此类图的实例并在进行不同的 traceroute 调用时向其添加边（跃点）？

我想写一个最短路径程序。我知道算法是如何工作的，但我不知道从哪里开始

最初，我想使用邻接矩阵，但后来因为空间问题决定放弃它。现在我认为邻接表会更好。

谁能建议我一个网站或教程如何开始编写邻接列表来为程序提供输入？

push_back 时，列表会花费大部分时间来分配内存。另一方面，当需要调整大小时，向量必须复制它们的元素。因此，哪个容器最有效地存储邻接表？

我有一个 800 x 600 的图像。我想把它当作一个矩阵来获取相邻的元素

前任。

(0,0) (1,0) (2,0) (3,0)

(0,1) (1,1) (2,1) (3,1)

(0,2) (1,2) (2,2) (3,2)

(0,3) (1,3) (2,3) (3,3)

示例解决方案： (0,0) 与： (1,0) (0,1) (1,1) 相邻

(1,1) 与： (0,0) (1,0) (2,0) (2,1) (2,2) (1,2) (0,2) (0,1) 相邻

所以我写了一个结构数组，我会将这些点中的每一个存储到

所以我的第一个想法是实施一个 dfs，但这并没有真正奏效，所以我想获得外部意见，以使自己保持在正确的轨道上。谢谢