- using System;
- using System.Collections.Generic;
- using System.Linq;
- using System.Text;
- using System.Threading.Tasks;
- namespace Kruskal
- {
- class Program
- {
- class Edge
- {
- public int p1, p2, weight;
- }
- class Subset
- {
- public int Parent;
- public int Rank;
- }
- class Graph
- {
- public Edge[] Edges;
- public int EdgeCount;
- public int VerCount;
- public Graph CreateGraph(int verCount, int edgeCount)
- {
- Graph graf = new Graph();
- graf.VerCount = verCount;
- graf.EdgeCount = edgeCount;
- graf.Edges = new Edge[graf.EdgeCount];
- return graf;
- }
- private int Find(Subset[] subsets, int i)
- {
- if (subsets[i].Parent != i)
- {
- subsets[i].Parent = Find(subsets, subsets[i].Parent);
- }
- return subsets[i].Parent;
- }
- private 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;
- }
- }
- private void Print(Edge[] results, int e)
- {
- for (int i = 0; i < e; i++)
- {
- Console.WriteLine("{a} -- {b} == {c}", results[i].p1, results[i].p2, results[i].weight);
- }
- }
- public void Kruskal(Graph graf)
- {
- int verCount = graf.VerCount;
- Edge[] results = new Edge[verCount];
- int i = 0;
- int e = 0;
- Array.Sort(graf.Edges, delegate (Edge a, Edge b)
- {
- return a.weight.CompareTo(b.weight);
- });
- Subset[] subsets = new Subset[verCount];
- for (int v = 0; v < verCount; v++)
- {
- subsets[v].Parent = v;
- subsets[v].Rank = 0;
- }
- while (e < verCount - 1)
- {
- Edge nextEdge = graf.Edges[i++];
- int x = Find(subsets, nextEdge.p1);
- int y = Find(subsets, nextEdge.p2);
- if (x != y)
- {
- results[e++] = nextEdge;
- Union(subsets, x, y);
- }
- }
- Print(results, e);
- }
- }
- static void Main(string[] args)
- {
- Graph graph=new Graph();
- graph.CreateGraph(4, 5);
- // Edge 0-1
- graph.Edges[0].p1 = 0;
- graph.Edges[0].p2 = 1;
- graph.Edges[0].weight = 10;
- // Edge 0-2
- graph.Edges[1].p1 = 0;
- graph.Edges[1].p2 = 2;
- graph.Edges[1].weight = 6;
- // Edge 0-3
- graph.Edges[2].p1 = 0;
- graph.Edges[2].p2 = 3;
- graph.Edges[2].weight = 5;
- // Edge 1-3
- graph.Edges[3].p1 = 1;
- graph.Edges[3].p2 = 3;
- graph.Edges[3].weight = 15;
- // Edge 2-3
- graph.Edges[4].p1 = 2;
- graph.Edges[4].p2 = 3;
- graph.Edges[4].weight = 4;
- graph.Kruskal(graph);
- }
- }
- }