Detecci n de ciclos

DETECCIÓN DE
CICLOS
Subtema:
El problema Encontrar-Unión
(Unión-Find)

OBJETIVO
 Ver

la lógica que tienen los
recorridos de grafos, para poder
encontrar el dato solicitado ydetectar cuando dos recorridos te
llevan al mismo lugar.

ALCANCE
 Ver

la deficiencia de ciertos
recorridos al tener redundancia en
los datos.

DETECCIÓN DE CICLOS
Se basa en ladetección de ciclos en
los grafos.
Es un algoritmo cúbico, el cual en
muchas
situaciones
es
muy
insuficiente. A

C

C

C

Para los grafos indirectos, son necesarias
pequeñas modificaciones enDFS(v) con el
fin de detectar los ciclos y reportarlos
cycleDeteccionDFS(v)
núm(v) = i++;
For todo los vértices u adyacentes
av
If núm(u) es 0
añade edge(uv) a edges;CycleDetectionDFS(u);
Else if edge(vu) no está en edges
Ciclo detectado;

EL PROBLEMA DE ENCONTRAR
UNIÓN
 Determinar

si los vértices están en el
mismo conjunto.

 Se

realizan dos operacionesimplementar esta tarea:

para

D

A

B
C

Encontrar el conjunto
al cual pertenece un
vértice v y unir dos
conjuntos en uno si el
vértice v pertenece a
uno de ellos y w al
otro.
A
C

B

DL1
a

b

c

d

L1

L2
p

q

r

a

b

c

L1
p

q

r

d

Initialize()
For i = 0 a |V| -1
root[i] nex[i] = i;
Length[i] = 1;
Union() puede definirse como sigue:
Union(edge(vu))
If(root[u] == root[v])

//ignora esta arista

Return;

//como v y u están en

Else if (length[root[v]] < length[root[u]])
Rt = root[v];

//el mismo conjunto; combina
//dos conjuntos en uno;Length[root[u] += length[rt];
Root[rt] = root[u];

//actualiza la raíz de rt y

For (j = next[rt]; j != rt; j = next[j])

//luego otros vertices

Root[j] = root[u];

//en la listacircular;

Swap(next[rt], next[root [u]]);
Add edge(vu) a spanningTree;
Else //if length[root[v]] >= length[root[u]]
//prosigue como antes, con v y u invertidos;

//fusiona dos listas;