Tengo un problema hw que solicita un algoritmo que detecta si hay algún ciclo en cualquier gráfico no dirigido que contenga un borde dado 'E'. El algoritmo debe ejecutarse en O (N) tiempo lineal.¿Cómo verificar si un borde está en algún ciclo?
El problema que tengo es que no sé por dónde empezar. Tengo algunos gráficos de muestra simples pero no sé a dónde ir desde allí.
¿Alguna pista?
Usted comienza con el borde 'e'. De él deberías obtener los dos vértices que conecta. De ellos obtienes otros bordes y otros vértices, y otros bordes y otros vértices, y ... Necesitarás una forma de averiguar si un vértice ya ha sido 'visitado' por tu algoritmo. Si tiene, entonces hay un ciclo del cual 'e' es parte.
Haga una búsqueda en profundidad para agregar nodos a una lista sobre la marcha, y eliminarlos de la lista cuando regrese.
La lista representa su ruta actual de recorrido.
Si te encuentras con un nodo que ya está en tu lista, entonces hay un ciclo/ciclo.
para el borde (u, v):
1- realizar una primera búsqueda en profundidad a partir de u, determinar si se encuentra v y un borde posterior existen a lo largo de la ruta a v
2-. realizar una primera búsqueda en profundidad de v, u si se detecta y borde posterior existen para u, entonces hay un ciclo que incluye tanto u como v.
En otras palabras,
1- realizar una DFS partir de u , compruebe si el borde posterior existe y v aún no ha finalizado.
2- Realice un DFS comenzando desde v, compruebe si el borde posterior existe y u no ha finalizado aún si ambas condiciones son verdaderas, entonces el borde (u, v) pertenece a un ciclo.
Elimine ese borde (u, v) de G. 1. Ejecute BFS para ver si todavía se puede acceder a v desde usted. 2. Si es así, entonces el gráfico original tiene un ciclo que contiene e. de lo contrario no hay.
¿Una pista? Por supuesto. Algunos conjuntos (como hashsets) tienen búsqueda O (1). – corsiKa