Cálculo recursivo de lo[]

[Enunciado]  Queremos escrever uma versão recursiva da função UGRAPHlo(). Basta combinar o código de GRAPHdfs() e dfsR() com a versão iterativa de UGRAPHlo().

int pre[1000], lo[1000];
vertex pa[1000];
int cnt;

void UGRAPHlo( UGraph G) {
   for (vertex v = 0; v < G->V; ++v)
      pre[v] = -1, pa[v] = v;
   cnt = 0;
   for (vertex v = 0; v < G->V; ++v)
      if (pre[v] == -1) {
         pa[v] = v;
         dfsRlo( G, v);
      }
}

static void dfsRlo( UGraph G, vertex v) { 
   pre[v] = cnt++;
   lo[v] = pre[v];
   for (link a = G->adj[v]; a != NULL; a = a->next) {
      vertex w = a->w;
      if (pre[w] != -1) { 
         if (w != pa[v] && pre[w] < lo[v])
            lo[v] = pre[w];
      } else {
         pa[w] = v;
         dfsRlo( G, w);
         if (lo[w] < lo[v])
            lo[v] = lo[w];
      }
   }
}

Compare esse código com a função UGRAPHebicon() (versão on-the-fly).

Exemplo 1

Agora aplique a função que acabamos de escrever ao grafo definido pelas seguintes listas de adjacência:

a: b
b: c a f
c: d b
d: e c
e: f d
f: b e

Veja o rastreamento da execução da função:

a dfsRlo(a)
a-b dfsRlo(b)
  b-c dfsRlo(c)
    c-d dfsRlo(d)
      d-e dfsRlo(e)
        e-f dfsRlo(f)
          f-b
          f-e
          f lo[f]=1
        e-d
        e lo[e]=1
      d-c
      d lo[d]=1
    c-b
    c lo[c]=1
  b-a
  b-f
  b lo[b]=1
a lo[a]=0

Exemplo 2

Aplique a função que acabamos de escrever ao grafo definido pelas seguintes listas de adjacência:

a: b    
b: a c f
c: b d  
d: c e  
e: d f  
f: e b  

Veja o rastreamento da execução da função:

a dfsRlo(a)
a-b dfsRlo(b)
  b-a 
  b-c dfsRlo(c)
    c-b
    c-d dfsRlo(d)
      d-c
      d-e dfsRlo(e)
        e-d 
        e-f dfsRlo(f)
          f-e
          f-b
          f lo[f]=1
        e lo[e]=1
      d lo[d]=1
    c lo[c]=1
  b-f
  b lo[b]=1
a lo[a]=0

Exemplo 3

Aplique a função que acabamos de escrever ao grafo definido pelas seguintes listas de adjacência:

a: b  
b: c a
c: d b
d: e c
e: f d
f:   e

Veja o rastreamento da execução da função:

a dfsRlo(a)
a-b dfsRlo(b)
  b-c dfsRlo(c)
    c-d dfsRlo(d)
      d-e dfsRlo(e)
        e-f dfsRlo(f)
          f-e
          f lo[f]=5
        e-d
        e lo[e]=4
      d-c
      d lo[d]=3
    c-b
    c lo[c]=2
  b-a 
  b lo[b]=1
a lo[a]=0