[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).
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
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
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