Newsgroup: it.comp.java
Titolo: [source] Kruskal

Questa classe risolve l'algoritmo di Kruskal. Fa uso di un package gia'
pubblicato su questo NG qualche tempo fa. Chi non riuscisse a recuperarlo mi
scriva privatamente.
------------------------------------------------Kruskal
package crivellaro.algorithms;
import java.util.Vector;
import java.util.Iterator;
import crivellaro.datatypes.*;
/**
 * Questa classe implementa l'algoritmo di Kruskal per grafi
 * pesati connessi. L'unico metodo di questa classe, <code>getMST</code>,
 * è <code>static</code>. Esso riceve in input un grafo e restituisce il
 * minimo albero ricoprente come <code>Vector</code> di archi.
 *
 */
public class Kruskal {
    /**
     * Restituisce il minimo albero che ricopre il grafo in input,
     * calcolato utilizzando l'algoritmo di Kruskal.
     *
     * @param   graph  Il grafo in esame.
     * @return  Il Vector contenente gli archi del minimo albero ricoprente.
     */
    public static Vector getMST(Graph graph) {
     Vector arcQueue = graph.getArcs();
     Vector nodeSet = graph.getNodes();
     // costruzione dell'insieme iniziale delle componenti connesse
     // (una per ciascun nodo).
     Vector clusterSet = new Vector();
     for (Iterator i = nodeSet.iterator(); i.hasNext();) {
         clusterSet.addElement(new Cluster((Node)i.next()));
        }
        int finalSizeMST = clusterSet.size() - 1;
     Vector mst = new Vector(0);
        Vector lArcQueue = (Vector)arcQueue.clone();
        arcIterator:
        for (Iterator i = lArcQueue.iterator(); i.hasNext();) {
      Arc arc = (Arc)i.next();
            for (Iterator j = clusterSet.iterator(); j.hasNext();) {
             Cluster cluster = (Cluster)(j.next());
            }
            int originId = arc.getOriginNode().getId();
            int destinationId = arc.getDestinationNode().getId();
            if (originId > destinationId) {
             int tmp = originId;
                originId = destinationId;
                destinationId = tmp;
            }
            // Questi flag tengono traccia del ritrovamento o meno
            // dei nodi di partenza e arrivo.
            boolean originIdFound = false;
            boolean destinationIdFound = false;
            Cluster c1 = new Cluster();
            Cluster c2 = new Cluster();
            clusterSetIterator:
            for (Iterator j = clusterSet.iterator(); j.hasNext();) {
             Cluster cluster = (Cluster)(j.next());
                // verifico se il cluster in esame contiene uno o entrambi
                // i nodi estremi dell'arco in esame.
                boolean bothInCluster = false;
                boolean oneInCluster  = false;
                clusterIterator:
                for (Iterator k = cluster.iterator(); k.hasNext();) {
                    Node node = (Node)(k.next());
                    if (node.getId() == originId) {
                        originIdFound = true;
                        if (oneInCluster) {
                         bothInCluster = true;
                         c2 = cluster;
                            break clusterIterator;
                        }
                        else {
                         oneInCluster = true;
                         c1 = cluster;
                        }
                    }
                    else if (node.getId() == destinationId) {
                     destinationIdFound = true;
                        if (oneInCluster) {
                         bothInCluster = true;
                         c1 = cluster;
                            break clusterIterator;
                        }
                        else {
                         oneInCluster = true;
                            c2 = cluster;
                        }
                    }
                }
                if (bothInCluster) {
                    // inutile esaminare gli altri cluster,
                    // passo all'arco successivo.
                    break clusterSetIterator;
                }
                if ((originIdFound)&&(destinationIdFound)) {
                    // L'arco è attivabile.
                    mst.addElement(arc);
                    c1.merge(c2);
                    j.remove();
                    if (mst.size() < finalSizeMST)
                     break clusterSetIterator;
                    else
                     break arcIterator;
                }
            }
            i.remove();
        }
        return mst;
    }

pubblicato su questo NG qualche tempo fa. 
Sei un grande, non so a quanti potrà essere utile tale algoritmo,
per ora me lo salvo... chissà in futuro. Comunque, TU, sei un GRANDE!
Grazie, grazie... grazie 1000 8)