Versão iterativa de DIGRAPHpath

Versão iterativa de DIGRAPHpath

por Fernando Akira Fujihara -
Número de respostas: 3

Olá pessoal,

Estava estudando a versão iterativa do DIGRAPHpath e surgiram dúvidas (em azul). Algúem pode me ajudar?

Em verde estão os comentários relacionados ao que etendi do algoritmo. Se eu estiver pensando errado nestes comentários, por favor me corrijam.

 while(k!= 1 || w!= G->V) ???
 {

  /*  Backtracking  ??? */
  if(w == G->V) /* Chegou no limite de w */
  {
   w = v + 1; ???
   k--; ???
   v = caminho[k-1]; ???
  }
  /* Atingiu um novo arco (que era AZUL), representado por w. */
  else if(G->adj[v][w] == 1 && lbl[w] == AZUL)
  {
   lbl[w] = VERMELHO; /* marca de vermelho o vértice atingido (w) */
   caminho[k++] = w; /* guarda o vértice na próxima posição (k) do vetor caminho */
   v = w; /* equivalente à recursão, começa a nova busca */
   w = 0;
  }
  else /* tenta próximo w */
   w++;

...

Em resposta à Fernando Akira Fujihara

Re: Versão iterativa de DIGRAPHpath

por Henrique Stagni -

Não sei se ajuda muito, mas eu coloquei uma explicação ae do que eu entendi comparando com a função recursiva.

 while(k!= 1 || w!= G->V) /* Eu entendo melhor essa condição pensando na equivalente: "while(!(k==1 && w==G->V))" ou seja ele para quando w=G->V (condição para o "backtracking") e ao mesmo tempo k==1 ou seja não há mais para onde voltar (k==1 significa que o único vertice na pilha(caminho) é aquele que começamos a busca)*/
 {

  /*  Backtracking */
  if(w == G->V) /* Chegou no limite de w. Aqui é como se estivessemos "voltando da chamada recursiva". Devemos voltar para o v que estávamos antes e procurar os w que faltavam */
  {
   w = v + 1; /* O próximo w que deve ser usado: Na parte em verde, quando "entramos na chamada recursiva" setamos "v = w". Agora, que estamos "voltando na recursão", devemos continuar do w seguinte ao que paramos(que no momento está armazenado em v)*/
   k--; ??? /* Aqui voltamos um vertice no caminho. Pensando na recursão, estamos desimpilhando uma chamada */
   v = caminho[k-1]; /* caminho[k-1] é o último vértice que havíamos empilhado. Estamos justamente voltando para ele para continuar percorrendo os w que faltam */
  }

/* Atingiu um novo arco (que era AZUL), representado por w. */
  else if(G->adj[v][w] == 1 && lbl[w] == AZUL)
  {
   lbl[w] = VERMELHO;
/* marca de vermelho o vértice atingido (w) */
   caminho[k++] = w; /* guarda o vértice na próxima posição (k) do vetor caminho */
   v = w; /* equivalente à recursão, começa a nova busca */
   w = 0;
  }
  else
/* tenta próximo w */
   w++;