Exercícios 3a

Variantes de código da função UGRAPHmstPrim1.

1. Discuta e critique a seguinte variante da função UGRAPHmstPrim1.  Como começa cada iteração do while?

   void UGRAPHmstPrim1( UGraph G, vertex *pa) { 
      bool tree[1000];
      int preco[1000];
      for (vertex v = 0; v < G->V; ++v) 
         pa[v] = -1, tree[v] = false, preco[v] = INFINITY; 
      vertex y = 0; 
      pa[y] = y;
      while (true) {
         int min;
         for (link a = G->adj[y]; a != NULL; a = a->next) {
            vertex w = a->w; 
            int c = a->c;
            if (!true[w] && c < preco[w]) 
               pa[w] = y, preco[w] = c; 
         }
         min = INFINITY;
         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;
      }
   }
   

2. Encontre o(s) erro(s) da seguinte implementação:

   void UGRAPHmstPrim1( UGraph G, vertex *pa) { 
      bool tree[1000];
      int preco[1001];
      for (vertex w = 0; w < G->V; ++w)
         pa[w] = -1, tree[w] = false, preco[w] = INFINITY; 
      vertex u = 0;
      pa[u] = 0;
      while (true) {
         int min = INFINITY;
         vertex y;
         for (link a = G->adj[u]; a != NULL; a = a->next) {
            vertex w = a->w;
            if (!tree[w]) { 
               if (a->c < preco[w]) {
                  preco[w] = a->c; 
                  pa[w] = u; 
               }
               if (preco[w] < min) 
                  min = preco[w], y = w; 
            }
         } 
         if (min == INFINITY) break;
         tree[y] = true;
         u = y; 
      }
   }
   

Exercícios 4a

Variantes de código da função UGRAPHmstPrim2().

1. Discuta e critique a seguinte versão de UGRAPHmstPrim2():

   void UGRAPHmstPrim2( UGraph G, vertex *pa) { 
      bool tree[1000];
      int preco[1000];
      PQinit( G->V); 
      for (vertex w = 0; w < G->V; ++w) 
         pa[w] = -1, tree[w] = false; 
      vertex y = 0; 
      pa[y] = y;
      while (true) {
         for (link a = G->adj[y]; a != NULL; a = a->next) {
            vertex w = a->w;
            if (!tree[w]) {
               if (pa[w] == -1) { 
                  preco[w] = a->c; 
                  PQinsert( w, preco); 
                  pa[w] = y; 
               } 
               else if (preco[w] > a->c) {
                  preco[w] = a->c; 
                  PQdec( w, pr); 
                  pa[w] = y; 
               }
            }
         }
         if (PQempty( )) break;
         y = PQdelmin( pr); 
         tree[y] = true; 
      }
   }
   

Exercícios 5a

Variantes de código da função UGRAPHmstPrim3().

1. Discuta e critique a seguinte variante da função UGRAPHmstPrim3():

   void UGRAPHmstPrim3( UGraph G, vertex *pa) { 
      int preco[1000];
      PQinit( G->V); 
      for (vertex w = 0; w < G->V; ++w) { 
         pa[w] = -1;
         preco[w] = INFINITY; 
         PQinsert( w, pr); 
      }
      vertex y = 0; 
      pa[y] = y;
      while (true) {
         for (link a = G->adj[y]; a != NULL; a = a->next) {
            vertex w = a->w;
            if (preco[w] > a->c) { 
               preco[w] = a->c; 
               PQdec( w, preco); 
               pa[w] = y; 
            }
         }
         if (PQempty( )) break;
         y = PQdelmin( pr);
         if (preco[y] == INFINITY) break;
      }
   }