克鲁斯克尔算法最小生成树

2020/01/15 31

算法

Kruskal算法是一种用来查找最小生成树的算法,由Joseph Kruskal在1956年发表。用来解决同样问题的还有Prim算法和Boruvka算法等。三种算法都是贪心算法的应用。和Boruvka算法不同的地方是,Kruskal算法在图中存在相同权值的边时也有效。

最小生成树

class Program
{
    static void Main(string[] args)
    {
        Graph graph = new Graph
        {
            VerticesCount = 7,
            Edges = new Edge[11]
        };

        graph.Edges[0].SourceChar = 'A';
        graph.Edges[0].DestinationChar = 'B';
        graph.Edges[0].Weight = 7;

        graph.Edges[1].SourceChar = 'A';
        graph.Edges[1].DestinationChar = 'D';
        graph.Edges[1].Weight = 5;

        graph.Edges[2].SourceChar = 'B';
        graph.Edges[2].DestinationChar = 'C';
        graph.Edges[2].Weight = 8;

        graph.Edges[3].SourceChar = 'B';
        graph.Edges[3].DestinationChar = 'D';
        graph.Edges[3].Weight = 9;

        graph.Edges[4].SourceChar = 'B';
        graph.Edges[4].DestinationChar = 'E';
        graph.Edges[4].Weight = 7;

        graph.Edges[5].SourceChar = 'C';
        graph.Edges[5].DestinationChar = 'E';
        graph.Edges[5].Weight = 5;

        graph.Edges[6].SourceChar = 'D';
        graph.Edges[6].DestinationChar = 'E';
        graph.Edges[6].Weight = 15;

        graph.Edges[7].SourceChar = 'D';
        graph.Edges[7].DestinationChar = 'F';
        graph.Edges[7].Weight = 6;

        graph.Edges[8].SourceChar = 'E';
        graph.Edges[8].DestinationChar = 'F';
        graph.Edges[8].Weight = 8;

        graph.Edges[9].SourceChar = 'E';
        graph.Edges[9].DestinationChar = 'G';
        graph.Edges[9].Weight = 9;

        graph.Edges[10].SourceChar = 'F';
        graph.Edges[10].DestinationChar = 'G';
        graph.Edges[10].Weight = 11;

        Kruskal(graph);
    }

    static int Find(Subset[] subsets, int i)
    {
        if (subsets[i].Parent != i)
        {
            subsets[i].Parent = Find(subsets, subsets[i].Parent);
        }
        return subsets[i].Parent;
    }

    static void Union(Subset[] subsets, int x, int y)
    {
        int xroot = Find(subsets, x);
        int yroot = Find(subsets, y);
        if (subsets[xroot].Rank < subsets[yroot].Rank)
            subsets[xroot].Parent = yroot;
        else if (subsets[xroot].Rank > subsets[yroot].Rank)
            subsets[yroot].Parent = xroot;
        else
        {
            subsets[yroot].Parent = xroot;
            ++subsets[xroot].Rank;
        }
    }

    static void Print(Edge[] result, int e)
    {
        int sum = 0;
        Console.WriteLine("Edge\tWeight");
        for (int i = 0; i < e; i++)
        {
            sum += result[i].Weight;
            Console.WriteLine($"{result[i].SourceChar} - {result[i].DestinationChar} \t {result[i].Weight}");
        }
        Console.WriteLine("Total Weight: " + sum);
    }

    static void Kruskal(Graph graph)
    {
        int verticesCount = graph.VerticesCount;
        Edge[] result = new Edge[verticesCount];
        int i = 0;
        int e = 0;

        Array.Sort(graph.Edges, (a, b) => a.Weight.CompareTo(b.Weight));

        Subset[] subsets = new Subset[verticesCount];

        for (int v = 0; v < verticesCount; v++)
        {
            subsets[v].Parent = v;
            // subsets[v].Rank = 0;
        }

        while (e < verticesCount - 1)
        {
            Edge nextEdge = graph.Edges[i++];
            int x = Find(subsets, nextEdge.Source);
            int y = Find(subsets, nextEdge.Destination);

            if (x != y)
            {
                result[e++] = nextEdge;
                Union(subsets, x, y);
            }
        }

        Print(result, e);
    }
}

struct Edge
{
    char _sourceChar;
    public char SourceChar
    {
        get => _sourceChar;
        set
        {
            _sourceChar = value;
            Source = SourceChar - 'A';
        }
    }

    char _destinationChar;
    public char DestinationChar
    {
        get => _destinationChar;
        set
        {
            _destinationChar = value;
            Destination = DestinationChar - 'A';
        }
    }

    public int Source { get; private set; }
    public int Destination { get; private set; }
    public int Weight { get; set; }
}

struct Graph
{
    public int VerticesCount { get; set; }
    public int EdgesCount => Edges == null ? 0 : Edges.Length;
    public Edge[] Edges { get; set; }
}

struct Subset
{
    public int Parent { get; set; }
    public int Rank { get; set; }
}

Output

Edge    Weight
A - D    5
C - E    5
D - F    6
A - B    7
B - E    7
E - G    9
Total Weight: 39
评论