DejarA Ser la matriz de adyacencia para la gráfica.G = (V,E). A(i,j) = 1 si los nodosi yj están conectados con un borde,A(i,j) = 0 de otra manera.

Mi objetivo es el de entender siG Es acíclico o no. Un ciclo se define de la siguiente manera:

i yj estan conectados:A(i,j) = 1j yk estan conectados:A(j,k) = 1k yi estan conectados:A(k,i) = 1

He implementado una solución que navega por la matriz de la siguiente manera:

Empezar desde un borde(i,j)Seleccione el conjuntoO de bordes que son salientes dej, es decir, todos los 1s en elj-th fila deANavegarO en una moda DFSSi una de las rutas generadas desde esta navegación conduce al nodoi, entonces se detecta un ciclo

Obviamente esta solución es muy lenta, ya que tengo que evaluar todos los caminos en la matriz. SiA Es muy grande, la sobrecarga requerida es muy grande. Me preguntaba si hay una forma de navegar por la matriz de adyacencia para encontrar ciclos sin usar un algoritmo costoso como el DFS.

Me gustaría implementar mi solución en MATLAB.

Gracias por adelantado,

Eleanore.