Algorytm Kruskala, jest algorytmem służącym do wyznaczania minimalnego drzewa spinającego grafu nieskierowanego. Poniższa implementacja w C# pochodzi z mojego projektu zaliczeniowego z przedmiotu "Algorytmy i struktury danych".
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Grafy
{
class Program
{
static Graf g;
static bool jestGraf = false;
static void Main(string[] args)
{
string c = "";
RysujMenu();
while (c != "x")
{
RysujMenu();
c = Console.ReadLine();
switch (c)
{
case "a" :
DodajNowyGraf();
break;
case "c" :
CzyscGraf();
break;
case "k" :
DodajKrawedzDoGrafu();
break;
case "z" :
Zapisz();
break;
case "w" :
g = new Graf(1);
Czytaj();
jestGraf = true;
break;
case "u" :
UsunKrawedzGrafu();
break;
case "d" :
WyznaczDrzewo();
break;
}
}
}
private static void WyznaczDrzewo()
{
Console.WriteLine("Wyznaczam mnimalne drzewo spinające:");
//częśc wykonawcza
Las l = new Las(g.ileWierzcholkow);
foreach (Krawedz k in g.krawedzie)
{
l.SprawdzKrawedz(k);
}
if (l.drzewa.Count > 1)
{
Console.BackgroundColor = ConsoleColor.Red;
Console.ForegroundColor = ConsoleColor.DarkRed;
Console.WriteLine("Graf nie jest spójny!");
Console.BackgroundColor = ConsoleColor.Black;
Console.ForegroundColor = ConsoleColor.White;
}
else
{
Console.BackgroundColor = ConsoleColor.Blue;
Console.ForegroundColor = ConsoleColor.Yellow;
foreach (Krawedz k in l.drzewa[0].krawedzie)
{
Console.WriteLine("[{0,3},{1,3},{2,3}]", k.WierzcholekPoczatkowy.ToString(), k.WierzcholekKoncowy.ToString(), k.Waga.ToString());
}
Console.BackgroundColor = ConsoleColor.Black;
Console.ForegroundColor = ConsoleColor.White;
}
Console.WriteLine("Naciśnij ENTER aby przejśc do menu");
Console.ReadLine();
}
private static void Czytaj()
{
string na;
Console.WriteLine("Podaj nazwę pliku");
na = Console.ReadLine();
g.CzytajZPliku(na);
}
private static void Zapisz()
{
string na;
Console.WriteLine("Podaj nazwę pliku");
na = Console.ReadLine();
g.ZapiszDoPliku(na);
}
private static void UsunKrawedzGrafu()
{
string wp;
string wk;
Console.WriteLine("Podaj wierzchołek początkowy");
wp = Console.ReadLine();
Console.WriteLine("Podaj wierzchołek końcowy");
wk = Console.ReadLine();
g.UsunKrawedz(int.Parse(wp), int.Parse(wk));
}
private static void CzyscGraf()
{
g = null;
jestGraf = false;
}
private static void DodajNowyGraf()
{
string c;
Console.WriteLine("Podaj ilośc wierzchołków grafu:");
c = Console.ReadLine();
g = new Graf(int.Parse(c));
jestGraf = true;
}
public static void DodajKrawedzDoGrafu()
{
int pierwszy;
int drugi;
int waga;
string c;
Console.WriteLine("Podaj pierwszy wierzchołek");
c = Console.ReadLine();
pierwszy = int.Parse(c);
Console.WriteLine("Podaj drugi wierzchołek");
c = Console.ReadLine();
drugi = int.Parse(c);
Console.WriteLine("Podaj wage");
c = Console.ReadLine();
waga = int.Parse(c);
Krawedz kr = new Krawedz(pierwszy, drugi, waga);
g.DodajKrawedz(kr);
}
public static void RysujMenu()
{
Console.Clear();
Console.WriteLine("Program \"Grafy\" - Paweł Filipowski IMUZ 1.1 (2009)");
if (jestGraf)
{
Console.WriteLine("Utworzono graf o {0} wierzchołkach. W grafie jest {1} krawędzi.", g.ileWierzcholkow, g.krawedzie.Count.ToString());
PokazKrawedzie();
}
Console.WriteLine();
if (!jestGraf)
{
Console.WriteLine("[a] Nowy graf");
Console.WriteLine("[w] Wczytaj z pliku");
}
else
{
Console.WriteLine("[k] Dodaj krawędź");
Console.WriteLine("[u] Usuń krawędź");
Console.WriteLine("[z] Zapisz do pliku");
Console.WriteLine("[c] Czyśc graf");
Console.WriteLine("[d] Wyznacz minimalne drzewo spinające algorytmem Kruskala");
}
Console.WriteLine("[x] Wyjście");
}
private static void PokazKrawedzie()
{
foreach (Krawedz k in g.krawedzie)
{
Console.WriteLine("[{0,3},{1,3},{2,3}]", k.WierzcholekPoczatkowy.ToString(), k.WierzcholekKoncowy.ToString(), k.Waga.ToString());
}
}
}
}
Deklaracje klas
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Grafy
{
class Krawedz : IComparable
{
public int WierzcholekPoczatkowy;
public int WierzcholekKoncowy;
public int Waga;
public Krawedz(int wp, int wk, int w)
{
this.WierzcholekPoczatkowy = wp;
this.WierzcholekKoncowy = wk;
this.Waga = w;
}
int IComparable.CompareTo(Object obj)
{
if (obj is Krawedz) //sprawdzenie czy obiekt jest prawidłowego typu
{
Krawedz castObj = (Krawedz)obj; //konieczne rzutowanie typu
return this.Waga.CompareTo(castObj.Waga);
}
throw new ArgumentException("Obiekt nie jest Krawędzią");
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
namespace Grafy
{
class Graf
{
public int ileWierzcholkow;
public List krawedzie;
public Graf(int iw)
{
this.ileWierzcholkow = iw;
krawedzie = new List();
}
public void DodajKrawedz(Krawedz k)
{
krawedzie.Add(k);
krawedzie.Sort();
}
public void UsunKrawedz(Krawedz k)
{
krawedzie.Remove(k);
}
public bool UsunKrawedz(int wp, int wk)
{
bool jestKrawedz = false;
foreach (Krawedz k in krawedzie)
{
if (k.WierzcholekPoczatkowy == wp && k.WierzcholekKoncowy == wk)
{
jestKrawedz = true;
krawedzie.Remove(k);
break;
}
}
return jestKrawedz;
}
public void ZapiszDoPliku(string nazwa)
{
StreamWriter x = new StreamWriter(nazwa, false, Encoding.UTF8);
x.WriteLine(this.ileWierzcholkow);
x.WriteLine(this.krawedzie.Count());
foreach (Krawedz k in this.krawedzie)
{
x.Write(k.WierzcholekPoczatkowy);
x.Write(",");
x.Write(k.WierzcholekKoncowy);
x.Write(",");
x.WriteLine(k.Waga);
}
x.Dispose();
}
public void CzytajZPliku(string nazwa)
{
string line;
string wp;
string wk;
string w;
StreamReader x = new StreamReader(nazwa, Encoding.UTF8);
line = x.ReadLine(); //czytanie liczby wierzchołkow
this.ileWierzcholkow = int.Parse(line);
line = x.ReadLine(); //czytanie liczby krawędzi (w sumie nie do końca potrzebne)
line = x.ReadLine();
while(line != null)
{
wp = line.Substring(0, line.IndexOf(","));
line = line.Substring(line.IndexOf(",") + 1);
wk = line.Substring(0, line.IndexOf(","));
line = line.Substring(line.IndexOf(",") + 1);
w = line;
Console.WriteLine(wp + "/" + wk + "/" + w);
//Console.ReadLine();
Krawedz k = new Krawedz(int.Parse(wp), int.Parse(wk), int.Parse(w));
this.DodajKrawedz(k);
line = x.ReadLine();
}
x.Dispose();
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Grafy
{
class Drzewo
{
public List wierzcholki;
public List krawedzie;
public Drzewo(int nrwierzcholka)
{
this.wierzcholki = new List();
this.krawedzie = new List();
wierzcholki.Add(nrwierzcholka); //na początku drzewo składa się z jednego wierzcholka
}
public void DodajDrzewo(Drzewo d)
{
this.wierzcholki.AddRange(d.wierzcholki);
this.krawedzie.AddRange(d.krawedzie);
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Grafy
{
class Las
{
public List drzewa;
//tworzenie lasu pustych wierzcholkow
public Las(int iledrzew) {
this.drzewa = new List();
for(int i = 1; i <= iledrzew; i++) {
drzewa.Add(new Drzewo(i));
}
}
//zwraca drzewo w którym istnieje zadany wierzchołek
public Drzewo SzukajWierzcholka(int wierzcholek)
{
Drzewo wynik = null;
foreach (Drzewo d in drzewa)
{
if (d.wierzcholki.Contains(wierzcholek))
{
wynik = d;
break;
}
}
return wynik;
}
//łączy drzewa -> dołącza drugie do pierwszego
public void PolaczDrzewa(Drzewo d1, Drzewo d2)
{
foreach (int w in d2.wierzcholki)
{
d1.wierzcholki.Add(w);
}
foreach (Krawedz k in d2.krawedzie)
{
d1.krawedzie.Add(k);
}
drzewa.Remove(d2);
}
//dołącza krawędź do drzewa jeśli jest taka możliwośc
public void SprawdzKrawedz(Krawedz k)
{
Drzewo d1 = SzukajWierzcholka(k.WierzcholekPoczatkowy);
Drzewo d2 = SzukajWierzcholka(k.WierzcholekKoncowy);
if (!d1.Equals(d2))
{
d1.krawedzie.Add(k);
PolaczDrzewa(d1, d2);
}
}
}
}
