Dado un árbol de expansión y una arista que no está en el árbol de expansión, ¿cómo formar una base de ciclo?

Question

Tengo una gráfica con Edge E y vértice V, puedo encontrar el árbol de expansión usando algoritmo de Kruskal (o cualquier otro tipo de algoritmo de recorrido-retroceso-recorrido-de nuevo), ahora quiero encontrar todas las bases de ciclo que se crean utilizando ese árbol de expansión y los bordes que no están en el árbol, cualquier algoritmo que me permita hacer ¿Eso, además de la búsqueda por fuerza bruta?

Por supuesto, puedo comenzar desde un vértice del borde del árbol que no se extiende, obtener todos los bordes, explorarlos todos, retraerme si encuentro un callejón sin salida, hasta regresar al otro vértice del borde.Pero esto es un poco, err...brutal.¿Alguna otra idea?

Answer 1

Un algoritmo simple que usamos para encontrar ciclos en gráficos:

Cree un árbol de expansión de profundidad donde cada nodo tenga un padre.Al recorrer el árbol, cree un registro de los nodos utilizados.Cuando un borde apunte a un nodo utilizado anteriormente, guárdelo como un borde cíclico.Cuando se completa el árbol de expansión, el recuento de los bordes cíclicos da el recuento de ciclos.Para cada borde cíclico recurrir a través de los antepasados ​​de los dos nodos hasta que se encuentra un antepasado común.Eso dará exactamente los ciclos.

Puede resultar útil tener un índice (tabla hash) de todos los ancestros de un nodo de borde cíclico para poder encontrar rápidamente el ancestro común.

Dudo que este sea el mejor algoritmo, pero es bastante rápido.

EDITAR en repsonse para comentar Cada nodo del árbol de expansión tiene un padre.Cuando se alcanza un nodo en un borde cíclico, calcula su lista de antepasados. (List<Node>Esta lista podría indexarse ​​por velocidad (es decir,contiene() es < O(n)).Cuando un borde cíclico con dos nodos (n1, n2) se encuentra y luego se itera a través de los antepasados ​​de n1, n1.ancestorList (rápidamente ya que la lista ya ha sido creada) y probar si el antepasado está en n2.ancestorList.Si se (commonAncestor) es, entonces exactamente esos ancestros atravesados ​​corresponden a ciclos.Luego itera a través de n2 hasta llegar a commonAncestor (rápido).El tiempo debería depender del número de aristas cíclicas, combinado con la búsqueda en listas (probablemente O(logN) pero barato).No es necesario volver a explorar el gráfico y no es posible retroceder.

Answer 2

Después de construir un árbol de expansión, itere en cada borde (A, B) que no esté en el árbol y encuentre el Ancestro común más bajo (LCA) para los nodos de este borde, su ciclo sería la ruta desde A - & Gt; LCA - & Gt; B - & Gt; A

puedes usar este enlace: http: //www.topcoder .com / tc? module = Static & amp; d1 = tutoriales & amp; d2 = lowerCommonAncestor     para la implementación eficiente del algoritmo del ancestro común más bajo.