Autor całego projektu: Paweł Jaroszewski gr 12.
Znajdowanie najmniejszego drzewa rozpinającego grafu metodą Kruskala
Opis i realizacja:
1. Posortować krawędzie w kolejności nie malejącej
-w tablicy "kol" typu Tdrzewo umieszczane są krawędzie
-krawędzie są sortowane
2. Do pustej tablicy drzewo typu Tdrzewo będą kopiowane elementy z tablicy kol które spełniają warunki algorytmu Kruskala:
-krawędź nie tworzy cyklu
-krawędź łączy wierzchołki, z których conajmniej jeden nie należy do drzewa
2. Po kolei z posortowanych krawędzi wybieramy krawędzie i sprawdzamy czy można krawędź dodać do drzewa:
- sprawdzenie czy któryś z wierzchołków już należy do drzewa odbywa się za pomoca funkcji nalezy:
bool nalezy(Tdrzewo drzewo[], int l, int x){
bool z=false;
for(int i=0;i<l;i++){
if ((x==drzewo[i].p)||(x==drzewo[i].k)){
z=true;
i=l;}
}
return z;
}
- jeżeli którys z wierzchołków nie należy do drzewa to dodajemy krawędź do drzewa
- jeżeli oba wierzchołki juz należą do drzewa to funkcja cykl sprawdza czy dana krawędź nie tworzy cyklu i jeżeli nie tworzy cyklu to dodajemy krawędź do drzewa:
Funkcja cykl jest rekurencyjna i sprawdza czy dane wierzchołki nie maja połączenia w drzewie.
bool cykl(Tdrzewo drzewo[], int l, int x, int y,int p){
bool c=false;
int i=0;
do{
if((drzewo[i].p==x)&&(drzewo[i].k!=p)){
if (drzewo[i].k==y){
c=true;
}
else
{
if(cykl(drzewo, l,drzewo[i].k,y,drzewo[i].p)){
c=true;}
}
}
else{
if((drzewo[i].k==x)&&(drzewo[i].p!=p)){
if (drzewo[i].p==y){
c=true;
}
else
{
if(cykl(drzewo, l,drzewo[i].p,y,drzewo[i].k)){
c=true;
}
}
}
}
i++;
}
while((i<l)&&(c!=true));
return c;
}
3. Po sprawdzeniu wszystkich elementów z tablicy kol otrzymujemy tablicę drzewo, w której znajdują sie tylko krawędzie tworzące drzewo.
4. Na koniec pozostaje sprawdzić czy wszystkie elementy należą do liczbie wszystkich wierzchołków pomniejszonej o 1.