Trova tutte le basi del ciclo in un grafico, con le coordinate del vertice fornite

Question

Una domanda simile is posted here.

Ho un grafico non orientato con Vertex V e Edge E. Sto cercando un algoritmo per identificare tutte le basi del ciclo in quel grafico. Un esempio di tale grafico è mostrato sotto:

Ora, tutte le coordinate dei vertici sono noto (differenza precedente domanda, e contraria alla spiegazione nel diagramma sopra) , quindi è possibile trovare i cicli più piccoli che racchiudono l'intero grafico.

In questo grafico, è possibile che ci siano bordi che non formano alcun ciclo.

Qual è il miglior algoritmo per farlo?

Ecco un altro esempio che si può dare un'occhiata a:

Supponendo che e1 è il bordo che viene raccolto prima, e la freccia indica la direzione del bordo.

Answer 1

Non ho provato questo ed è piuttosto avido, ma dovrebbe funzionare:

1. Scegli un nodo
2. andare in uno Si trova ad vicini
3. andare avanti fino a tornare al nodo di partenza , ma non ti è permesso visitare un vecchio nodo.
4. Se si ottiene un ciclo, salvarlo se non esiste già o un sottoinsieme di quei nodi costituisce un ciclo. Se il nodo nel ciclo è un sottoinsieme dei nodi in un altro ciclo, rimuovere il ciclo più grande (o forse dividerlo in due?)
5. Ricominciare da capo a 2 con un nuovo vicino.
6. Ricominciare da 1 con un nuovo nodo.

Commenti: A 3 si dovrebbe ovviamente fare la stessa cosa del punto 2, quindi prendere tutti i percorsi possibili.

Forse è un inizio? Come ho detto, non l'ho provato, quindi non è ottimizzato.

MODIFICA: Una versione non documentata e non ottimizzata di un'implementazione dell'algoritmo può essere trovata qui: https://gist.github.com/750015. Ma, non risolve completamente la soluzione poiché può solo riconoscere i "veri" sottoinsiemi.