Newsgroup: it.comp.java
Titolo: Algoritmo di Prim

Vorrei gentilmente sapere come risolvere il problema sull'algoritmo di
Prim in modo da ottenere il risultato atteso: ho pensato che potrebbero
esserci problemi con i metodi della classe Heap oppure ho sbagliato ad
implementare qualche istruzione in MSTPRim. Sarei grato se qualcuno mi
aiutasse a risolvere il problema. Ecco il codice java con tutte le
classi da utilizzare.
NB. ho implementato i metodi Enqueue,Dequeue,Heapify,Decreasekey e
MSTPrim; gli altri sono sicuramente corretti e non c'è bisogno di
testare la classe Graph.
Grazie.
/**********************************************************
	Terza Consegna
	Gruppo:
	Data di spedizione:
	Alberi di copertura minimi su grafi non orientati;
	algoritmo di Prim
**********************************************************/
import java.util.*;
//-------- Interfaccia delle code di priorita' -------------
interface PriorityQueue {
	boolean IsEmpty ();
	// true sse this e' la coda vuota
	void Enqueue (Object obj, int key);
	// aggiunge a this l'elemento obj di chiave (priorita') key
	Object Dequeue ();
	// elimina e ritorna il minimo
	Object Minimum ();
	// ritorna il minimo senza rimuoverlo dalla coda
	void DecreaseKey (Object obj, int newkey);
	//	pre: obj e' nella coda this, con chiave key, e newkey <= key
	//  post: obj e' in this con chiave newkey
}
//-------- Implementazione delle code di priorita' -----------
class Heap implements PriorityQueue
{
	public boolean IsEmpty ()
	// true sse this e' la coda vuota
	{
		return nextfree == 0;
	}
	public void Enqueue (Object obj, int key)
	// aggiunge a this l'elemento obj di chiave (priorita') key
	{
		heapnodearray[nextfree]=new HeapNode(obj,key);
		int i=nextfree;
		heapnodearray[0].key=0;
        while (i>0 && heapnodearray[Parent(i)].key>heapnodearray[i].key)
        {
			System.out.println("ciao");
			HeapNode temp=heapnodearray[Parent(i)];
			heapnodearray[Parent(i)]=heapnodearray[i];
			heapnodearray[i]=temp;
			i=Parent(i);
        }
		if (nextfree!=heapnodearray.length-1)
	    	nextfree++;
	}
    private void heapify(int indice)
    {
		int indexLeft, indexRight,min;
		indexLeft=Left(indice);
		indexRight=Right(indice);
		if(heapnodearray[indexLeft].key<heapnodearray[indice].key)
			min=indexLeft;
		else min=indice;
		if(heapnodearray[indexRight].key<heapnodearray[min].key)
			min=indexRight;
		if (min!=indice)
        {
			HeapNode temp=heapnodearray[min];
			heapnodearray[min]=heapnodearray[indice];
			heapnodearray[indice]=temp;
            heapify(min);
		}
	}
	public Object Dequeue ()
	// elimina e ritorna il minimo
	{
   	    Object min=heapnodearray[0].info;
		heapnodearray[0]=heapnodearray[nextfree];
        heapnodearray[nextfree]=null;
        nextfree--;
		heapify(0);
		return min;
	}
	public Object Minimum ()
	// ritorna il minimo senza rimuoverlo dalla coda
	{
			return heapnodearray[0].info;
	}
	public void DecreaseKey (Object obj, int newkey)
	//	pre: obj e' nella coda this, con chiave key, e newkey <= key
	//  post: obj e' in this con chiave newkey
	{
		for (int i=0;i<heapnodearray.length-1;i++)
		{
			if (heapnodearray[i]!=null && heapnodearray[i].info==obj)
			{
				heapnodearray[i].key=newkey;
				heapify(i);
			}
		}
	}
	private class HeapNode
	{
		Object info;
		int key;
		HeapNode (Object i, int k)
		{
			info = i;
			key = k;
		}
	}
	private HeapNode[] heapnodearray;
	// array destinato a contenere le coppie (obj, key)
	private int nextfree;
	// indice della prossima locazione libera su heapnodearray
	public Heap (int maxnumelements)
	{
		heapnodearray = new HeapNode[maxnumelements];
		nextfree = 0;
	}
	private int Left (int i)
	{
		int l = 2*i + 1;
		if (l > nextfree) return i;
		return l;
	}
	private int Right (int i)
	{
		int r = 2*i + 2;
		if (r > nextfree) return i;
		return r;
	}
	private int Parent (int i)
	{
		if (i > 0) return  (i+1)/2 - 1;
		return i;
	}
	public String toString ()
	{
		String s = "";
		for (int i = 0; i < nextfree; i++)
			if (heapnodearray[i].key != Integer.MAX_VALUE) s +=
heapnodearray[i].key + " ";
			else s += "inf ";
		return s;
	}
}
// ----------------- Grafi -----------------
/** Classe di implementazione di grafi orientati,
    con archi pesati.
    Le etichette dei vertici sono caratteri
    Metodi pubblici della classe:
    public void addVertex(char label_of_vertex)
	// aggiunge un vertice di etichetta label_of_vertex
	// se il grafo non ha vertici con questa etichetta
	public void addEdge(char labelsource, char labeldes, int weight)
	// aggiunge l'arco (labelsource, labeldes) di peso weight;
	// se l'arco (labelsource, labeldes) gia' esiste, ne aggiorna il peso
	public void addEdge(int labelsource, int labeldes)
	// aggiunge l'arco di (labelsource,labeldes) di peso 1
	// sovraccarica addEdge(int,int,int)
	public int cardVertexes ()
	// ritorna la cardinalita' del grafo
	// (il numero dei suoi vertici)
*/
class Graph
{
	// colori impiegati nelle visite
		final static int WHITE = 1; // vertice esterno
		final static int GRAY  = 2; // vertice sulla frontiera
		final static int BLACK = 3; // vertice interno
	// classe dei vertici
	protected class Vertex
	{
		char label;		// etichetta
		int color;		// colore
		AdjList alist;	// lista degli adiacenti
		Vertex (char lbl)
		{
			this(lbl, WHITE, null);
		}
		Vertex (char lbl, int col, AdjList al)
		{
			label = lbl;
			color = col;
			alist = al;
		}
		ListIterator iterator()
		{
			ListIterator itr = new ListIterator(alist);
			return itr;
		}
	}
	// iteratore sulle liste di adiacenza
	protected class ListIterator
	{
		AdjList alist;
		ListIterator (AdjList a)
		{
			alist = a;
		}
		boolean hasNext()
		{
			return alist != null;
		}
		AdjList next()
		{
			AdjList n = alist;
			alist = alist.next;
			return n;
		}
	}
	// classe degli archi
	protected class Edge implements Comparable
	{
		int fst, snd;  // indici dei vertici in cui l'arco incide
		int weight;    // peso dell'arco
		Edge (int f, int s, int w)
		{
			fst = f;
			snd = s;
			weight = w;
		}
		public int compareTo (Object o)
		// post: confronta this con o (che e' un arco) in base al peso
		//       ritornando: -1 se this.weight < o.weight
		//                    0 se this.weight = o.weight
		//                    1 se this.weight > o.weight
		{
			Edge e = (Edge) o;
			if (weight < e.weight) return -1;
			if (weight > e.weight) return  1;
			return 0;
		}
	}
	// classe degli elementi delle liste di adiacenza
	protected class AdjList
	{
		int vertexIndex;  // indice del vertice in cui l'arco incide
		int weight; 	  // peso dell'arco
		AdjList next;	  // prossimo nella lista
		AdjList (int i, int w, AdjList n)
		{
			vertexIndex = i;
			weight = w;
			next = n;
		}
		public String toString ()
		{
			String s = "" + "(" + ((Vertex)vertices.elementAt(vertexIndex)).label
+
			           "," + weight + ") ";
			if (next != null) s += next;
			return s;
		}
	}
	protected Vector vertices = new Vector(); // vettore dei vertici
	public int addVertex(char label_of_vertex)
	// aggiunge un vertice di etichetta label_of_vertex
	// se il grafo non ha vertici con questa etichetta
	{
		Vertex v = new Vertex(label_of_vertex);
		int i = 0;
		while (i < vertices.size() &&
				((Vertex)vertices.elementAt(i)).label != label_of_vertex)
			i++;
		// post: i == l'indice del primo vertice con etichetta ==
label_of_vertex
		//       se esiste; i == vertices.size() altrimenti
		if (i == vertices.size()) vertices.addElement(v);
			// il nuovo vertice viene aggiunto se non ne esisteva uno
			// con la stessa etichetta
		return i; // i e' in ogni caso l'indice dove ora si trova il vertice
	}
	protected AdjList ordInsert (int i, int w, AdjList l)
	// inserimento ordinato per indice sulla lista degli adiacenti
	// con sovrascrittura del peso in caso di elemento gia' esistente
	{
		if (l == null || i < l.vertexIndex) return new AdjList(i, w, l);
		if (l.vertexIndex == i)
		{
			l.weight = w;
			return l;
		}
		l.next = ordInsert(i, w, l.next);
		return l;
	}
	public void addEdge(char labelsource, char labeldes)
	// aggiunge l'arco di (labelsource,labeldes) di peso 1
	{
		addEdge(labelsource, labeldes, 1); // default per il peso == 1
	}
	public void addEdge(char labelsource, char labeldes, int weight)
	// aggiunge l'arco (labelsource, labeldes) di peso weight;
	// se l'arco (labelsource, labeldes) gia' esiste, ne aggiorna il peso
	{
		int i = addVertex(labelsource);
		int j = addVertex(labeldes);
		Vertex vrt = ((Vertex)vertices.elementAt(i));
		vrt.alist = ordInsert(j, weight, vrt.alist);
	}
	public int cardVertexes ()
	// ritorna la cardinalita' del grafo
	// (il numero dei suoi vertici)
	{
		return vertices.size();
	}
	public String toString ()
	{
		String s = "";
		for (int i = 0; i < vertices.size(); i++)
		{
			s += ((Vertex)vertices.elementAt(i)).label + ": ";
			if (((Vertex)vertices.elementAt(i)).alist != null)
				s += ((Vertex)vertices.elementAt(i)).alist;
			s += "\n";
		}
		return s;
	}
}
/*
	classe UnorderedGraph per la rappresentazione di grafi non orientati
	estende la classe Graph
	Ridefinizioni:
	public void addEdge (char labelsource, char labeldes, int weight)
	// aggiunge l'arco non orientato {labelsource, labeldes} di peso
	// weight, aggiungendo alla struttura gli archi
	// orientati (labelsource, labeldes) e (labeldes, labelsource)
	// di egual peso
	// ridefinisce: Graph.addEdge
	Estensioni:
	public int getTotalweight()
	// la classe mantiene un campo privato:
	// int Totalweight == somma dei pesi degli archi
	// che viene incrementato da addEdge e ispezionato
	// da getTotalweight()
*/
class UnorderedGraph extends Graph
{
	private int Totalweight; // somma dei pesi degli archi
	UnorderedGraph ()
	{
		super(); 	     // chiamata al costruttore di Graph
		Totalweight = 0;
	}
	public int getTotalweight()
	// metodo di lettura della somma dei pesi degli archi
	{
		return Totalweight;
	}
	public void addEdge (char labelsource, char labeldes, int weight)
	// aggiunge l'arco non orientato {labelsource, labeldes} di peso
	// weight, aggiungendo alla struttura (labelsource, labeldes)
	// e (labeldes, labelsource)
	// ovverrides: Graph.addEdge
	{
		// gli archi sono inseriti usando il metodo Graph.AddArc
		super.addEdge(labelsource, labeldes, weight);
		super.addEdge(labeldes, labelsource, weight);
		Totalweight += weight;
	}
	/* Algoritmo MST_Prim, per il calcolo
	   di un albero di copertura minima del grafo pesato
	   e non ordinato this con l'algoritmo di Prim
	   pre:  il grafo this e' connesso
	   post: ritorna un grafo pesato aciclico non ordinato, che
	         rappresenta un MST di this
	*/
	private class VertexIndex
	// mio contenitore per i vertici, identificati con i
	// rispettivi indici nel Vector Graph.vertices
	// da impiegarsi quando un vertice viene ineserito nella
	// coda di priorita'
	{
		int index;
		public boolean equals (Object vi)
		{
			return index == ((VertexIndex)vi).index;
		}
		VertexIndex (int i)
		{
			index = i;
		}
	    public char returnInd(Graph G)
		{
			return ((Vertex)G.vertices.elementAt(index)).label;
	    }
	}
	public UnorderedGraph MST_Prim ()
	{
		UnorderedGraph T = new UnorderedGraph();
		int [] father = new int [cardVertexes()];
		int [] key = new int [cardVertexes()]; //vettore di appetibilità
		boolean [] isinqueue = new boolean[cardVertexes()];
		Heap Q = new Heap(cardVertexes ());
		if(this==null) return T;
		for (int i=0; i<cardVertexes(); i++)   //inizializzazione delle
appetibilita a infinito
		{
			key[i]=Integer.MAX_VALUE;
			VertexIndex vertice=new VertexIndex(i);
			//System.out.println(((Vertex)vertices.elementAt(i)).label);
			Q.Enqueue(vertice,Integer.MAX_VALUE);
			father[i]= 0;
			isinqueue[i]=true;
		}
    	VertexIndex vertice1=new VertexIndex(0);
		char label=vertice1.returnInd(this);
		T.addVertex(label);
        while(!Q.IsEmpty())
        {
			VertexIndex v=(VertexIndex)Q.Dequeue();
			isinqueue[v.index]=false;
			ListIterator a=((Vertex) vertices.elementAt(v.index)).iterator();
			while (a.hasNext())
			{
				AdjList x=a.next();
				if (isinqueue[x.vertexIndex]==true && x.weight<key[x.vertexIndex])
				{
                      key[x.vertexIndex]=x.weight;
                      father[x.vertexIndex]=v.index;
                      Q.DecreaseKey(x,x.weight);
				}
        	}
	    }
     	for (int i=0;i<cardVertexes(); i++)
		{
		 	int w,u;
		 	u=father[i];
		 	char label1=((Vertex)vertices.elementAt(u)).label;
		 	char label2=((Vertex)vertices.elementAt(i)).label;
			w=key[i];
			T.addEdge(label1,label2,w);
		}
       return T;
	}
}
class PrimTest
{
	public static void main(String[] args)
	{
		UnorderedGraph G = new UnorderedGraph();
		G.addEdge('a','b',4);
		G.addEdge('a','h',8);
		G.addEdge('b','h',11);
		G.addEdge('b','c',8);
		G.addEdge('c','d',7);
		G.addEdge('c','f',4);
		G.addEdge('c','i',2);
		G.addEdge('d','e',9);
		G.addEdge('d','f',14);
		G.addEdge('e','f',10);
		G.addEdge('f','g',2);
		G.addEdge('g','h',1);
		G.addEdge('g','i',6);
		G.addEdge('h','i',7);
		System.out.println("Grafo G:\n" + G);
		System.out.println("w(G) = " + G.getTotalweight() + "\n");
		UnorderedGraph T = G.MST_Prim();
		System.out.println("Albero T:\n" + T);
		System.out.println("w(T) = " + T.getTotalweight());
		/*
		Il main produce la stampa:
		Grafo G:
		a: (b,4) (h,8)
		b: (a,4) (h,11) (c,8)
		h: (a,8) (b,11) (i,7) (g,1)
		c: (b,8) (d,7) (f,4) (i,2)
		d: (c,7) (f,14) (e,9)
		f: (c,4) (d,14) (e,10) (g,2)
		i: (h,7) (c,2) (g,6)
		e: (d,9) (f,10)
		g: (h,1) (f,2) (i,6)
		w(G) = 93
		Albero T:
		b: (a,4)
		a: (b,4) (h,8)
		h: (a,8) (g,1)
		c: (f,4) (d,7) (i,2)
		f: (c,4) (g,2)
		d: (c,7) (e,9)
		g: (h,1) (f,2)
		i: (c,2)
		e: (d,9)
		w(T) = 37
		*/
	}
}
-- 
Posted via Mailgate.ORG Server - 
http://www.Mailgate.ORG

