Karger Min Cut算法运行时间 [英] Karger Min cut algorithm running time

问题描述

我想实现Karger的最小切算法.

I want to implement the min cut algorithm form Karger.

维基百科声称可以编写运行时间为 O(| V | ^ 2)的实现.我看不到有任何方法可以做到这一点.该算法进行 | V | 迭代，并且在每次迭代中都会收缩一条边.要缩小边缘，您需要:

Wikipedia claims it is possible to write an implementation with a running time of O(|V|^2). I don't see any way to do this. The algorithm makes |V| iterations and in each iteration it contracts an edge. To contract an edge you need to:

1. 创建一个新顶点
2. 删除两个旧顶点，然后
3. 删除旧顶点之间的边缘.

在 O(| V |)中，图没有数据结构可以添加顶点，删除顶点和删除边.Wikipedia建议使用邻接表，但运行时间为 O(| V | + | E |)，如果您具有 | E | = | V | ^ 2 .可以在 O(| V | ^ 2)中实施Karger的最小切割吗?

There is no data structure for graphs which can add vertexes, delete vertexes and delete edges in O(|V|). Wikipedia recommends an adjacency lists but it has an running time of O(|V|+|E|) which is bad if you have |E|=|V|^2. Is it possible to implement the Karger's min cut in O(|V|^2)?

推荐答案

Wikipedia省略了以下详细信息:您需要具有加权边的邻接表，以便可以通过添加平行边的权重来合并它们.这样，(未加权)度数受| V |限制.在每个步骤中.

Wikipedia left out the detail that you need an adjacency list with weighted edges, so that you can merge parallel edges by adding their weights. In this way, the (unweighted) degree is bounded by |V| at each step.

这篇关于Karger Min Cut算法运行时间的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！