问题标签 [directed-graph]

我需要对有向图的节点进行排序，以使向后流动的箭头数量（与排序顺序相反）最小。

我可以想到算法（例如，不断交换节点，直到没有交换可以改善事情）但我不确定它们运行的​​速度或它们是否达到最佳解决方案。

这个问题的名称和复杂性是什么？

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

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

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

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

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

谢谢！

我正在寻找一种在 PHP 中绘制有向图的方法。（如http://upload.wikimedia.org/wikipedia/commons/0/08/Directed_acyclic_graph.png）。我希望它创建图形的图像，就像 GD 可以输出图像一样。

我在这方面搜索了很多，但我只能找到很多用于绘制一般图形的库（带有条形图等），而不是有向图。

PS我试过通过system()使用dot（linux程序），但不幸的是我没有在服务器上这样做的权限。另外，我无权在服务器上安装 PHP 扩展和类似的东西，所以它应该与普通的 PHP 一起工作（最好只包含一个文件）。

提前致谢。

我正在尝试制定一种算法来找到穿过有向图的路径。这不是一条传统的道路，我找不到任何关于已经完成的类似事情的参考。

我想找到具有最大最小权重的路径。

即如果有两条路径的权重为 10->1->10 和 2->2->2，那么第二条路径被认为比第一条路径更好，因为最小权重 (2) 大于第一条的最小权重 ( 1）。

如果有人能想出办法做到这一点，或者只是向我指出一些参考材料的方向，那将非常有用:)

编辑:: 似乎我忘了提到我正试图从一个特定的顶点到另一个特定的顶点。那里很重要：/

EDIT2:: 正如下面有人指出的那样，我应该强调边缘权重是非负的。

也许它甚至不是一个 DAG，但是在我不确定给它取什么标题之后，它的命名是...

每个节点只能有 0 或 1 条路径 INTO 的数据结构的名称是什么？严格来说，这是一棵树吗？

谢谢

我一直在制作我的第一个网页，该网页将用作基于一系列问题的故障排除指南。题目由上一题的答案决定，因此变成了“选择自己的冒险”。幸运的是，我得到了一张显示所有可能路径的决策流程图，但它看起来像东京地铁地图。我首先创建了一系列面板，每个面板都包含问题和一个下拉列表控件，其中包含作为文本的答案和它应该位于前面的面板的 ID。接下来我创建了一个类来将所有面板组织成一个图形结构。通过这个类，我能够知道选择哪些面板的顺序，哪些面板没有被选择，并且很容易对决策流程进行更改。

下面是我如何在 pageload 事件中使用该类的示例，下面是实际类。

由于我对 asp.net 不是很熟悉，我只是想知道是否有更好的方法来解决这个问题，以及我的代码中是否存在缺陷。我的代码正在运行，但我确信可能会有改进。

这是课程

我有一个有向循环图。有些边缘是固定的，可能不会被移除。可以移除其他边缘以中断循环。

删除此图中的循环的最佳方法是什么？遍历应该尽可能多地是 DFS，并从给定节点开始。

使用点有向图语言，是否可以创建具有不同 rankdir 的子图？

我尝试了以下方法，但没有成功。尽管子图中存在 rankdir="TB"，但这两个图都是从左到右的。

是否有其他语法可以在同一个图中获得上/下和左/右图，或者这不可能？

我需要一个 .NET 应用程序中最多 4 维的稀疏矩阵。矩阵的大小（如果表示为 .NET 数组）可能会超过 400MB。

该数组可能非常稀疏，我需要能够非常快速地实例化和处置它（尽管这不是不行）。因此，我需要一个稀疏数组库，它可以从 .NET 3.5 中使用（我认为排除了使用托管 C++ 中的 BGL？），它尽可能密集，并且支持快速随机访问索引。它必须可序列化为一些可以廉价缓存的密集格式。

.NET 是否存在这样的事情（还存在）？开源软件？成熟？

TIA

安德鲁·马修斯

我正在寻找有关如何对包含一个特殊节点的有向图进行建模的意见。

特殊节点：

1. 不能有任何边缘通向它。
2. 无法删除。

当前设计：

表：节点、边。Edges 包含两列；from_node_id 和 to_node_id，每个都引用 Nodes 表中的一条记录。

我没有将特殊节点存储为 Nodes 表中的第一条记录，而是决定根本不为其保留记录，而是将其与任何数据库查询分开构建。在 Edges 表中，NULL 在 from_node_id 列中具有特殊含义，指的是中心节点。

我使用这种设计的动机是我不必担心保护中心节点记录不被删除/修改或在 Edges 表的 to_node_id 列中被引用。这也将自动阻止一条边进出同一个节点。我意识到这种设计有一些缺点，例如无法将 from_node_id 和 to_node_id 设为复合主键，可能还有更多。

我目前倾向于使中心节点成为实际记录并在相关数据库方法中为该节点创建检查。这种设计的最佳方式是什么？