在无向图中寻找负圈
我试着用谷歌搜索，但是没有任何有价值的东西弹出。
图表：
- 它是无方向的
- 表示为具有双边的有向图
- 可能包含具有负权重的边
我知道我可以使用Bellman Ford在有向情况下解决这个问题，但是对于无向边，它只返回单边（2个循环）作为其输出。我需要找到一个循环的大小
此外，该算法应该具有运行时复杂性O（V*E）和内存复杂性O（V）。
共有1个答案
在Belman Ford算法中，在步骤2中，考虑使用每一个边（u，v）来找到V的较短路径，并且如果看到改进，则通过设置前驱[V]＝U来记录它，这意味着在每个阶段中，你知道每个节点的前身-因此，你可以通过检查前一个[U]！来消除长度两个周期。设置前导[v]=u之前的v。
通过消除这些循环，您可以改变归纳的不变量-在每个阶段，您现在可以找到从s到u的最短路径，最多有i条边，其中不包括任何长度为2个循环。
可以从源访问的长度为3或更大的循环仍然会显示-在您应该找到长度达到访问每个顶点所需长度的每个最短路径后，检查负循环会寻找明显的改进。
例如：考虑G={{A，B，C，D}，{AB=2，AC=2，BC=-3，BD=1，CD=1}。
更新，更新B，然后更新C，然后更新D：
A=0， B=C=D=无穷大
A=0，B=2来自A，C=-1来自B，D=0来自C
A=0，B=1来自D，C=-2来自B，D=-1来自C
A=0，B=0来自D，C=-3来自B，D=-2来自C
A=-1来自C，B=-1来自D，C=-4来自B，D=-3来自C。。。
这里有一个证明，在负循环的情况下，距离将继续无限期地变化：
假设不是这样。然后是一个稳定的距离分配：任何可能的距离更新都不会减少它。这意味着，检查边的顺序可能会减少距离，这是不相关的，因为在这种情况下，检查每条边时，距离保持不变。
在负循环中选择一个点，考虑从该点开始的路径，直到它绕过并再次到达自己。由于检查此路径中的第一条边会使所有内容保持不变，因此该边远端的距离减去该边近端的距离必须不超过沿该边的距离。同样，沿着路径的两步距离减去路径开始时的距离必须不超过沿着两个相关边缘的距离之和，否则我们将把距离更新到两个点中的更远的一个。继续，我们计算出（圆形）路径末端的距离必须不超过（圆形路径）的起点加上沿着该路径的边的总和，否则会更新一些东西。但是路径的开始和结束是相同的点，因为它是圆形的，沿着边缘的距离之和是负的，因为它是负的循环，所以我们达到了一个矛盾，事实上，一旦我们检查了沿着圆形路径的所有边缘。
-
我需要为一组有向无环图找到从节点 0 开始的最长路径。我正在使用维基百科中的最长路径问题算法。我已经让算法适用于大多数图形，但对于其他图形，它没有给出正确的结果。算法为： 图形实现使用邻接列表来存储图形。如果我传递一个图，例如： 我得到的答案5，这是正确的。但是，如果我通过图表： 然后我得到2，而正确答案应该是3。 我使用的TopSort2算法是： DFS 算法包括：
-
设G=(V,E）是无向图。如果G的每个圈在F中至少有一条边，则称边集F E为反馈边集。 a）最小尺寸反馈边集：由于图是无权的，我们可以使用DFS。我们像往常一样从任意顶点开始DFS。当我们遇到一个后边时，我们将它插入反馈边集。当DFS完成时，该集将是答案。 b）最小权重反馈边集：由于图是加权的，我们可以使用Kruskal。但是Kruskal通常从最小权重的边开始。如果我们可以否定所有的边权重，然后
-
我想在无向图中找到一个强连通分量，即如果我从一个节点开始，那么我将回到节点，并且每个边都被精确地访问一次。 对于有向图，可以用Tarjan算法求强连通分量，但是对于无向图，该怎么办。
-
我需要找到一个算法来找到有向图中的所有根，在O（n m）。 我有一个寻找单个根的算法： 在v中的某些v上运行DFS（v）。如果结果是一个生成树，则v是根。否则，结果就是树木成林。然后： 在最后一棵树的根上运行DFS（u）。如果结果是一棵生成树，那么u是根。否则，图中没有根 现在，如果我想找到所有的根，最好的方法是每次在最后一棵树的不同顶点上运行上述算法O（n）次吗？假设我找到了一个根，如果另一个根
-
设想一个有向无环图如下所示，其中： “a”是根（总是正好有一个根） 每个节点都知道其父节点 节点名称是任意的-不能从中推断出任何内容 我们从另一个来源了解到，节点是按照A到G的顺序添加到树中的（例如，它们是在版本控制系统中提交的） 我可以使用什么算法来确定两个任意节点的最低共同祖先(LCA)，例如： null 注： 从根到给定节点不一定只有一条路径（例如“g”有两条路径），所以不能简单地遍历从根到