public Grafo getArvoreGeradoraMinima() {
        Grafo g = new Grafo(true);
        //implementa a Árvore Geradora Minima através do Algoritmo de Prim      
        int[] parent = new int[tamanho]; // Array para armazenar a árvore.
        int[] key = new int[tamanho];   // Array para armazenar os valores minimos das arestas
        boolean[] mstSet = new boolean[tamanho];  // Array para armazenar o conjuto de vértices qeu não foram incluídos na árvore

        // inicializo os valores com o infinito
        for (int i = 0; i < this.tamanho; i++) {
            key[i] = Integer.MAX_VALUE;
            mstSet[i] = false;
        }

        // sempre incluo o primeiro vértice a árvore
        key[0] = 0;     // atribuo como zero para ser o primeiro vértice selecionado.
        parent[0] = -1; // primeiro nó é a raiz da árvore.

        // 
        for (int i = 0; i < this.tamanho - 1; i++) {
            // pego o menor valor que não esteja incluida na árvore            
            int u = minKey(key, mstSet);

            // adiciono o valor no conjunto da árvore
            mstSet[u] = true;
            
            for (int v = 0; v < this.tamanho; v++) 
            // graph[u][v] is non zero only for adjacent vertices of m
            // mstSet[v] é falso para vértices não inclusos na AGM.
            // Atualiza a chave somente se graph[u][v] for menor que key[v]
            {
                if ( this.matriz[u][v] != 0 && mstSet[v] == false && this.matriz[u][v] < key[v]) {
                    parent[v] = u;
                    key[v] = this.matriz[u][v];
                }
            }
        }
        
        //boolean primeiro = true;
        for (int i = 1; i < parent.length; i++){
            if (g.getVerticeById(String.valueOf(alfabeto.charAt(parent[i]))) == null){
                g.addVertice(new Vertice(String.valueOf(alfabeto.charAt(parent[i]))));
            }
            if (g.getVerticeById(String.valueOf(alfabeto.charAt(i))) == null){
                g.addVertice(new Vertice(String.valueOf(alfabeto.charAt(i))));
            }
            g.addLigacao(new Vertice(String.valueOf(alfabeto.charAt(parent[i]))), 
                         new Vertice(String.valueOf(alfabeto.charAt(i))), 
                         matriz[i][parent[i]]);
            /*if (parent[i] == 0 && primeiro){
                primeiro = false;
            } else {
                break;
            }*/
            //System.out.printf("%d - %d = %d\n",parent[i], i, matriz[i][parent[i]]);
        }
        return g;
    }