Miglior algoritmo per verificare se un elenco collegato ha un ciclo

StackOverflow https://stackoverflow.com/questions/34249

Domanda

Qual è il migliore algoritmo (di arresto) per determinare se un elenco collegato contiene un ciclo?

[Modifica] L'analisi della complessità asintotica sia per il tempo che per lo spazio sarebbe dolce, quindi le risposte possono essere confrontate meglio.

[Modifica] La domanda originale non riguardava i nodi con grado superiore a 1, ma se ne parla.Questa domanda è più sulla falsariga di "Il miglior algoritmo per rilevare i cicli in un grafico diretto".

È stato utile?

Soluzione

Avere due puntatori che iterano attraverso l'elenco;fai in modo che uno ripeta al doppio della velocità dell'altro e confronta le loro posizioni ad ogni passaggio.In cima alla mia testa, qualcosa del tipo:

node* tortoise(begin), * hare(begin);
while(hare = hare->next)
{
    if(hare == tortoise) { throw std::logic_error("There's a cycle"); }
    hare = hare->next;
    if(hare == tortoise) { throw std::logic_error("There's a cycle"); }
    tortoise = tortoise->next;
}

O(n), che è il massimo che puoi ottenere.

Altri suggerimenti

Precondizione:Tieni traccia della dimensione dell'elenco (aggiorna la dimensione ogni volta che un nodo viene aggiunto o eliminato).

Rilevamento del circuito:

  1. Mantieni un contatore quando attraversi la dimensione dell'elenco.

  2. Se il contatore supera la dimensione dell'elenco, è possibile un ciclo.

Complessità:SU)

Nota:il confronto tra il contatore e la dimensione della lista, così come l'operazione di aggiornamento della dimensione della lista, deve essere reso thread-safe.

Prendi 2 puntatori *p e *q , inizia ad attraversare l'elenco collegato "LL" utilizzando entrambi i puntatori:

1) il puntatore p eliminerà ogni volta il nodo precedente e punterà al nodo successivo.

2) Il puntatore q andrà ogni volta solo in direzione avanti.

condizioni:

1) il puntatore p punta a null e q punta a qualche nodo:Il ciclo è presente

2) entrambi i puntatori puntano a null:non c'è nessun ciclo

Che ne dici di usare una tabella hash per memorizzare i nodi già visti (li guardi in ordine dall'inizio dell'elenco)?In pratica, potresti ottenere qualcosa di vicino a O(N).

Altrimenti, l'utilizzo di un heap ordinato anziché di una tabella hash otterrebbe O(N log(N)).

Mi chiedo se ci sia un altro modo oltre a procedere semplicemente in modo iterativo: popolare un array mentre si avanza e controllare se il nodo corrente è già presente nell'array...

L'algoritmo di Konrad Rudolph non funzionerà se il ciclo non punta all'inizio.Il seguente elenco lo renderà un ciclo infinito:1->2->3->2.

L'algoritmo di DrPizza è sicuramente la strada da percorrere.

In questo caso il codice di OysterD sarà la soluzione più veloce (colorazione dei vertici)

Mi sorprenderebbe davvero.La mia soluzione effettua al massimo due passaggi attraverso l'elenco (se l'ultimo nodo è collegato al penultimo filo) e nel caso comune (nessun ciclo) effettuerà un solo passaggio.Senza hashing, nessuna allocazione di memoria, ecc.

In questo caso il codice di OysterD sarà la soluzione più veloce (colorazione dei vertici)

Mi sorprenderebbe davvero.La mia soluzione effettua al massimo due passaggi attraverso l'elenco (se l'ultimo nodo è collegato al penultimo filo) e nel caso comune (nessun ciclo) effettuerà un solo passaggio.Senza hashing, nessuna allocazione di memoria, ecc.

SÌ.Ho notato che la formulazione non era perfetta e l'ho riformulata.Sono ancora convinto che un hashing intelligente potrebbe funzionare più velocemente, per un pelo.Credo al tuo algoritmo È la soluzione migliore, però.

Giusto per sottolineare il mio punto:la colorazione dei vertici viene utilizzata per rilevare i cicli nelle dipendenze dai moderni garbage collector, quindi esiste un caso d'uso molto reale per questo.Utilizzano principalmente bit flag per eseguire la colorazione.

Dovrai visitare ogni nodo per determinarlo.Questo può essere fatto in modo ricorsivo.Per impedirti di visitare i nodi già visitati, hai bisogno di un flag per dire "già visitato".Questo ovviamente non ti dà loop.Quindi invece di un bit flag, usa un numero.Inizia alle 1.Controllare i nodi connessi, quindi contrassegnarli come 2 e ripetere finché la rete non è coperta.Se quando controlli i nodi incontri un nodo che è più di uno in meno rispetto al nodo corrente, allora hai un ciclo.La durata del ciclo è data dalla differenza.

Due puntatori vengono inizializzati all'inizio dell'elenco.Un puntatore avanza una volta ad ogni passo e l'altro avanza due volte ad ogni passo.Se il puntatore più veloce incontra nuovamente quello più lento, si verifica un ciclo nell'elenco.Altrimenti non c'è ciclo se quello più veloce raggiunge la fine dell'elenco.

Il codice di esempio riportato di seguito viene implementato in base a questa soluzione.Il puntatore più veloce è pFast e quello più lento è pSlow.

bool HasLoop(ListNode* pHead)
{
    if(pHead == NULL)
        return false;


    ListNode* pSlow = pHead->m_pNext;
    if(pSlow == NULL)
        return false;


    ListNode* pFast = pSlow->m_pNext;
    while(pFast != NULL && pSlow != NULL)
    {
        if(pFast == pSlow)
            return true;


        pSlow = pSlow->m_pNext;


        pFast = pFast->m_pNext;
        if(pFast != NULL)
            pFast = pFast->m_pNext;
    }


    return false;
}

Questa soluzione è disponibile su il mio blog.C'è un altro problema discusso nel blog:Qual è il nodo di ingresso quando è presente un ciclo/loop in un elenco?

Soluzione "Hack" (dovrebbe funzionare in C/C++):

  • Attraversa l'elenco e imposta l'ultimo bit di next puntatore a 1.
  • Se trova un elemento con puntatore contrassegnato, restituisce vero e il primo elemento del ciclo.
  • Prima di tornare, reimposta i puntatori, anche se credo che il dereferenziamento funzionerà anche con i puntatori contrassegnati.

La complessità temporale è 2n.Sembra che non utilizzi variabili temporali.

Questa è una soluzione che utilizza una tabella Hash (solo un elenco in realtà) per salvare l'indirizzo del puntatore. 

def hash_cycle(node):
    hashl=[]
    while(node):
        if node in hashl:
            return True
        else:
            hashl.append(node)
            node=node.next
    return False

def ciclo_ha(testa):contatore = imposta()

while head is not None:
    if head in counter:
        return True
    else:
        counter.add(head)
        head = head.next
Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top