如何连接两个点而不穿越其他路径？
假设我有以下网格。我需要连接字母对。不仅必须连接相同的字母，还必须确保连接路径不交叉。有什么算法可以告诉我是否可能连接所有的配对而不交叉路径并且找到最短路径？ 我意识到这是一个图形问题，最短路径部分可以使用BFS解决。我不确定的是交叉路径。 +---+---+---+---+---+-...
如何用1、0、-1权值找到精确为0成本的多维路径
我得到了一个有n个节点和边的有向图，每条边都有一个长度为m的由1、0、-1数字组成的向量权重。我想找到任意一条路径（或者说这样的路径不存在），从一个节点到另一个节点（我们可以多次访问节点），使其权重之和等于只包含零的向量。我考虑使用暴力回溯算法，但不能保证它会结束。我们能否通过限制路径长度来控...
实现常见子表达式消除
我正在研究实现公共子表达式消除（CSE），以处理对应于大型数学表达式的表达式图（数百万个节点）。 哪些算法适用于执行此操作？我在互联网上搜索了易于实现的算法，但未找到任何内容。如果可能，该算法应具有与完整表达式图中节点数量成线性关系的复杂度。
寻找循环：深度优先搜索与并查集哪个更好？
DFS 带着颜色的时间复杂度为 O(V+E)，而并查集的时间复杂度为 O(ElogV)。 参考资料：http://www.geeksforgeeks.org/detect-cycle-undirected-graph/ 因此，并查集方法更慢。 如果 V=100，E=100，则 DFS=200...
如何计算2D平面上由一系列点组成的多边形数量？
如下图所示，我的问题是如何确定由一系列点形成的多边形。 在左侧的图片中，一系列点为 {A, B, C, D, E, A}，因此仅形成一个多边形 {A, B, C, D, E}。 在右侧的图片中，一系列点为 {A, B, C, D, E, F, A}。它创建了2个多边形{A, F, G}和 ...
如何以最快的方式找到两个不同集合中符合某些条件的坐标之和？
我有以下两个集合。找到每个集合中的一个坐标，使它们的和至少为H，最佳方法是什么。 A = {(x1,y1), (x2,y2),....(xn,yn)} B = {(p1,q1), (p2,q2),....(pn,qn)} 如果答案是（x1，y1）和（p1，q1），那么它应该满足 x1+p...
算法简化（地铁）地图
这可能有点难度，但在开始艰苦的工作之前，我想试一试。 我的项目是构建一个应用程序，将给定的输入站点（顶点）和线路（边缘），即某些公共交通地图，转换成地铁图。我对这个问题进行了一些研究，发现它是一个NP完全问题，相当于3-SAT问题。我也有一些理论上的想法可以生成这样的地图，但它们不够详细。 ...
高效地查找所有连接的诱导子图
是否存在一种有效的算法来查找有标签顶点的连通无向图的所有连接（诱导）子图？ 我知道，在一般情况下，由于对于一个团（Kn），有2^n个连通子图，因此任何这样的算法的复杂度可能为O（2^n）。然而，我通常处理的图形将具有更少的连通子图，因此我正在寻找一种方法来生成它们，而不必考虑所有2^n个子图并...
一次性力导向图绘制算法
我正在寻找一种单次算法（或编写它的想法），可以计算有向、无权图的二维或三维坐标。顶点唯一的元数据是标题和类别。 我需要以这种方式实现该算法，即可以添加/删除顶点而不必重新计算整个图结构。 该算法必须应用于一个大型（5GB）数据集，该数据集不断变化。 我的谷歌搜索结果显示出n-pass算法...
PageRank的大O复杂度是什么？
我正在寻找PageRank算法的Big-O复杂度。我很难找到任何有用的信息，只找到了 O(n+m) （n - 节点数，m - 弧/边数），但我目前不相信这个复杂度。 我认为它缺乏收敛标准。我认为这并非恒定值，而是取决于图直径的收敛。可能只需要考虑一次迭代的Big-O，那么收敛就不重要了。 ...