Questo è un progetto, scritto in JavaScript, che abbiamo sviluppato all’Università per la materia Algoritmi e Complessità…. tra l’altro mi ha fruttato un bel 30 e lode 😀

Si tratta di un simulatore di algoritmi per trovare l’albero di copertura minimo di un grafo connesso con archi non orientati.

Minimum Spanning Tree Algorithm Demo

Un albero di copertura di un grafo, anche noto con il termine inglese spanning tree (ST), è un albero che contiene tutti i vertici del grafo, ma degli archi ne contiene soltanto un sottoinsieme, cioè solo quelli necessari per connettere tra loro tutti i vertici con uno e un solo cammino.

Dato un grafo G, un albero T si dice albero di copertura minimo, o minimum spanning tree (MST), se e solo se qualsiasi altro albero ricoprente T” di G vale che la somma dei pesi degli archi di T è minore o uguale alla somma degli archi di T”.

Il simulatore implementa gli algoritmi di Kruskal e Prim per trovare il Minimum Spanning Tree del grafo.

Il progetto è orientato alla didattica, quindi oltre alla possibilità di lanciare gli algoritmi in modalità standard, c’è anche la possibilità di eseguirli “step by step“, cioè mostrando ogni singolo passo dell’algoritmo. Con questa modalità verranno inoltre catturate delle istantanee di ogni passo dell’algoritmo, ed è possibile esportare tutte le istantanee in un unico file di formato pdf.

L’applicazione mette a disposizione una serie di grafi di default su cui lanciare gli algoritmi, ma c’è anche la possibilità di aggiungere archi e nodi a tali grafi o di costruire un nuovo grafo personalizzato.

Tutti i grafi personalizzati che si realizzano possono essere esportati e salvati su file in locale, per poi essere reimportati all’interno dell’applicazione.

 

Link: shinworld.altervista.org/mst-demo

Codice Sorgente: github.com/ShinDarth/mst-demo

 

Librerie utilizzate:

Autori: Francesco Borzì, Filippo Randazzo, Sebastiano Siragusa.

About Shin

Programmatore per passione. Mi piace condividere qualsiasi idea o informazione utile, per questo motivo ho realizzato il blog.