查找平方矩阵上2个点之间的所有路径
重复标记之前请仔细阅读！ 我有一个矩阵： 0 0 0 x 0 0 0 0 0 0 0 0 0 0 0 0 x 0 0 0 0 0 0 0 0 您不能在矩阵中对角移动！ 我想找到两个“ x”之间的所有可能路径。唯一的条件是，路径不能自身交叉（因此没有循环）。显然，DSF算法无法找到每个单独的路径（要了解原因，请参阅本文： http://www.algo
..
graph-theory相关内容
图的集团数
我想知道一种快速算法，该算法仅查找具有约100个顶点的图的团数（实际上未找到团）。 我正在尝试解决以下问题。 http://uva.onlinejudge.org/external/1/193。 html 解决方案 这是NP完全的，并且比实际找到最大值要好得多集团并计算其顶点。来自维基百科： 集团问题包括： 解决测试图是否包含大于N的集团的决策问题。 这些问题都很
..
寻找节点的t友的算法
我进行以下练习，下面是一个社交图。根据我的理解，如果 t = 2 并且我们具有 p = H ，那么结果将等于 O和B 。 这种理解正确吗？ 解决方案 从原点开始进行广度优先搜索。当您使一个点入队时，也要使其与原点的距离也入队。通过不使距离大于 t 的点入队，将距离限制为 t 。被访问的节点集就是解决方案。 您最多可以访问每个顶点一次，最多可以访问每个边缘一次。复杂度是 O（E）
..
从一个节点A到节点B的最大边缘权重
给出一个具有 N 个节点（1 N 边缘。让我们定义一个函数 F（a，b），其中 F（a，b）等于从 a 到 b 。我们如何找到所有 a ， b 的 F（a，b）的总和，使得 1
..
单源最短路径，每个边缘具有距离和权重
假设有一个无向图，并且连接任意两个节点的每个边都有两个权重（即距离和成本）。我想获得最短的路径，但还要确保我不会超出一定的成本。 我尝试实现Djikstra的方法，只是回溯（因为缺少如果我超出成本，则可以遍历整个图表。但是，我正在寻找比这更快的解决方案。我也尝试使用给定边的距离和成本来创建权重的函数，但我认为这不会返回最佳解决方案。 有什么想法吗？ 解决方案 我们可以使用 E
..
检测图形中是否存在负周期的最快算法
我使用矩阵 d 表示图表。 d。（i）。（j）表示 i 和 j之间的距离; v 表示图中的节点数。 此图中可能存在负循环。 我想检查是否存在负循环。我从 Floyd-Warshall 的变体中写了以下内容： let dr = Matrix.copy d in （* part 1 *） for i = 0至v-1做 博士（i）。（i）完成; （*第2部分*） 尝试
..
为什么贪心算法没有找到二部图的最大独立集？
我试图使用贪婪方法解决二部图上的最大独立集问题。因此，碰到了这个帖子，它正是我想要做的。但是我只专注于二部图。答案中的反例不是二部图。 Greedy（G）： S = {} 当G不为空时： 设v为G中具有最小度的节点 S = union（S，{v}） 从v $ b $中删除v及其邻居b返回S 解决方案 与也适用于此处，但图形略有修改：
..
为什么使用逆阿克曼函数来描述Kruskal算法的复杂性？
在一类用于算法分析的类中，向我们展示了Kruskal算法的伪代码： 然后针对不相交的森林陈述以下内容： m的序列MAKE-SET，UNION和FIND-SET操作，其中n个 是MAKE-SET操作，可以在最坏情况下通过等级和路径压缩对不相交集林 进行联合 O（mα（n））。 用于计算第2步和第5-8步的复杂度 对于已连接的G：| E | ≥| V | -1; m = O
..
如果减少一个边缘权重，则更新最短路径距离矩阵
我们得到了一个加权图G及其最短路径距离的矩阵增量。因此，delta（i，j）表示从i到j的最短路径的权重（i和j是图的两个顶点）。最初给出 增量，其中包含最短路径的值。边缘E的权重突然从W减小到W'。如何更新O（n ^ 2）中的delta（i，j）？ （n =图的顶点数） 问题不在于再次计算具有最佳O（n ^ 3）复杂度的全对最短路径。问题是更新三角洲，因此我们无需重新计算所有对最短路径。
..
连接偶数个节点而不交叉
我有两组n个节点。现在，我要连接一组中的每个节点与另一组中的另一个节点。生成的图形应该没有相交。 我知道几种扫掠线算法（ Bentley-Ottmann-Algorithm 来检查相交的位置，但是除了蛮力方法外，我找不到解决这些相交的算法。 一组中的每个节点都可以连接到另一组中的任何其他节点。 指向（an EDIT1 ： 这是 n = 7 的问题的一种解决方案：
..
使用Tarjan算法枚举图形中的循环
我正在尝试使用Tarjan的算法确定有向图的循环，该算法在1972年9月发表在他的研究论文“有向图的基本电路的枚举”中。 我正在使用Python编写算法代码，并使用邻接表来跟踪节点之间的关系。 因此，在下面的“ G”中，节点0指向节点1，节点1指向到节点4,6,7 ...等。 G = [[1]，[4，6，7] ，[4、6、7]，[4、6、7]，[2、3]，[2、3]，[5、8]
..
是否有用于平面度测试的在线算法？
我知道平面度测试可以在O（v）（相当于O（e ），因为平面图具有O（v）条边）的时间。 我想知道是否可以在O（1）摊销时间内在线添加每条边（换句话说，在表示图表边缘并受制于表示图表是平面的约束的数据库表中，如何负责管理约束的DBMS必须花多少时间来验证每个建议的插入？ （为简化起见，假设没有删除。）是否必须重新运行O（v）平面度测试算法之一来测试每个建议的插入或插入组？ 解决方案 经
..
如何将无向图转换为DAG？
Wiki页面说 任何无向图都可以通过选择其顶点的总顺序并将每个边缘从顺序中较早的端点定向到较晚的端点而制成DAG。 但是我不知道如何获得无向图的总阶。我应该使用DFS吗？如果是这样，我将如何进行？ 更多信息：我正在处理一个有向源和一个汇的无向图。我正在尝试引导这些边缘，以便按照边缘方向从源到接收器。 解决方案 总的顺序基本上只是将所有顶点按某种顺序排列-将其视为用1到|
..
解决此分布珠难题的算法？
假设您有一个带有 N 个斑点的圆圈（如下所示），并且您在插槽中分布了 N 个珠子。 这里是一个例子： 每个珠子可以顺时针移动 X 个广告位，费用为 X ^ 2 美元。您的目标是在每个插槽中放置一个珠子。您必须花费最少的钱才能完成这项任务？ 此问题的更有趣的变化：分配珠子拼图的算法（2）？ 解决方案 在这个答案中，我假设珠子只能移动一次。否则，很明显珠子一次只能移动一个方块
..
合并共享至少2个元素的集合的算法
给出一组列表： S_1：[1，2，3，4] S_2：[3、4、5、6、7] S_3：[8、9、10、11] S_4 ：[1，8，12，13] S_5：[6，7，14，15，15，16，17] 最有效的方法是合并所有共享至少2个元素的集合？我想这类似于连接组件的问题。因此结果将是： [1，2，3，4，5，6，7，14，15，16，17 ]（S_1 UNION S_2 UNI
..
如何删除未加权有向图中的循环，以使边的数量最大化？
让G是一个包含循环的未加权有向图。我正在寻找一种算法，该算法可以查找/创建所有非循环图G'，该图由G中的所有顶点和G的边的子集组成，正好足以使G'变为非循环。 更正式：所需算法消耗G并创建一组非循环图S，其中S中的每个图G'满足以下属性： G'包含G的所有顶点。 G'包含G的边的子集，这样G'是非循环的。 G'的边数最大。这意味着：没有G''满足属性1和2，因此G''包含更多的边，
..
通过修改边更新最小生成树
带有MST 的图（正重边）如果将某些边e修改为新值，那么更新MST而不完全重新生成MST的最佳方法是什么。我认为这可以在线性时间内完成。而且，似乎我需要基于以下两种算法：1）e是否已经是MST的一部分，2）新边缘e是否大于或小于原始边缘 解决方案 有4种情况： Edge is在MST中，并且您降低了edge的值： 当前的MST仍然是MST Edge不在MST会降低边的值
..
寻找找到欧拉路径的算法
我正在寻找一种算法来在图中找到欧拉路径。 几个星期前我见过一个不错的产品，但现在找不到了，我记得有标记边缘的东西，连接偶数/奇数。 .. 您知道类似，简单且直接的算法吗？ 解决方案 从 Graph-Magics.com 中，对于无向图，这将为您提供相反的顺序，即从终点到起点： 从一个空堆栈和一个空电路开始（欧拉路径）。 如果所有顶点均具有偶数阶，请选择其中任意一个。
..
使用DFS在有向图中找到最长的周期
我需要使用DFS在有向图中找到最长的循环。 我曾经见过这篇Wikipedia文章，描述了这样做的方法，并且我认为它已经接近该问题类似于将节点标记为以下三种状态之一：节点尚未访问，完成搜索节点以及节点已访问但尚未完成访问。 如果有人可以与我分享链接，将不胜感激。顺便说一下，它不是塔里安的算法。 下面的问题是我要解决的问题，以防万一您想知道。 > 第一行中给出的两位数字是N和M
..
此示例中DFS与BFS之间的区别？
在阅读 DFS 中的示例后，我有点困惑两种DFS方法都以不同的方式打印 ，尽管两者都被称为DFS。 实际上，DFS递归方法与 BFS 。那有什么区别呢？ 使用堆栈 //使用堆栈 的迭代DFS public void dfsUsingStack（Node node） { Stack stack = new Stack（）; stack.ad
..