好的,这是我在图中寻找切割的算法(这里我不是在说最小切割)
假设我们得到了一个非有向图的邻接列表。
我的问题是,这个算法正确吗?
同意你一定要去除自循环。我想补充的另一点是,在你随机选择第一个顶点后,你不必随机选择另一个节点,直到你有一个节点连接到第一个节点,你可以简单地从连接到第一个顶点的节点中选择,因为你知道第一个选择的节点连接到多少个节点。所以在更小的范围内进行第二次随机选择。这只是有效地随机选择一条边(由两个节点/顶点决定)。我有一些实现krager算法的c#代码,你可以随便玩玩。这不是最有效的代码(尤其是可以使用更有效的数据结构),因为我在一个200节点的图上测试了它,对于10000次迭代,它需要大约30秒来运行。
using System;
using System.Collections.Generic;
using System.Linq;
namespace MinCut
{
internal struct Graph
{
public int N { get; private set; }
public readonly List<int> Connections;
public Graph(int n) : this()
{
N = n;
Connections = new List<int>();
}
public override bool Equals(object obj)
{
return Equals((Graph)obj);
}
public override int GetHashCode()
{
return base.GetHashCode();
}
private bool Equals(Graph g)
{
return N == g.N;
}
}
internal sealed class GraphContraction
{
public static void Run(IList<Graph> graphs, int i)
{
var liveGraphs = graphs.Count;
if (i >= liveGraphs)
{
throw new Exception("Wrong random index generation; index cannot be larger than the number of nodes");
}
var leftV = graphs[i];
var r = new Random();
var index = r.Next(0, leftV.Connections.Count);
var rightV = graphs.Where(x=>x.N == leftV.Connections[index]).Single();
foreach (var v in graphs.Where(x => !x.Equals(leftV) && x.Connections.Contains(leftV.N)))
{
v.Connections.RemoveAll(x => x == leftV.N);
}
foreach (var c in leftV.Connections)
{
if (c != rightV.N)
{
rightV.Connections.Add(c);
int c1 = c;
graphs.Where(x=> x.N == c1).First().Connections.Add(rightV.N);
}
}
graphs.Remove(leftV);
}
}
}
我只会改变你的随机化。
选择第一个顶点后,从邻接列表中选择另一个顶点。现在,您确定两个顶点之间有边。下一步是从邻接列表中查找顶点。
这是对Krager的无向图的Min-Cut算法的一个很好的解释。
我想你可能错过了一个细节。或者也许我只是误读了你的描述。
< b >您想要移除所有自循环。
例如,在您删除一个顶点并运行您的算法后,顶点A现在可能有一条从顶点A到顶点A的边,这称为自循环。并且它们经常在收缩两个顶点的过程中产生。作为第一步,您可以简单地检查整个图中的自循环,尽管还有一些更复杂的方法。
这有意义吗?
我们已经看到,树的生成和切割是密切相关的。这里有另一个联系。让我们移除Kruskal算法添加到生成树中的最后一条边;这将树分解为两个组件,从而在图中定义一个截(S,S)。我们对这个伤口能说什么呢?假设我们正在处理的图是未加权的,并且它的边是均匀随机排列的,以便Kruskal的算法处理它们。这里有一个值得注意的事实:在概率至少1/n^2的情况下,(S,S)是图中的最小割,其中割的大小(S,S)是S和
问题内容: 因此,我正在创建一个免费的手绘图JPanel,它会响应鼠标的移动并 绘制线条。我得到了它的大部分工作,除了一个错误,它会 在线之间随机画一条直线。该随机直线不是 故意的,在缓冲图像上绘制的内容严格来说应该是 用户绘制的内容。这些随机绘制的线不是由用户完成的, 这令人困惑。以下是我的代码,任何人都可以看看吗?所包含的图像 使您可以直观地看到正在执行的操作。 问题答案: 您可能希望嵌套列表
但是,如果要单击RecycerView中的随机项怎么办?
我需要在MATLAB中实现一个基于连通分量算法原理的图像分割函数,但需要做一些修改。这是为了非常简单的2D图像,有一个背景颜色和一些不同颜色的对象。 其思想是,将图像作为一个矩阵,我提供了一个选择背景颜色的工具(它将对每个图像变化)。然后,当图像的背景颜色的值被选中时,我要对图像中的所有对象进行分割,结果应该是一个带标签的矩阵,图像大小相同,背景为0,每个对象有不同的数字。 这是我的意思的一个生动
(这正是网站上的内容) 结果是
事情是这样的,我一直在思考如何得到一个运算符,我可以使用,因为我也在使用一个非标准的CRC计算。最初的CRC计算是基于查找表的CRC32 0xEDB88320多项式,但是计算本身被破坏了,所以不是像0x00000000、0x77073096、0xEE0E612C、0x990951BA、0x076DC419、0x706AF48F、0xE963A535、...它现在看起来像这个0x00000000,0