algorithm - profundidad - Mejor algoritmo para detectar ciclos en una gráfica dirigida.
dfs algorithm (13)
Comience con un DFS: existe un ciclo solo si se descubre un back-edge durante el DFS . Esto se demuestra como resultado del teorema del camino blanco.
¿Cuál es el algoritmo más eficiente para detectar todos los ciclos dentro de un gráfico dirigido?
Tengo un gráfico dirigido que representa una programación de trabajos que deben ejecutarse, un trabajo que es un nodo y una dependencia una ventaja. Necesito detectar el caso de error de un ciclo dentro de este gráfico que conduce a dependencias cíclicas.
Como ha dicho, tiene un conjunto de trabajos, debe ejecutarse en cierto orden. Topological sort dado el orden requerido para la programación de trabajos (o para problemas de dependencia si se trata de un direct acyclic graph ). Ejecute dfs y mantenga una lista, y comience a agregar un nodo al principio de la lista, y si se encuentra con un nodo que ya está visitado. Luego encontraste un ciclo en una gráfica dada.
Dado que este es un calendario de trabajos, sospecho que en algún momento los ordenará en un orden de ejecución propuesto.
Si ese es el caso, entonces una implementación de ordenamiento topológico puede, en cualquier caso, detectar ciclos. Unix tsort ciertamente lo hace. Creo que es probable que, por lo tanto, sea más eficiente detectar ciclos al mismo tiempo que realizar un pedido, en lugar de hacerlo en un paso separado.
De modo que la pregunta podría convertirse en "cómo puedo hacer un pedido más eficiente", en lugar de "cómo detectar bucles de manera más eficiente". A lo que probablemente la respuesta sea "use una biblioteca", pero si falla el siguiente artículo de Wikipedia:
tiene el pseudocódigo para un algoritmo y una breve descripción de otro de Tarjan. Ambos tienen complejidad en el tiempo O(|V| + |E|) .
En mi opinión, el algoritmo más comprensible para detectar el ciclo en un gráfico dirigido es el algoritmo de colorear gráfico.
Básicamente, el algoritmo de colorear gráfico recorre el gráfico de manera DFS (búsqueda en profundidad, lo que significa que explora una ruta completamente antes de explorar otra ruta). Cuando encuentra un borde posterior, marca el gráfico como que contiene un bucle.
Para obtener una explicación detallada del algoritmo de coloreado de gráficos, lea este artículo: http://www.geeksforgeeks.org/detect-cycle-direct-graph-using-colors/
Además, proporciono una implementación de coloración de gráficos en JavaScript https://github.com/dexcodeinc/graph_algorithm.js/blob/master/graph_algorithm.js
Había implementado este problema en sml (programación imperativa). Aquí está el esquema. Encuentre todos los nodos que tengan un grado de ingreso o un grado de salida de 0. Dichos nodos no pueden formar parte de un ciclo (elimínelos). A continuación, elimine todos los bordes entrantes o salientes de dichos nodos. Aplicar recursivamente este proceso al gráfico resultante. Si al final no te queda ningún nodo o borde, el gráfico no tiene ningún ciclo, de lo contrario tiene.
La forma en que lo hago es hacer un ordenamiento topológico, contando el número de vértices visitados. Si ese número es menor que el número total de vértices en el DAG, tiene un ciclo.
La forma más sencilla de hacerlo es hacer un recorrido transversal primero (DFT) de profundidad del gráfico .
Si la gráfica tiene n vértices, este es un algoritmo de complejidad de tiempo O(n) . Dado que posiblemente tendrá que hacer una DFT a partir de cada vértice, la complejidad total se convierte en O(n^2) .
Debe mantener una pila que contenga todos los vértices en el primer recorrido de la profundidad actual , siendo su primer elemento el nodo raíz. Si te encuentras con un elemento que ya está en la pila durante la DFT, entonces tienes un ciclo.
No hay algoritmo que pueda encontrar todos los ciclos en un gráfico dirigido en tiempo polinomial. Supongamos que el gráfico dirigido tiene n nodos y cada par de nodos tiene conexiones entre sí, lo que significa que tiene un gráfico completo. Por lo tanto, cualquier subconjunto no vacío de estos n nodos indica un ciclo y hay 2 ^ n-1 número de tales subconjuntos. Así que no existe un algoritmo de tiempo polinomial. Supongamos que tiene un algoritmo eficiente (no estúpido) que puede indicarle el número de ciclos dirigidos en un gráfico; primero puede encontrar los componentes conectados fuertes y luego aplicar su algoritmo a estos componentes conectados. Dado que los ciclos solo existen dentro de los componentes y no entre ellos.
Si DFS encuentra un borde que apunta a un vértice ya visitado, tiene un ciclo allí.
Si no puede agregar una propiedad "visitada" a los nodos, use un conjunto (o mapa) y simplemente agregue todos los nodos visitados al conjunto a menos que ya estén en el conjunto. Utilice una clave única o la dirección de los objetos como la "clave".
Esto también le proporciona la información sobre el nodo "raíz" de la dependencia cíclica que será útil cuando un usuario tenga que solucionar el problema.
Otra solución es tratar de encontrar la siguiente dependencia a ejecutar. Para esto, debe tener alguna pila donde pueda recordar dónde se encuentra ahora y qué debe hacer a continuación. Compruebe si ya hay una dependencia en esta pila antes de ejecutarla. Si es así, has encontrado un ciclo.
Si bien esto puede parecer que tiene una complejidad de O (N * M), debe recordar que la pila tiene una profundidad muy limitada (por lo que N es pequeña) y que M se hace más pequeña con cada dependencia que puede marcar como "ejecutado" más puede detener la búsqueda cuando encuentra una hoja (para que nunca tenga que revisar todos los nodos -> M también será pequeño).
En MetaMake, creé el gráfico como una lista de listas y luego eliminé todos los nodos a medida que los ejecutaba, lo que naturalmente reducía el volumen de búsqueda. Nunca tuve que realizar una verificación independiente, todo sucedió automáticamente durante la ejecución normal.
Si necesita un modo "solo de prueba", simplemente agregue un indicador de "ejecución en seco" que deshabilita la ejecución de los trabajos reales.
Si una gráfica satisface esta propiedad.
|e| > |v| - 1
entonces la gráfica contiene al menos en ciclo.
El algoritmo de componentes fuertemente conectados de Tarjan tiene una complejidad de tiempo O(|E| + |V|) .
Para otros algoritmos, vea Componentes fuertemente conectados en Wikipedia.
https://mathoverflow.net/questions/16393/finding-a-cycle-of-fixed-length Me gusta esta solución la mejor especialmente para 4 longitud :)
También el asistente de física dice que tienes que hacer O (V ^ 2). Creo que solo necesitamos O (V) / O (V + E). Si el gráfico está conectado, DFS visitará todos los nodos. Si el gráfico ha conectado sub gráficos, cada vez que ejecutamos un DFS en un vértice de este sub gráfico, encontraremos los vértices conectados y no tendremos que considerarlos para la próxima ejecución del DFS. Por lo tanto la posibilidad de correr para cada vértice es incorrecta.