问题标签 [graph-theory]

我正在查看 Prim 算法的Wikipedia 条目，我注意到它与邻接矩阵的时间复杂度为 O(V^2)，而其与堆和邻接列表的时间复杂度为 O(E lg(V))，其中 E 是边数和 V 是图中的顶点数。

由于 Prim 算法用于更密集的图中，E 可以接近 V^2，但是当它接近时，堆的时间复杂度变为 O(V^2 lg(V))，大于 O(V^2)。显然，与仅搜索数组相比，堆将提高性能，但时间复杂度另有说明。

算法实际上是如何随着改进而变慢的？

所以，我理解在图中找到最长简单路径的问题是 NP-hard，因为您可以通过将边权重设置为 1 并查看最长简单路径的长度是否等于边缘。

我的问题是：如果你画一个图，找到最大边权重，m用 替换每个边权重w，m - w然后运行标准最短路径算法，你会得到什么样的路径？这显然不是最长的简单路径，因为如果是，那么 NP = P，我认为类似的证明会更复杂一些 =P。

有人可以解释广度优先搜索来解决以下问题吗

我需要找到 4 到 7 之间的所有路径

我正在编写一个操作某种社交网络数据的应用程序，因此理想的底层数据结构是加权有向图。我想直接对数据进行操作（和搜索），而不是先将整个图形加载到内存中并在之后进行序列化。

这可以使用标准 SQL 数据库或键/值存储来模拟，但这会非常低效（对于我想使用的图遍历算法，例如最短路径等）。

由于谷歌搜索没有找到任何有用的结果，因此我有点想自己写，但我更愿意使用现有的解决方案（如果有的话，我错过了），而不是重新发明轮子。该项目是为了娱乐/个人研究，因此软件必须是开源的（并且最好能够在 Linux 下运行）。

那么，有没有符合上述描述的项目？

谢谢！

我有一个 DAG，用于存储我的应用程序中某些对象之间的关系。当通过在现有顶点下方添加新顶点来更新此结构时（即，在新顶点中隐式创建新边），然后（在以后的任何时间）从那里到其他顶点的新边，我想确保图保持 DAG，即我的代码不会创建循环。

我是否必须为每个插入和连接操作添加循环检测，或者是否有可以在插入时遵循的规则来保证我不会产生循环？

我能想到的一种方法是存储每个节点的拓扑级别，并且只允许指向更高级别（离源节点更远）的新边。但是，这似乎实际上会剥夺我通过使用 DAG 而不是一组普通树来实现的许多灵活性。

我正在寻找一个（免费）库，它允许我绘制CFG（控制流图）。像yFiles 之类的东西，但免费或最好是开源的？理想情况下，该库将允许用户浏览图形（并对其进行修改），即图形不仅仅是静态的先验渲染位图。想法？

更新：
Glee与上面提到的 QuickGraph 库相结合似乎工作得很好。谢谢

Update2： Graph#似乎是目前最强大的库。还有一个关于如何使用它的不错的教程。

我正在尝试编写（或扩展现有的）图搜索算法，考虑到无法保证节点将被连接，该算法将让我找到最接近目标节点的路径。

为了提供一个实际的应用，假设我需要从安大略省的布兰普顿到安大略省的汉密尔顿。我知道在我的起点我可能的选择是本地交通、GO 巴士或步行。我知道步行是到达目的地最不受欢迎的方式，所以我先看看 GO 巴士。我知道我可以将 GO 带到靠近汉密尔顿的一个点，但是在那一点上，GO 巴士转向另一个方向，在最近的点是我别无选择的地方（除了步行，但算法只会考虑步行对于短距离，否则它将认为该路线不可行）

使用同样的例子，如果算法发现我可以到达那里的方式更长但让我更接近目标节点（或可能在目标节点），这将是一个更高的加权路径（权重不在它的搜索过程中非常重要，只有当结果交付时，它才会按升序列出离目的地最近的路径）。例如，一辆 GO Bus 可以让我距离目的地节点 3 公里，而 3 辆公共交通巴士可以让我距离目标节点 500m

所以我的问题有两个方面：1）我应该从什么算法开始做类似的事情 2）我如何以编程方式解释如果节点不连接也没关系，这样它就不会只是从节点 A 跳转到节点 R。会从头开始并向后工作来完成这个

编辑：我忘了问如何瞄准最佳近似解决方案，因为特别是对于一个大图，这个问题可能会有数百万个解决方案。

谢谢，迈克尔

我正在尝试找到一个简单的 Java API 来创建图形关系。它应该有一些功能，如addEdge(), addNode(), isConnected(node1, node2),findPaths(node1, node2)等。我不需要 UI，只需要逻辑。

我找到了一堆学术项目，但似乎没有一个是“ The Definitive Graph API ”。

有人知道这样的API吗？

我有一个基于瓷砖的地图，其中几个瓷砖是墙壁，其他瓷砖是可步行的。可步行的瓷砖构成了我想在路径规划中使用的图表。我的问题是他们是否有任何好的算法来找到访问图中每个节点的路径，最大限度地减少重复访问？

例如：

地图示例 http://img220.imageshack.us/img220/3488/mapq.png

如果底部的黄色瓷砖是起点，则访问所有重复次数最少的瓷砖的最佳路径是：

路径示例 http://img222.imageshack.us/img222/7773/mapd.png

这条路径有两次重复访问。更糟糕的路径是在第一个路口左转，然后在三个已经访问过的瓷砖上回溯。

我不关心结束节点，但开始节点很重要。

谢谢。

编辑：

我在我的问题中添加了图片，但在查看时看不到它们。他们来了：

http://img220.imageshack.us/img220/3488/mapq.png

http://img222.imageshack.us/img222/7773/mapd.png

此外，在图表中我需要这个，因为永远不会出现 min repeats = 0 的情况。也就是说，要踩到地图中的每个图块，玩家必须至少穿过自己的路径一次。

我有一个类“类”，它有一个成员 std::list，我想在该列表/树中搜索一个项目，特别是一个具有特定名称的项目。我的班级的基本表示如下：

我可以在 Class::findItem 中做这样的事情：

但是，我想要发生的是 findItem() 将“最接近”的项目返回到搜索的项目。例如，如果这是我的树，每个字母代表列表层次结构中的一个级别，每个数字代表项目“值”。我希望 findItem(3) 返回 B(3)，而不是 C(3)。