Minimal Spanning Tree^*

according to Prim's and Kruskal's algorithm

CLICK HERE AND DOWNLOAD FREE ENGLISH VERSION OF PROGRAM , WITH SOME EXPLANATIONS. PACKED IN SETUP FILE OF 366 Kb.

Prim's algorithm for finding a minimal cost spanning tree in a connected graph is very easy to follow. It begins by adding the lowest cost edge and its two endpoints to the solution set. It then loops adding the lowest cost edge that connects a vertex in the solution set to one outside it. It also adds the endpoint of this edge that is not already in the solution set. The algorithm terminates when all vertices are in the solution set. The edges and vertices in the solution set at this point constitute a minimal cost spanning tree of the input graph.

Kruskal's algorithm for finding a minimal spanning tree in a connected graph is a greedy algorithm; that is, given a choice, it always processes the edge with the least weight.This algorithm operates by considering edges in the graph in order of weight from the least weighted edge up to the most while keeping track of which nodes in the graph have been added to the spanning tree. If an edge being considered joins either two nodes not in the spanning tree, or joins a node in the spanning tree to one not in the spanning tree, the edge and its endpoints are added to the spanning tree. After considering one edge the algorithm continues to consider the next higher weighted edge. In the event that a graph contains equally weighted edges the order in which these edges are considered does not matter. The algorithm stops when all nodes have been added to the spanning tree.

^{*Program development tool: Borland Delphi 4}

^{Back to HomePage}

Metoda najkraceg stabla^*

prema Primovom i Kruskalovom algoritmu

KLIKNI OVDJE I DOWNLOADIRAJ BESPLATNU VERZIJU PROGRAMA NA BOSANSKOM JEZIKU KOJA UKLJUCUJE I SEMINARSKI RAD. INSTALACIJA JE ZAPAKOVANA U .EXE FAJL TEZINE 488 Kb. KLIKNI OVDJE DA POGLEDAS SEMINARSKI RAD(.HTML FAJL TEZAK 240 Kb).KLIKNI OVDJE I POGLEDAJ ANIMIRANU PREZENTACIJU RADA PROGRAMA PRIJE NEGO SE ODLUCITE NA DOWNLOAD SAMOG PROGRAMA (fajl je tezak 142 Kb i najbolje ga je pogledati u Full Screen modu,pritisnite F11 ako koristite Internet Explorer).

Primov algoritam je vrlo jednostavan za pracenje. Pocetna tacka se bira proizvoljno i ona odmah postaje dio grafa. Svaka sljedeca tacka se dodaje ako se ustanovi da je udaljenost između bilo koje tacke iz grafa i bilo koje slobodne tacke najmanja upravo za tu tacku i neku tacku koja je već u grafu.Postupak se iterativno nastavlja sve dok sve ne ostane ni jedna slobodna tacka , odnosno dok sve tacke ne budu ukljucene u graf. Jezikom pseudocoda :
1. Izaberi proizvoljan pocetni cvor,
2. Nadji njemu najblizi cvor i taj cvor postaje dio grafa,
3. Nadji grafu najblizi slobodni cvor,
4. Iterativno ponavljaj postupak pod tackom 3. dok svi cvorovi ne budu ukljuceni u graf.
Kruskalov algoritam za pronalazenje najkraceg stabla grafa je tkzv. sebicni (greedy) algoritam zbog toga sto on obradjuje uvijek najmanju dostupnu ivicu (granu) grafa. Grane kandidati za ulazak u graf jesu sve moguce kombinacije pocetnih tacaka s tim što se izbjegava dupliranje grana npr. grana a- b je jednaka grani b-a pa granu b-a ne treba ukljucivati u moguce kombinacije . Grafu se prikljucuje najmanja dostupna grana pazeci da se pri tome ne zatvori ciklus.Jezikom pseudocoda,
1. Sortirati sve grane-kandidate za ulazak u graf,
2. Prikljuci najmanju granu grafu ako se tim prikljucivanjem ne zatvara ciklus,
3. Iterativno ponavljaj postupak pod tackom 2. dok sve pocetne tacke ne postanu dio grafa.

^{* Razvojni alat : Borland Delphi 4      Nazad na HomePage}