Facebook
From Sole Marmoset, 9 Months ago, written in Plain Text.
Embed
Download Paste or View Raw
Hits: 87
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4. using System.Text;
  5. using System.Threading.Tasks;
  6.  
  7. namespace Kruskal
  8. {
  9.     class Program
  10.     {
  11.         class Edge
  12.         {
  13.             public int p1, p2, weight;
  14.         }
  15.         class Subset
  16.         {
  17.             public int Parent;
  18.             public int Rank;
  19.         }
  20.         class Graph
  21.         {
  22.             public Edge[] Edges;
  23.             public int EdgeCount;
  24.             public int VerCount;
  25.  
  26.             public Graph CreateGraph(int verCount, int edgeCount)
  27.             {
  28.                 Graph graf = new Graph();
  29.                 graf.VerCount = verCount;
  30.                 graf.EdgeCount = edgeCount;
  31.                 graf.Edges = new Edge[graf.EdgeCount];
  32.  
  33.                 return graf;
  34.             }
  35.  
  36.             private int Find(Subset[] subsets, int i)
  37.             {
  38.                 if (subsets[i].Parent != i)
  39.                 {
  40.                     subsets[i].Parent = Find(subsets, subsets[i].Parent);
  41.                 }
  42.                 return subsets[i].Parent;
  43.             }
  44.  
  45.             private void Union(Subset[] subsets, int x, int y)
  46.             {
  47.                 int xroot = Find(subsets, x);
  48.                 int yroot = Find(subsets, y);
  49.  
  50.                 if (subsets[xroot].Rank < subsets[yroot].Rank)
  51.                     subsets[xroot].Parent = yroot;
  52.                 else if (subsets[xroot].Rank > subsets[yroot].Rank)
  53.                     subsets[yroot].Parent = xroot;
  54.                 else
  55.                 {
  56.                     subsets[yroot].Parent = xroot;
  57.                     ++subsets[xroot].Rank;
  58.                 }
  59.             }
  60.             private void Print(Edge[] results, int e)
  61.             {
  62.                 for (int i = 0; i < e; i++)
  63.                 {
  64.                     Console.WriteLine("{a} -- {b} == {c}", results[i].p1, results[i].p2, results[i].weight);
  65.                 }
  66.             }
  67.             public void Kruskal(Graph graf)
  68.             {
  69.                 int verCount = graf.VerCount;
  70.                 Edge[] results = new Edge[verCount];
  71.                 int i = 0;
  72.                 int e = 0;
  73.  
  74.                 Array.Sort(graf.Edges, delegate (Edge a, Edge b)
  75.                  {
  76.                      return a.weight.CompareTo(b.weight);
  77.                  });
  78.                 Subset[] subsets = new Subset[verCount];
  79.  
  80.                 for (int v = 0; v < verCount; v++)
  81.                 {
  82.                     subsets[v].Parent = v;
  83.                     subsets[v].Rank = 0;
  84.                 }
  85.                 while (e < verCount - 1)
  86.                 {
  87.                     Edge nextEdge = graf.Edges[i++];
  88.                     int x = Find(subsets, nextEdge.p1);
  89.                     int y = Find(subsets, nextEdge.p2);
  90.  
  91.                     if (x != y)
  92.                     {
  93.                         results[e++] = nextEdge;
  94.                         Union(subsets, x, y);
  95.                     }
  96.                 }
  97.                 Print(results, e);
  98.             }
  99.         }
  100.         static void Main(string[] args)
  101.         {
  102.             Graph graph=new Graph();
  103.             graph.CreateGraph(4, 5);
  104.             // Edge 0-1
  105.             graph.Edges[0].p1 = 0;
  106.             graph.Edges[0].p2 = 1;
  107.             graph.Edges[0].weight = 10;
  108.  
  109.             // Edge 0-2
  110.             graph.Edges[1].p1 = 0;
  111.             graph.Edges[1].p2 = 2;
  112.             graph.Edges[1].weight = 6;
  113.  
  114.             // Edge 0-3
  115.             graph.Edges[2].p1 = 0;
  116.             graph.Edges[2].p2 = 3;
  117.             graph.Edges[2].weight = 5;
  118.  
  119.             // Edge 1-3
  120.             graph.Edges[3].p1 = 1;
  121.             graph.Edges[3].p2 = 3;
  122.             graph.Edges[3].weight = 15;
  123.  
  124.             // Edge 2-3
  125.             graph.Edges[4].p1 = 2;
  126.             graph.Edges[4].p2 = 3;
  127.             graph.Edges[4].weight = 4;
  128.  
  129.             graph.Kruskal(graph);
  130.         }
  131.     }
  132. }
  133.