крускал

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace MibOstTreeWithDSU
{
struct Edge
{
public readonly int v1, v2, weight;
public Edge(int v1, int v2, int weight)
{
this.v1 = v1;
this.v2 = v2;
this.weight = weight;
}
public override string ToString()
{
return String.Format("[({0},{1}), w = {2}]", v1, v2, weight);
}
}
class DSU
{
private int[] p;
private int[] cnt;
public DSU(int size)
{
p = new int[size];
cnt = new int[size];
for (int i = 0; i < size; ++i)
{
p[i] = i;
cnt[i] = 1;
}
}
public int getID(int vertex)
{
if (p[vertex] == vertex) return vertex;
return p[vertex] = getID(p[vertex]);
}
public bool unite(int a, int b)
{
a = getID(a);
b = getID(b);
if (a == b) return false;
if (cnt[a] > cnt[b])
{
cnt[a] += cnt[b];
p[b] = a;
}
else
{
cnt[b] += cnt[a];
p[a] = b;
}
return true;
}
}
class Program
{
public static List<int> Kraskall(int n, Edge[] G, out int SumW)
{
int m = G.Length;
int[] ord = new int[m];
for (int i = 0; i < m; ++i)
ord[i] = i;
Array.Sort(ord, (int x, int y) =>
{
return G[x].weight.CompareTo(G[y].weight);
});
DSU dsu = new DSU(n);
List<int> ans = new List<int>(n - 1);
SumW = 0;
foreach (int id in ord)
{
if (dsu.unite(G[id].v1, G[id].v2))
{
ans.Add(id);
SumW += G[id].weight;
}
}
return ans;
}
static void Main(string[] args)
{
int n = 5;
Random rand = new Random(15);
Edge[] G = new Edge[n * (n - 1) / 2];
for (int i = 0, pos = 0; i < n; ++i)
for (int j = 0; j < i; ++j, ++pos)
{
G[pos] = new Edge(i, j, rand.Next(100));
}
Console.WriteLine("============Graph============");
foreach (Edge e in G)
Console.WriteLine(e);
Console.WriteLine("=============================");
int w;
List<int> ostTr = Kraskall(n, G, out w);
Console.WriteLine("Min ost. tree weight = {0}", w);
foreach(int id in ostTr)
{
Console.Write(id + " ");
}
}
}
}