#define UGraph Graph

/* Recebe um grafo não-dirigido conexo G com custos nas arestas
   e calcula uma MST de G.
   A função trata a MST como uma árvore radicada com 
   raiz 0
   e armazena a árvore no vetor de pais pa[]. 
   (O grafo G e os custos são representados por uma 
   matriz de adjacências.
   A função supõe que todo arco tem custo menor que 
   INFINITY.
   Supõe também que o grafo tem no máximo 1000 vértices. 
   O código é uma versão melhorada
   do Programa 20.3 de Sedgewick.) */

void UGRAPHmstP1( UGraph G, vertex *pa) { 
   bool tree[1000];
   int preco[1000];
   // inicialização:
   for (vertex w = 1; w < G->V; ++w) 
      pa[w] = -1, tree[w] = false, preco[w] = G->adj[0][w]; 
   pa[0] = 0;

   while (true) {
      int min = INFINITY; 
      vertex y;  
      for (vertex w = 0; w < G->V; ++w) 
         if (!tree[w] && preco[w] < min) 
            min = preco[w], y = w; 
      if (min == INFINITY) break;
      tree[y] = true;
      for (vertex w = 0; w < G->V; ++w) 
         if (!tree[w] && G->adj[y][w] < preco[w]) {
            preco[w] = G->adj[y][w]; 
            pa[w] = y; 
         }
   }
}