我正在尝试在离散能源地形图上找到两个极大值之间最短的路径，其中最短路径是指其在整个路径过程中高度下降最少的路径。也许最大能量路径更正确，但换句话说，即使路径绕着地形图走了很长的距离，但没有进入山谷，这也被认为是好的。 我的初始想法是创建一个地形图的图形，其中权重是相邻之间地形高度差异，上升和...

我正在开发一个基于一些流行的Python包的开源图形和网络近似算法库。主要目标是包含最新的图形和网络NP完全问题的近似算法。原因在于1）我还没有看到一个很好（现代化的）综合套件来覆盖这个领域，2）它将是一个很好的教学工具，用于学习NP难优化问题上的近似算法。 在构建这个库时，我使用单元测试进...

有没有一种算法可以找到一个无向图的生成树，使连接多于一条边的顶点数量最小化？ 例如，给定一个4 x 4的网格图，我们想要找到一个生成树，像左边那样（有7个顶点连接多于一条边），而不是右边那样（有12个顶点连接多于一条边）： 编辑：如果我们只考虑平面图（甚至只考虑网格图），那么这个问题会...

DFS 带着颜色的时间复杂度为 O(V+E)，而并查集的时间复杂度为 O(ElogV)。 参考资料：http://www.geeksforgeeks.org/detect-cycle-undirected-graph/ 因此，并查集方法更慢。 如果 V=100，E=100，则 DFS=200...

有很多谜题是"Konigsberg的7座桥"谜题的变体，你必须在不重复使用门的情况下找到一组房间的路径。 以下是一个无解的例子。 以下是稍作修改并有解的谜题。 我对以编程方式解决这些问题很感兴趣。虽然有很多方法可以确定特定房间和门的组合没有解，但我对计算访问门列表来解决谜题很感兴趣。...

我有一个DAG（有向无环图）来存储应用程序中某些对象之间的关系。当通过在现有顶点下方添加新顶点（即隐式创建一个新边缘）并随后（在任何晚些时候）从那里到其他顶点添加新的边缘时，我希望确保图形保持为DAG，也就是我的代码不会创建循环。 我是否需要将循环检测添加到每个插入和连接操作中，或者是否有我...

假设G是一个图。因此，G是一组节点和一组链接。我需要找到一种快速的方法来对图进行分区。我现在处理的图只有120×160个节点，但我可能很快就会在另一个上下文（不是医学，而是网站开发）中处理具有数百万个节点的等效问题。 所以，我将所有链接存储到一个图矩阵中： M=numpy.mat(nump...

我正在寻找一种在图中寻找欧拉路径的算法。 我几周前看到了一个很好的算法，但现在无法找到它，我记得其中有标记边，涉及偶数/奇数连接...... 你知道类似的、简单明了的算法吗？

我一直在通过观看Christopher Bishops的视频（http://videolectures.net/mlss04_bishop_gmvm/）学习如何使用图形来进行机器学习，我发现这非常有趣，并观看了一些其他与机器学习/图形相关的视频，但是想知道是否有人有更多的学习建议？ 我的问题...

我有一个无向的、正边权重图(V,E)，我想要覆盖顶点子集k的最小生成树（史泰纳树问题）。 我不限制生成树的大小为k个顶点；相反，我知道需要在MST中准确地包含哪些k个顶点。 从整个MST开始，我可以逐渐缩减边和节点，直到得到包含所有k的最小MST。 我可以使用Prim算法获得整个MST，...