问题标签 [graph-theory]

我想我已经理解了如下所述的特定情况，但是我缺乏进行证明的理论知识，并且找不到任何提及它的来源。如果我的理解是正确的，我可以在我的邻接矩阵上节省一半的空间，如果不是，我可能会有非常奇怪的错误。所以我想确定一下，如果有更扎实背景的人可以审查我的推理，我将不胜感激。

假设我在 n * n 邻接矩阵中表示 n 个顶点的 DAG，这样条目i,j是否1存在从 vertexi到 vertex的边j，0否则。因为该图是有向图和无环图，所以如果i,j = 1，则j,i = 0。如果我现在对矩阵中的节点进行排序，使得 i _n处的节点的拓扑级别等于或大于 i _n-1处的节点，那么在我看来，邻接矩阵的一半将始终只包含0s ，如下例所示：

也许我是对的，但是有没有正式的方法来检查这个？

以下是我存储在哈希图中的数据集，我必须找到两个值之间的最短路径。

哈希映射的键值是每行的第一个值，其余的是 9244 的假定“朋友”（在每种情况下都相同）。

我以这种格式保存在哈希表中：hashmap(key, array)，其中：

• 密钥是例如 9244
• 然后数组保存 [ 4322, 4886, 5989, 8598, 9979, 1447, 9657 ]

如何找到两个键之间的最短路径？

对于二分图，您可以将邻接矩阵替换为所谓的邻接矩阵：

二部图的邻接矩阵 A 的部分具有 r 和 s 个顶点，其形式为

其中 B 是一个 r × s 矩阵，O 是一个全零矩阵。显然，矩阵 B 唯一地代表了二分图，通常称为它的二分邻接矩阵。

现在，DAG 是一个二分图，例如，您可以对其进行拓扑排序，并让集合 U 和 V 分别作为奇数或偶数拓扑级别的节点。

这意味着，对于具有 n 个节点的 DAG，我只需要一个 (n/2) ²矩阵（平均）而不是²矩阵。问题是，我不知道如何构建它。有什么提示吗？

我需要一个节点的有向循环图的最短路径示例（它应该从将成为输入的节点到达图的所有节点）。

请如果有一个例子，我需要它在 C++ 或算法中。

我有点困惑，试图想出一个好的算法来导航下图。

替代文字 http://www.archimedesinc.biz/images/StackOverflow/Tree.jpg

如果用户选择“表 21”作为起点，我需要能够从该起始表获取到任何其他表的路径。

EX：如果用户选择“表 21”作为开始，然后从“表 8”中添加一个值，我需要创建以下路径“表 21 ->表 12 ->表 9 ->表 6 ->表 8 "，表之间的所有权重都是相同的。

我似乎忘记了自己处理有向图的技巧，想不出一个好的算法。我不是在寻求解决方案，而只是朝着正确的方向前进。

谢谢！

有一个 KSPA 的自定义实现需要重新编写。当前实现使用修改后的 Dijkstra 算法，其伪代码大致解释如下。我认为它通常被称为使用边缘删除策略的 KSPA。（我是图论的新手）。

据我了解该算法，为了获得第 k 条最短路径，将在每个源-目的地对之间找到“k-1”个 SPT，并且对于每个组合同时删除一个 SPT 中的每个“k-1”个边。显然，该算法具有组合复杂性，并且在大图上阻塞了服务器。人们向我推荐了 Eppstein 的算法（http://www.ics.uci.edu/~eppstein/pubs/Epp-SJC-98.pdf）。但是这份白皮书引用了一个“有向图”，我没有看到提到它只适用于有向图。我只是想问这里的人们是否有人在无向图上使用过这个算法？

如果没有，是否有好的算法（就时间复杂度而言）在无向图上实现 KSPA？

提前致谢，

我有一个几何无向平面图，即每个节点都有一个位置并且没有两条边交叉的图，我想找到所有没有边交叉的循环。

这个问题有什么好的解决方案吗？

我打算做的是一种A*类似的解决方案：

• 将最小堆中的每条边作为路径插入
• 使用每个选项扩展最短路径
• 剔除循环回到起点以外的路径（可能不需要）
• 剔除将是第三个使用给定边缘的路径

有没有人看到这个问题？它甚至会起作用吗？

鉴于：

• 有向图
• 节点有标签
• 同一个标签可以出现多次
• 边缘没有标签

我想找到一组最大的（连接的）子图，它们在考虑节点标签的情况下是相等的。

该图可能很大（数百万个节点）有没有人知道一个有效的解决方案？

我正在寻找算法，最好是 Java 实现。

更新：因为这个问题很可能是 NP 完全的。我也会对产生近似解的算法感兴趣。

这似乎至少很接近： 频繁子图

我有一个 XML 文件，它对表示偏序的有向无环图 (DAG)进行编码 。这样的图对于指定依赖关系和查找关键路径等事情很有用。出于好奇，我当前的应用程序是为构建系统指定组件依赖项，因此顶点是组件，边指定编译时依赖项。这是一个简单的例子：

这个 DAG 可以这样绘制：

_{（来源：iparelan.com）}

我想应用一个XSLT 样式表来生成另一个 XML 文档，该文档只包含与偏序的最小元素相对应的顶点。也就是说，那些没有传入边的顶点。示例图的最小顶点集是{A, B, F}。对于我的构建依赖应用程序，找到这个集合很有价值，因为我知道如果我构建这个集合的成员，那么我的项目中的所有内容都将被构建。

这是我当前的样式表解决方案（我正在使用 Apache Ant 的xslt任务在 Java 上使用 Xalan 运行它）。directed-edge-to一个关键的观察是在任何元素中都不会引用最小顶点：

应用此样式表会产生以下输出（我认为这是正确的）：

问题是，我对这个解决方案并不完全满意。我想知道是否有一种方法可以将selectof thefor-each和testof theif与 XPath 语法结合起来。

我想写一些类似的东西：

但这并不符合我的要求，因为该current()函数没有引用外部//vertex表达式选择的节点。

到目前为止，我的解决方案使用XPath 1.0和XSLT 1.0语法，尽管我也对XPath 2.0和XSLT 2.0语法持开放态度。

如果您愿意，这是 Ant 构建脚本：

dot目标生成用于渲染图形的Graphviz Dot 语言 代码。这里是xml-to-dot.xsl：

我有一个带有节点和边的平面图，将平原切成部分。nes

作为and和s的函数的上限是多少？nee/n

我试图找出我可以依靠一些代码使用的内存有多少。

很容易证明它e不超过n*(n-1)/2，但我有一种感觉，它将是一个小整数。对于n ~= 10我有固定节点位置的情况，这将限制高估了 2 倍。