-
Notifications
You must be signed in to change notification settings - Fork 1
jdermont/2rok2sem
Folders and files
| Name | Name | Last commit message | Last commit date | |
|---|---|---|---|---|
Repository files navigation
algorytm kruskala znajdowania minimalnego drzewa rozpinajacego
zad.
dana jest struktura nieskierowanego grafu wazonego:
unsigned int n; // liczba wierzcholkow
struct vertex {
unsigned int label; // nazwa wierzcholka
unsigned int parent; // nazwa rodzica
unsigned int rank; // ranga wierzcholka
} *V; // tablica wierzcholkow rezerwowana dynamicznie
struct edge {
unsigned int u,v; // para etykiet wierzcholkow
float weight; // waga krawedzi
} *E; // tablica krawedzi rezerwowana dynamicznie
Uwaga: program powinien weryfikowac podana liste krawedzi (sprawdzac czy krawedzie nie powtarzaja sie - uwzgledniac
tez odwrotna kolejnosc podawania wierzcholkow).
Kruskal(G) {
struct edge *A;
1. niech A bedzie zbiorem pustym;
2. dla wszystkich wierzcholkow veV wykonaj Make-Set(v);
3. Posortuj zbior krawedzi w E niemalejaco wzgledem wag
4. dla wsyzstkich kolejnych krawedzi(u,v) w E wykonaj:
if (Find-Set(u) != Find-Set(v)) {
dopisz(u,v) do zbioru A;
union(u,v);
}
} // A - wynik dzialania algorytmu
Uwaga: nalezy zmodyfikowac funkcje z poprzednich zajec tak, zeby uwzglednialy dowolne etykietowanie wierzcholkow grafu
About
No description, website, or topics provided.
Resources
Stars
Watchers
Forks
Releases
No releases published
Packages 0
No packages published