4

好的，这是我在图中找到切点的算法（我不是在这里谈论最小切点）

假设我们得到了一个无向图的邻接表。

  1. 选择图形上的任何顶点（用枢轴表示）
  2. 选择图形上的任何其他顶点（随机）。（用 x 表示）
  3. 如果两个顶点之间有一条边，则从图中删除该边。并将 x 连接到的所有顶点转储到枢轴上。（如果没有，则返回第 2 步。
  4. 如果任何其他顶点连接到 x，则更改邻接列表，以便现在 x 被枢轴替换。即他们连接到Pivot。
  5. 如果顶点数大于 2（返回步骤 2）
  6. 如果等于 2。只需计算 2 个点中的任何一个的邻接列表中存在的顶点数。这将给削减

我的问题是，这个算法正确吗？

4

3 回答 3

1

我只会改变你的随机化。

选择第一个顶点后，从他的邻接列表中选择另一个。现在您确定两个顶点之间有边。下一步是从邻接列表中找到顶点。

于 2013-07-28T01:02:57.073 回答
1

这是对 Krager 的无向图最小割算法的一个很好的解释。

我想你可能错过了一个细节。或者我只是误读了你的描述。

您想删除所有自循环。

例如，在您删除一个顶点并运行您的算法后，顶点 A 现在可能有一条从顶点 A 到顶点 A 的边。这称为自循环。它们在收缩两个顶点的过程中经常产生。作为第一步，您可以简单地检查整个图的自循环，尽管有一些更复杂的方法。

那有意义吗？

于 2012-04-09T06:03:02.030 回答
-1

同意您绝对应该删除自循环。还有一点我想补充的是，在你随机选择第一个顶点之后，你不必随机选择另一个节点，直到你有一个连接到第一个节点的节点，你可以简单地从连接到的节点中选择第一个顶点，因为您知道第一个选择的节点连接到多少个节点。所以在较小的范围内进行第二次随机选择。这只是有效地随机选择一条边（由两个节点/顶点确定）。我有一些实现 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);
    }
}

}

于 2014-11-07T17:15:10.527 回答