Melhor algoritmo para testar se uma lista ligada tem um ciclo de

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

Pergunta

Qual é a melhor (interrompendo) algoritmo para determinar se uma lista ligada tem um ciclo em que?

[Editar] Análise de assintótico complexidade de tempo e espaço seria doce por isso, as respostas podem ser comparados melhor.

[Editar] questão não era de endereçamento de nós com outdegree > 1, mas há alguma conversa sobre isso.Essa pergunta é mais ao longo das linhas de "Melhor algoritmo para detectar ciclos em um gráfico direcionado".

Foi útil?

Solução

Temos dois ponteiros iteração a lista;fazer um iterar através de duas vezes a velocidade dos outros, e comparar suas posições em cada etapa.Em cima da minha cabeça, algo como:

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), que é tão boa como você pode começar.

Outras dicas

Pré-requisito:Controlar o tamanho da lista (atualizar o tamanho whenenver um nó é adicionado ou excluído).

A detecção de Loop:

  1. Manter um contador quando percorrer a lista tamanho.

  2. Se o contador exceder o tamanho da lista, existe um possível ciclo.

Complexidade:O(n)

Nota:a comparação entre o contador e o tamanho da lista, bem como a operação de atualização do tamanho da lista, deve ser feita thread-safe.

Tomar 2 ponteiro *p e *q , começar a percorrer a lista ligada "LL" usando ponteiros :

1) ponteiro p excluirá nó anterior ao nó de cada vez, e a apontar para o próximo nó.

2) ponteiro q vai de cada vez na direção de avanço de direção apenas.

condições:

1) ponteiro p está a apontar para null e p está a apontar para algum nó :Loop

2) ambos ponteiro apontando para null:nenhum loop existe

Que tal usar uma tabela de hash para armazenar o já visto nós (você olhar para eles de ordem a partir do início da lista)?Na prática, você poderia conseguir algo perto de O(N).

De outra forma, usando um classificados de pilha, em vez de uma tabela de hash iria atingir O(N log(N)).

Gostaria de saber se há alguma outra forma que não apenas vai iterativamente - preencher uma matriz como você passo a frente e verifique se o nó atual é já presente na matriz...

Konrad Rudolph algoritmo não funciona se o ciclo não está apontando para o início.A lista a seguir irá torná-lo um loop infinito:1->2->3->2.

DrPizza do algoritmo é definitivamente o caminho a percorrer.

Neste caso OysterD código vai ser a solução mais rápida (vértice colorir)

O que realmente me surpreende.A minha solução faz no máximo, a dois, passa através da lista (se o último nó é ligado a penúltima lode), e no caso comum (nenhum loop) vai fazer apenas uma passagem.Sem hash, nenhuma alocação de memória, etc.

Neste caso OysterD código vai ser a solução mais rápida (vértice colorir)

O que realmente me surpreende.A minha solução faz no máximo, a dois, passa através da lista (se o último nó é ligado a penúltima lode), e no caso comum (nenhum loop) vai fazer apenas uma passagem.Sem hash, nenhuma alocação de memória, etc.

Sim.Tenho notado que a formulação não era perfeita e ter reformulada-lo.Eu ainda acredito que um inteligente sistema de hash pode executar mais rápido – por um fio de cabelo.Acredito que o algoritmo de é a melhor solução, no entanto.

Apenas para salientar o meu ponto de vista:o vertec a coloração é utilizado para detectar ciclos nas dependências modernos coletores de lixo, logo existe um real caso de uso para ele.Eles, principalmente, usar sinalizadores de bit para realizar a coloração.

Você terá que visitar cada nó para determinar isso.Isso pode ser feito de forma recursiva.Para impedi-lo de visitar já visitou nós, você precisa de uma bandeira para dizer "já visitado".É claro que isso não dará loops.Assim, em vez de um sinalizador de bits, use um número.Inicia em 1.Verifique conectados nós e, em seguida, marcam-como 2 e recursivamente até que a rede é coberto.Se quando a verificação de nós encontrar um nó que é mais do que um a menos que o nó atual, então você tem um ciclo.A duração do ciclo é dado pela diferença.

Dois ponteiros são inicializados na cabeça da lista.Um ponteiro encaminha uma vez em cada etapa, e os outros atacantes duas vezes em cada passo.Se o mais rápido do ponteiro atende a um mais lento, novamente, não é um loop na lista.Caso contrário, não há loop se o mais rápido atinge o fim da lista.

O código de exemplo abaixo é implementado de acordo com esta solução.O mais rápido do ponteiro é pFast, e o mais 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;
}

Esta solução está disponível em meu blog.Há um problema mais discutido no blog:O que é o nó de entrada quando houver ciclo/loop em uma lista?

"Hack" solução (deve funcionar em C/C++):

  • Percorrer a lista e defina o último bit de next ponteiro para 1.
  • Se encontrar um elemento com sinalizado ponteiro -- retorna verdadeiro e o primeiro elemento do ciclo.
  • Antes de retornar, repor os ponteiros de volta, embora eu acredito que a referência vai funcionar mesmo com sinalizado ponteiros.

Tempo de complexidade é 2n.Parece que ele não usa qualquer temporais variáveis.

Esta é uma solução usando uma tabela de Hash ( apenas uma lista, na verdade) para salvar o endereço de ponteiro. 

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

def has_cycle(cabeça):contador = set()

while head is not None:
    if head in counter:
        return True
    else:
        counter.add(head)
        head = head.next
Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top