Dado um Spanning Tree e uma borda Não no Spanning Tree, Como para formar uma base Ciclo?

Question

Eu tenho um gráfico com E Edge e Vertex V, posso encontrar o Spanning Tree usando Kruskal algoritmo (ou qualquer outra travessia-backtrack-travessia de novo tipo de algoritmos), agora eu quero encontrar todas as bases de ciclo que são criados por utilitizing que spanning tree e as arestas que não estão na árvore, qualquer algoritmo que me permite fazer isso, além de busca de força bruta?

eu posso, é claro, começa a partir de um vértice da borda árvore não abrangendo, recebe todas as arestas, explorar todos eles, retrai, se eu encontrar beco sem saída, até que eu volte para o outro vértice da borda. Mas isso é um pouco, err ... brutal. Quaisquer outras ideias?

Answer 1

Um algoritmo simples que usamos para encontrar ciclos em gráficos:

Criar uma árvore geradora em profundidade onde cada nodo tem um pai. Em percorrer a árvore criar um registro de nós usados. Quando uma aresta aponta para um nó utilizado anteriormente, armazená-lo como um borda cíclico. Quando a árvore de expansão estiver concluída, a contagem do cíclica bordas dá a contagem de ciclos. Para cada recursivo borda cíclico através dos antepassados ??dos dois nós até um antepassado comum é encontrado. Este dará exatamente os ciclos.

Pode ser útil ter um índice (tabela de dispersão) de todos os antepassados ??de um nó de borda cíclica de modo que é rápido para encontrar o antepassado comum.

Eu duvido que este é o melhor algoritmo, mas é bastante rápido.

Editar em repsonse ao comentário Cada nó na árvore de expansão tem um pai. Quando um nó numa extremidade cíclico é alcançado que calcula a sua lista de lista antepassados ??(List<Node>This podia ser indexado para a velocidade (ou seja, contém () é < O(n)). Quando uma borda cíclica com dois nós (n1, n2) encontra-se então percorrer os antepassados ??de n1, n1.ancestorList ( rapidamente desde que a lista já foi criada) e teste se o antepassado é de n2.ancestorList. Se ele (commonAncestor) é, em seguida, exatamente esses ancestrais atravessaram correspondem a ciclos. então iterate através n2 até chegar commonAncestor (rápida). o tempo deve depender sobre o número de arestas cíclicos, combinado com a pesquisa em listas (provavelmente O(logN) mas barato). não há necessidade de re-explorar o gráfico e não há retrocesso.

Answer 2

Depois de construir árvore de expansão, iterate em cada extremidade (A, B) que não está na árvore e encontrar mais baixas ancestral comum (LCA) para os nós desta vantagem, seu ciclo seria caminho a partir A -> LCA -> B -> A

Você pode usar este link: http://www.topcoder.com/tc?module=Static&d1 = tutoriais & d2 = lowestCommonAncestor para a implementação eficiente algoritmo mais baixo ancestral comum.