import java.util.LinkedList;

public class Prim {

    public static final int INFINITY = 10000;
    static int vertex_num;
    static Vertex V[];
    static int w[][];
    static Heap Q;

    public static void add_edge (char c1, char c2, int distance) {
	Vertex v1, v2;
	int i;
	v1= null;
        v2 = null;
	for (i = 0; i < vertex_num; i++) {
	    if (V[i].name == c1) {
		v1 = V[i];
	    }
	    if (V[i].name == c2) {
		v2 = V[i];
	    }
	}
	
	if (v1 != null && v2 != null) {
	    v1.adj_list.add(v2);
	    v2.adj_list.add(v1);
	    w[v1.ID][v2.ID] = distance;
	    w[v2.ID][v1.ID] = distance;
	}
    }


    public static void main(String[] args) {
	
	int i,j;
	Vertex u,v;
	int pos;

	vertex_num = 9;
	/* initialize weight matrix */
	w = new int[vertex_num][vertex_num];
	for (i = 0; i < vertex_num; i++) {
	    for (j = 0; j < vertex_num; j++) {
		if (i==j) {
		    w[i][j] = 0;
		}
		else {
		    w[i][j] = - INFINITY;
		}
	    }
	}

	/* initialize the graph with adjacency list */
	V = new Vertex[vertex_num];
	for (i = 0; i < vertex_num; i++) {
	    V[i]= new Vertex();
	    V[i].ID = i;
	    V[i].in_Q = true;
	    V[i].adj_list = new LinkedList<Vertex>();
	}
	
	V[0].name = 'a';
	V[1].name = 'b';
	V[2].name = 'c';
	V[3].name = 'd';
	V[4].name = 'e';
	V[5].name = 'f';
	V[6].name = 'g';
	V[7].name = 'h';
	V[8].name = 'i';

	add_edge('a','b', 4);

	add_edge('b','c', 8);
	add_edge('b','h', 11);
	add_edge('c','d', 7);	
	add_edge('c','f', 4);	
	add_edge('c','i', 2);	
	add_edge('d','e', 9);	
	add_edge('d','f', 14);	
	add_edge('e','f', 10);	
	add_edge('f','g', 2);	
	add_edge('g','i', 6);	
	add_edge('g','h', 1);	
	add_edge('a','h', 8);
	add_edge('h','i', 7);	

	for (i = 0; i < vertex_num; i++) {
	    V[i].key = INFINITY;
	    V[i].parent = null;
	}

	V[0].key = 0;
	
	/* add all vertices to a heap */
	Q = new Heap();
	for (i = 0; i < vertex_num; i++) {
	    Q.add_node(V[i].key, V[i]);
	}
	

	while (Q.not_empty()) {
	    u = Q.extract_min();
	    if (u.parent == null) {
		System.out.println ("First Node: " + u.name);
	    }
	    else {
		System.out.println ("Add Edge: " + u.parent.name + " -- " + u.name + "            Distance: " + u.key);
	    }
	    for (i = 0; i < u.adj_list.size(); i++) {
		v = u.adj_list.get(i);
		if (v.in_Q && w[u.ID][v.ID] < v.key) {
		    v.parent = u;
		    v.key = w[u.ID][v.ID];
		    pos = v.Q_pos;
		    Q.key[pos] = v.key;
		    Q.up_heap(pos);
		}
	    }

	}

    }

}