#define INTREE 0
#define FRINGE 1
#define UNSEEN 2

/*
  Esta versão do algoritmo Prim codifica a ORLA como uma lista
  representada em arrays (variáveis "fringeList", "fringLink[]", "fringeWgt[]").

  A árvore do resultado é representada também num array dos ascententes
  (variável "parent[]").
*/
void mst(ALGraph g)
{
  int status[g.nVert];		// estado do vértice (UNSEEN->FRINGE->INTREE)

  int fringeList;		// Início da lista
  int fringeLink[g.nVert];	// próximo elemento da lista (-1 no fim)
  int fringeWgt[g.nVert];	// peso do elemento respectivo

  int parent[g.nVert];		// informação do pai (árvore num array)

  int edgeCount;		// número de arcos já na árvore
  bool stuck;			// Não consegue prosseguir...

  /* outras variáveis auxiliares... */
  ALNode *ptr;
  int x,y;
  int sum;

  /* inicializacao */
  x = 0; 
  status[0] = INTREE;
  edgeCount = 0;
  fringeList = -1;
  for (y = 1 ; y < g.nVert ; y++) status[y] = UNSEEN;
  stuck = false;
  

  /* Ciclo principal */
  while(edgeCount<g.nVert-1 && (!stuck)) {

    /* percorre lista de adjacencias de x */
    ptr = g.adjL[x];
    while(ptr) {
      y = ptr->vert;
      if (status[y]==FRINGE && ptr->info<fringeWgt[y]) {
	/* substituir arco candidato de y por xy */
	parent[y] = x;
	fringeWgt[y] = ptr->info;
      }
      else if (status[y]==UNSEEN) {
	/* inserir y na orla com xy como arco candidato */
	status[y] = FRINGE;
	fringeLink[y] = fringeList;
	fringeList = y;
	parent[y] = x;
	fringeWgt[y] = ptr->info;
      }
      ptr = ptr->next;
    } /* while(ptr) -- LISTA DE ADJACÊNCIA (sucessores) */

    /* escolher próximo vértice (e respectivo arco) da orla
       para entrar para a árvore */
    if (fringeList==-1) stuck = true; // não pode prosseguir...
    else { // escolhe o vértice apropriado (com menor peso)
      int prev = -1;
      x = fringeList;
      for (y=fringeList; fringeLink[y]!=-1; y=fringeLink[y]) 
	if (fringeWgt[fringeLink[y]]<fringeWgt[x]) {
	  x = fringeLink[y];
	  prev = y;
	}
      if (x==fringeList) // remove no início da lista...
	fringeList = fringeLink[x];
      else // remove no meio da lista...
	fringeLink[prev] = fringeLink[x];
      fringeLink[x] = -1;
      status[x] = INTREE;
      edgeCount++;
    }
  } /* while(edgeCount) -- CICLO PRINCIPAL!!! */

  // VISUALIZA RESULTADO...
  for (x=1, sum=0 ; x<g.nVert ; x++) {
      printf("\n\t%d-->%d, peso %d", x, parent[x], fringeWgt[x]);
      sum+=fringeWgt[x];  
  }
  printf("\n\n\tSum = %d\n", sum);
}