问题标签 [graph-theory]

当图的节点具有权重时，计算有向无环图的关键路径的最佳（关于性能）方法是什么？

例如，如果我有以下结构：

关键路径应该是A->B->F（总权重：10）

基于经典 GIS 格式的地理数据。这些矩阵是不同车辆路线问题等的基本输入。它们通常可以在最佳时间或最短距离的基础上产生。

谁能告诉我，在网上哪里可以找到 Bron-Kerbosch 算法的解释，或者在这里解释它是如何工作的？

我知道它发表在“算法 457：找到无向图的所有派系”一书中，但我找不到可以描述该算法的免费资源。

我不需要算法的源代码，我需要解释它是如何工作的。

我需要一个像这样的树/有向无环图实现：

• 没有任何类型的排序。
• 这TreeNode只是键和可能值的包装器（节点不必设置值）。
• 我需要链接到父母和孩子。

标准 API 或 Commons 等中是否有任何东西可以为我做到这一点？

我不介意自己写（我当然不会要求你们这样做）我只是不想重新发明轮子。

好奇什么被认为是判断有向无环图强度的可靠算法/方法 - 特别是某些节点的强度。我对此的主要问题可以归结为以下两个图表：

（如果图表未显示，请单击此处或访问此链接：http ://www.flickr.com/photos/86396568@N00/2893003041/

在我看来，A 的地位比 A 强。我判断强度的依据是如果一个链接被击倒，一个节点可以保持多强。我称第一个为细“高跷”，第二个为粗“茎”。

以下是我目前考虑的判断节点强度的方法：

1）计算下面的节点数，减去上面的节点数。

• A=7, a=7, B=5, b=1

2）计算每个节点的完整路径（到终止）的数量，将它们的长度相加。

• A=17 (1+5+5+5+1), B=12 (4+4+4), a=9 (3+3+3), b=2
• 这使高跷更坚固，而不是茎。

3）计算每条可能的路径，将每个节点视为目的地。

• A=9 (A->B, A->C, A->D, A->E, A->G, 2xA->F, 2xA->H), B=6, a=9, b= 2

到目前为止，3 似乎是最好的选择，但有没有更好的、适用于 DAG 的通用选项？这是具有已知最佳方法的东西吗？原则是在图表中使用尽可能多的信息，并以直观的方式解释解决方案。

我有几种类型的实体，每种都有自己的字段，它们存储在单独的表中。
这种表中的每条记录可以连接到不同表中的零个或多个记录，即链接到来自不同实体类型的记录。
如果我使用查找表，我会得到 (m(m-1))/2=O(m^2) 需要初始化的单独查找表。
虽然对于 6 或 7 种不同的实体类型仍然可行，但它仍然适用于 50 多种此类类型吗？
特别是，给定的记录需要与大多数其他实体类型有链接，所以从理论上讲，我将处理一个几乎完整的、无向的 n 边图。
任何人都可以阐明如何将这种结构存储在关系 DBMS 中吗？
（如果重要的话，我正在使用 Postgresql，但其他 DBMS 的任何解决方案都同样有帮助）。
感谢您的时间！

尤瓦尔

我正在尝试更熟悉需要解决图形的问题（最好通过图形解决）。

如果有人有一个使用图表的旧 ACM 编程竞赛问题，或者在他们解决问题时发现另一个特别有启发性的问题，我将不胜感激。我想熟悉图形，轻松识别图形类型问题并能够利用基本的图形遍历算法。

任何人有一个甜蜜的问题，他们可以发送我的方式？

我正在解决前几年的 ACM 编程竞赛问题，试图更好地解决图形问题。

我现在正在处理的一个是给定任意数量的无向图节点、它们的邻居以及连接节点的边的距离。我需要的是两个最远节点之间的距离（权重距离，而不是节点数）。

现在，我确实有以下形式的 Dijkstra 算法：

通过这个实现，我可以给它一个特定的节点，它会给我一个到该节点的所有距离的列表。因此，我可以在该距离列表中获取最大距离，但我不能确定任何特定节点是两端最远的两个节点之一。

所以我能想到的唯一解决方案是在每个节点上运行这个 Dijkstra 算法，遍历每个返回的距离列表并寻找最大距离。在用尽每个节点返回它的距离列表后，我应该有任何两个节点之间最大距离的值（两个最广泛分离的村庄之间的“道路”距离）。必须有一种更简单的方法来做到这一点，因为这看起来在计算上确实很昂贵。问题是可能有多达 500 个节点的样本输入，所以我不希望它花费太长时间。这是我应该怎么做的吗？

这是该问题的示例输入：

节点总数：5

边：
节点 2 - 连接 - 节点 4. 距离/权重 25
节点 2 - 连接 - 节点 5. 距离/权重 26
节点 3 - 连接 - 节点 4. 距离/权重 16
节点 1 - 连接 - 节点 4. 距离/权重 14

此示例输入的答案是“67 英里”。这是两个相距最远的村庄之间的道路长度。

那么我应该按照我描述的方式去做，还是有一种更简单、计算成本更低的方法？

Garmin 和 TomTom 等导航系统一直让我着迷。我想实现小型地图/导航应用程序来尝试各种路径算法并扩展我对它们的了解。

这是一个两部分的问题：

1.) 地图数据如何存储？ - 当您拥有道路网络时，这些数据通常如何存储？保留哪些部分数据以便以后重现地图？每条道路是否存储为一系列改变方向的点？这些数据以何种文件格式存储？是否有公开可用的库来轻松解析这些文件？有没有人有关于如何存储/表示地图/道路数据的细节，这将非常有帮助。

2.）导航/路径 - 在此地图数据（la Garmin）上进行基本路径时，我的假设是否正确，即它被转换为有向图？每个道路交叉点是否是一个顶点，边缘加权顶点之间的距离？这就是我正在考虑做的，所以我可以尝试一些基本的众所周知的路径算法，看看我得到了什么。

我已经在美国看到了这个公开可用的地图数据，但我不确定它是如何表示的，以及它是否足够详细，让我能够从中构建我的有向图。

如果有人有任何信息，我将不胜感激。掌握的知识越详细越好。

我想知道是否有人可以推荐一个好的 C++ 树实现，如果可能的话，希望它是兼容 stl 的。

作为记录，我以前写过很多次树算法，我知道这很有趣，但如果可能的话，我想变得务实和懒惰。因此，与工作解决方案的实际链接是这里的目标。

注意：我正在寻找通用树，而不是平衡树或地图/集，在这种情况下，结构本身和树的连接性很重要，而不仅仅是其中的数据。所以每个分支都需要能够保存任意数量的数据，并且每个分支都应该是可单独迭代的。