问题标签 [graph-algorithm]

我正在寻找一种简单的算法来“序列化”有向图。特别是我有一组文件，它们的执行顺序相互依赖，我想在编译时找到正确的顺序。我知道这一定是一件相当普遍的事情——编译器一直都在这样做——但我的 google-fu 今天一直很弱。什么是“首选”算法？

我正在寻找具有一些不寻常属性的图形算法。

图中的每条边要么是“上”边，要么是“下”边。

一条有效的路径可以经过不定数量的“up”，然后是不定数量的“down”，反之亦然。但是，它不能多次改变方向。

例如，有效路径可能是 A “up” B “up” C “down” E “down” F 无效路径可能是 A “up” B “down” C “up” D

什么是找到两个节点之间最短有效路径的好算法？如何找到所有等长的最短路径？

如何从/到给定节点的有向图中找到（迭代）所有循环？

例如，我想要这样的东西：

但不是：B->C->B

我想使用 构建一个新的中心性度量igraph，最好是在R.

我该如何开始呢？

例如，我会更好地添加到igraph C library或R interface吗？

我正在处理一个家庭作业问题，它问我这个问题：

给定一组有限的数字和一个目标数字，找出该集合是否可用于使用基本数学运算（add、sub、mult、div）计算目标数字，并仅使用集合中的每个数字一次（所以我需要用尽集合）。这必须通过递归来完成。

所以，例如，如果我有一套

和目标 10，然后我可以通过使用

我试图用伪代码来表达算法，但到目前为止还没有走得太远。我认为图表是要走的路，但肯定会感谢您对此的帮助。谢谢。

任何人都有 C# 中反向广度优先遍历算法的现成实现？

通过反向广度优先遍历，我的意思不是从公共节点开始搜索树，而是从底部搜索树并逐渐收敛到公共节点。

让我们看下图，这是广度优先遍历的输出：

在我的反向广度优先遍历中，9, 10,11和12将是找到的前几个节点（它们的顺序并不重要，因为它们都是一阶的）。5, 6,7和8是找到的第二个节点，依此类推。1将是找到的最后一个节点。

任何想法或指示？

编辑：将“广度优先搜索”更改为“广度优先遍历”以澄清问题

我正在为.net 框架寻找一个开源（GPL、LGPL 等）图形布局库，最好是完全托管的代码。我不担心事物的可视化方面。

我可以找到很多用于 Java 的，但没有用于 .net 的...

谢谢！

我是整数线性规划的新手。我计划使用整数线性规划求解器来解决我的组合优化问题。我更熟悉 IDE 上的 C++/面向对象编程。现在我大部分时间都在使用带有 Cygwin 的 NetBeans 来编写我的应用程序。

请问是否有适合我的易于使用的 ILP 求解器？还是取决于我要解决的问题？我正在尝试做一些资源映射优化。如果需要任何进一步的信息，请告诉我。

非常感谢你，卡西。

我了解 DFS 和 BFS 之间的区别，但我很想知道何时使用其中一种更实用？

谁能举例说明 DFS 如何胜过 BFS，反之亦然？

给定一个加权图（有向或无向），我需要找到具有最大权重的图的循环。

循环的权重是图的边权重的总和。

它可以是任何循环，而不仅仅是我们可以的基本循环

• 查找所有基环（请参阅在无向图中识别所有环基的算法）
• 计算每个基本循环的权重并找到最大值

我可以尝试枚举图的所有循环，然后计算最大值，但循环的总数可能非常大（如果图是完整的，那么第一个和最后一个相同的任何顶点序列都是一个循环）。

您有什么想法可以在不枚举所有循环的情况下找到最大重量循环吗？

如果您需要图表上的假设（例如正权重），请指出它们。