using System;

using System.Collections;

​

class AdjencyMatrix {

    public int n;

    public int[, ] a;

}

​

class EDGE {

    public int v;

    public int w;

    public int weight;

}

​

class EDGEComparer : IComparer

{

    public int Compare(object x, object y)

    {

        if (((EDGE)x).weight > ((EDGE)y).weight) return 1;

        if (((EDGE)x).weight < ((EDGE)y).weight) return -1;

        return 0;

    }

}

​

class Subset {

    public int parent;

    public int rank;

}

​

public class Program

{

    public static void Main()

    {

        AdjencyMatrix g = new AdjencyMatrix();

        g.a = new int[,] {

            {0, 5, 3, 0, 0, 0, 0},

{5, 0, 4, 6, 2, 0, 0},

{3, 4, 0, 5, 0, 6, 0},

{0, 6, 5, 0, 6, 6, 0},

{0, 2, 0, 6, 0, 3, 5},

{0, 0, 6, 6, 3, 0, 4},

{0, 0, 0, 0, 5, 4, 0},

        };

        g.n = 7;

        kruskal(g);

    }

    static void PrintListEdges(EDGE []lstEdges) {

        for (int i = 0; i < lstEdges.Length; i++) {

            Console.WriteLine(String.Format("{0}-{1}: {2}", lstEdges[i].v, lstEdges[i].w, lstEdges[i].weight));

        }

    }

    static EDGE[] SortListEdge(AdjencyMatrix g) {

        EDGE []lstEdges = InitListEdge(g);

        EDGEComparer eC = new EDGEComparer();

        Array.Sort(lstEdges, eC);

        return lstEdges;

    }

    static EDGE[] InitListEdge(AdjencyMatrix g) {

        EDGE []lstEdges = new EDGE[g.n * (g.n - 1)];

        int nEdgesCount = 0;

        for (int i = 0; i < g.n; i++) {

            for (int j = i; j < g.n; j++) {

                if (g.a[i, j] !=0) {

                    EDGE edge = new EDGE();

                    edge.v = i;

                    edge.w = j;

                    edge.weight = g.a[i, j];

                    lstEdges[nEdgesCount] = edge;

                    nEdgesCount++;

                }

            }

        }

        EDGE []result = new EDGE[nEdgesCount];

        for (int i = 0; i < nEdgesCount; i++) {

            result[i] = lstEdges[i];

        }

        return result;

    }

    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 bool IsCircle(Subset []subsets, EDGE currentEdge) {

        int x = Find(subsets, currentEdge.v);

        int y = Find(subsets, currentEdge.w);

        if (x == y) {

            return true;

        }

​

        Union(subsets, x, y);

        return false;

    }

    static void kruskal(AdjencyMatrix g) {

        EDGE []T = new EDGE[g.n - 1];

        int nT = 0;

        Subset[] subsets = new Subset[g.n];

        EDGE []lstEdges = SortListEdge(g);

        int nEdgesCount = lstEdges.Length;

​

        for (int i = 0; i < g.n; i++) {

            Subset subset = new Subset();

            subset.parent = i;

            subset.rank = 0;

            subsets[i] = subset;

        }

        int eMinIndex = 0;

        while (nT < g.n - 1) {

            if (eMinIndex < nEdgesCount) {

                if (IsCircle(subsets, lstEdges[eMinIndex]) == false) {

                    T[nT++] = lstEdges[eMinIndex];

                }

                eMinIndex++;

            }

        }

        Console.WriteLine("Tap canh cua cay khung:");

        int totalWeight = 0;

        for (int i=0; i < T.Length; i++) {

            totalWeight += T[i].weight;

            Console.WriteLine(String.Format("{0}-{1}: {2}", T[i].v, T[i].w, T[i].weight));

        }

        Console.WriteLine(String.Format("Tong so cua cay khung nho nhat: {0}", totalWeight));

    }

    static void prim(AdjencyMatrix g, int source) {

        EDGE []T = new EDGE[g.n - 1];

        int nT = 0;

        bool []marked = new bool[g.n];

        for (int i = 0; i < g.n; i++) {

            marked[i] = false;

        }

        marked[source] = true;

        while (nT < g.n - 1) {

            EDGE edgeMin = new EDGE();

            int nMinWeight = -1;

            for (int w = 0; w < g.n; w++) {

                if (marked[w] == false) {

                    for (int v = 0; v < g.n; v++) {

                        if (marked[v] == true && g.a[v, w] !=0) {

                            if (nMinWeight == -1 || g.a[v, w] < nMinWeight) {

                                edgeMin.v = v;

                                edgeMin.w = w;

                                edgeMin.weight = g.a[v, w];

                                nMinWeight = g.a[v, w];

                            }

                        }

                    }

                }

            }

            T[nT++] = edgeMin;

            marked[edgeMin.w] = true;

        }

        Console.WriteLine("Tap canh cua cay khung:");

        int totalWeight = 0;

        for (int i=0; i < T.Length; i++) {

            totalWeight += T[i].weight;

            Console.WriteLine(String.Format("{0}-{1}: {2}", T[i].v, T[i].w, T[i].weight));

        }

        Console.WriteLine(String.Format("Tong so cua cay khung nho nhat: {0}", totalWeight));

    }

}

​

​