问题标签 [directed-graph]

给定这样的锦标赛图表：您如何系统地找出有多少排名？帮助/解释将不胜感激。

是否有可用于创建有向图的库或类，谁的边也支持容量？（或者我必须自己创建它？）。

我想测试我最近学到的最大流量算法

我想实现一个函数，它从有向循环图 G 中的源顶点 V 找到所有可能顶点的所有可能路径。

现在性能无所谓，我只是想了解一下算法。我已经阅读了深度优先搜索算法的定义，但我没有完全理解要做什么。

我没有任何完整的代码可以在这里提供，因为我不知道如何：

• 存储结果（连同 A->B->C-> 我们还应该存储 A->B 和 A->B->C）；
• 表示图（有向图？元组列表？）；
• 使用多少递归（使用每个相邻的顶点？）。

如何在 Erlang 的有向循环图中从一个给定的源顶点找到所有可能的路径？

UPD：根据到目前为止的答案，我必须重新定义图定义：它是一个非循环图。我知道如果我的递归函数遇到一个循环，它就是一个无限循环。为了避免这种情况，我可以检查当前顶点是否在结果路径的列表中 - 如果是，我停止遍历并返回路径。

UPD2：感谢发人深省的评论！是的，我需要找到从一个源顶点到所有其他顶点没有循环的所有简单路径。

在这样的图表中：

对于源顶点 A，算法应该找到以下路径：

• 甲，乙
• A,B,C
• A B C D
• 广告
• 甲、丁、丙
• A,D,C,B

下面的代码完成了这项工作，但它不能用于具有超过 20 个顶点的图（我猜这是递归的问题 - 占用太多内存，永远不会结束）：

UPD3：

问题是常规的深度优先搜索算法将首先进入路径之一：（A，B，C，D）或（A，D，C，B）并且永远不会进入第二条路径。

无论哪种情况，它都是唯一的路径——例如，当常规 DFS 从 (A,B,C,D) 回溯时，它会返回到 A 并检查是否访问了 D（A 的第二个邻居）。并且由于常规 DFS 为每个顶点维护一个全局状态，因此 D 将具有“已访问”状态。

所以，我们必须引入一个依赖于递归的状态——如果我们从 (A,B,C,D) 回溯到 A，我们应该在结果列表中有 (A,B,C,D) 并且我们应该在算法开始时将 D 标记为未访问。

我试图优化尾递归的解决方案，但该算法的运行时间仍然不可行 - 遍历一个由 16 个顶点组成的小图大约需要 4 秒，每个顶点有 3 条边：

有什么想法可以在可接受的时间内运行吗？

我想知道是否有一种算法可以计算有向图中的最小生成树（最佳分支），给定所有这些根顶点之间的一组根顶点，但不仅仅是一个根顶点和图中的所有其他顶点.

给定一组根顶点 [1,4,6] 和一个图 G，如下图所示：

...算法应该在同一张图片上返回类似绿色子图的东西。

我想得到这样一个 MST，它连接提供给算法的所有根顶点。我倾向于认为可能算法的结果是图 G 的子图，其中包含 G 的所有根顶点和一些其他顶点。

笔记：

1. 我知道有向图没有 MST，但有Chu-Liu/Edmonds 算法。
2. 我猜这种算法的结果（如果实际上可能的话）将返回一个最佳分支，其中包括图的一些顶点以及所有根顶点。

我有两个顶点列表：V和S.

我想从等生成所有可能的有向图V，S每个顶点V只有一个出边和一个入边，每个顶点S可以有任意数量的入边和出边。结果中的每个图都应包含来自V和 的所有顶点S。结果可以包含连通图和不连通图。

首先我认为这是一个与 powerset 相关的问题，但是 powerset 有许多其他的集合可能只包含一个元素（我不需要那些）。

我目前的策略是：

• 找到顶点之间的所有对V，添加到Pairs；
• 找到顶点之间的所有对S，添加到Pairs；
• V从和中找到所有顶点之间的对S，添加到Pairs;
• 生成大小不小于V这样的对子集，每个子​​集在第一个位置恰好有一个顶点v实例，在第二个位置有一个顶点实例，以及来自任何位置v的任意数量的任何顶点实例.sS

我不确定这是否正确，我想知道任何想法。

也许我可以从中创建一个完全连接的图G，V然后S以某种方式从中提取子图？（也许在 digraph:utils 的帮助下）

PS 我正在尝试在 Erlang 中解决这个问题，因为它是我现在正在使用并积极学习的语言。但我很高兴在答案中看到 Java、Ruby 或伪代码。

到目前为止，我已经找到了这篇论文。它过时了吗？有没有更快更好的实现？

顺便说一句，维基百科说在无向图中可以有 n^n-2 棵生成树。有向图中可以有多少棵生成树？

假设我们有一个完全连通的有向图G。顶点是[a,b,c]。每个顶点之间都有两个方向的边。

给定一个起始 vertex a，我想在所有方向上遍历图形并仅在遇到路径中已经存在的顶点时才保存路径。

所以，函数full_paths(a,G)应该返回：

我不需要像[{a,b}]or这样的“不完整”结果[{a,b}, {b,c}]，因为它已经包含在第一个结果中。

除了生成 G 的幂集并过滤掉一定大小的结果之外，还有其他方法吗？

我该如何计算？

编辑：正如 Ethan 指出的，这可以通过深度优先搜索方法来解决，但不幸的是我不明白如何修改它，使其在回溯之前存储路径（我使用 Ruby Gratr来实现我的算法）

我从老师那里得到了一些我们应该用来测试程序的输入文件。任务是从文件中读取，创建有向图并打印输出。但是如果有一个循环，我们应该终止程序。

我有一些名为house1 和house2 的文件。在文件 house1 中没有任何循环，但在 house2 中有。但我不知道为什么我的程序找不到那个循环。在这里我有所有的代码，任何关于我应该在哪里看的帮助都是珍贵的:)

我目前正在开展一个项目，该项目使用有向超图框架枚举动态程序的 k 最佳解决方案。我当前的实现（在 Python 中）运行良好，但速度相当慢。该算法执行许多紧密循环和相当多的递归。我真的认为我可以使用 C++ 实现显着提高速度。然而，经过一番搜索，我找不到任何在 C++ 中提供超图实现的库（特别是有向超图——但我什至找不到无向超图的库）。有人知道这样的图书馆吗？几年前似乎有一个 GSoC 提议来提升对超图的支持，但看起来它并没有真正成功。

假设我们有一个G带有N顶点和M边的完全连接的有向图。

图有多少条边？是M = N^2吗？

如果我们取一个顶点并开始以“深度优先搜索”的方式访问它的邻居并避免循环，我们将获得多少非循环简单路径？

例如，如果我们从 4 个顶点的图中的顶点 1 开始，则路径如下：

N!带有顶点的图是它还是更多N？我找不到一种方法来概括这一点并推导出一个可用的公式。