Algoritmo de varredura profunda

O algoritmo de pesquisa em profundidade (ou pesquisa em profundidade , ou DFS , para pesquisa em profundidade ) é um algoritmo para navegar em uma árvore e, mais geralmente, para navegar em um gráfico . Ele naturalmente se descreve recursivamente . Sua aplicação mais simples é determinar se existe um caminho de um vértice para outro.

História

Para gráficos não orientados , a varredura de profundidade corresponde ao método intuitivo usado para encontrar a saída de um labirinto sem andar em círculos. Profundos algoritmos de rota são formulados a partir do XIX °  século. Édouard Lucas (1891) em suas Recreações matemáticas propõe uma solução rigorosa, ideia que atribui a Charles Pierre Trémaux. Gaston Tarry apresenta outra solução.

Princípio

Explorar um curso profundo de um vértice S funciona da seguinte maneira. Em seguida, segue um caminho no gráfico até chegar a um beco sem saída ou até chegar a um cume já visitado. Ele então retorna ao último cume onde poderíamos seguir outro caminho e então explora outro caminho (veja o vídeo ao lado). A exploração para quando todos os vértices desde S forem visitados. Em suma, a exploração progride a partir de um vértice S chamando-se recursivamente para cada vértice vizinho de S.

O nome Deep Algorithm é devido ao fato de que, ao contrário do algoritmo de travessia de largura , ele realmente explora os caminhos um por um "completamente": para cada vértice, ele marca o vértice atual e leva o primeiro vértice vizinho até que um vértice tenha não há mais vizinhos (ou todos os seus vizinhos estão marcados) e, em seguida, retorna ao vértice pai.

Se G não fosse uma árvore , o algoritmo poderia a priori rodar indefinidamente se continuássemos a exploração a partir de um vértice já visitado. Para evitar isso, marcamos os picos que visitamos, para não os explorar novamente.

No caso de uma árvore, o caminho de profundidade é usado para caracterizar a árvore .

Implementação recursiva

Durante a exploração, marcamos os picos a fim de evitar atravessar novamente os picos percorridos. Inicialmente, nenhum vértice é marcado.

explorer(graphe G, sommet s) marquer le sommet s afficher(s) pour tout sommet t voisin du sommet s si t n'est pas marqué alors explorer(G, t);

O caminho em profundidade de um gráfico G é então:

parcoursProfondeur(graphe G) pour tout sommet s du graphe G si s n'est pas marqué alors explorer(G, s)

Observe que é possível implementá-lo iterativamente usando uma pilha LIFO contendo os vértices a serem explorados: um vértice é desempilhado e seus vizinhos ainda não explorados são empilhados.

Exemplo

Vejamos concretamente o funcionamento da rota em profundidade a partir do vértice A no gráfico a seguir:

Graph.traversal.example.svg

Concordaremos que os vértices à esquerda neste gráfico serão escolhidos antes daqueles à direita. Se o algoritmo usar efetivamente uma marcação dos vértices para evitar girar indefinidamente em um loop, teremos a seguinte ordem de visita: A, B, D, F, E, C, G.

Suponha agora que não utilizamos o método de marcação, teríamos então a visita dos seguintes vértices na ordem: A, B, D, F, E, A, B, D, F, E, etc. indefinidamente, uma vez que o algoritmo não pode sair do loop A, B, D, F, E e, portanto, nunca alcançará C ou G.

Formulários

Como os outros algoritmos de travessia de grafos , o algoritmo de travessia em profundidade encontra o conjunto de vértices acessíveis a partir de um dado vértice s , ou seja, aqueles para os quais existe um caminho a partir de s . Esses são precisamente os vértices marcados pelo algoritmo. Isso se aplica a um gráfico direcionado ou não direcionado. Em um gráfico não direcionado, podemos usar esta propriedade para o cálculo de componentes conectados .

No caso de um gráfico direcionado acíclico , a varredura de profundidade permite calcular uma classificação topológica dos vértices.

O algoritmo Kosaraju executa uma profundidade dupla - para calcular os componentes fortemente associados a qualquer gráfico direcionado.

Complexidade

A complexidade do caminho é onde está o número de vértices e o número de arcos. Em 1985, John Reif definiu um problema de decisão associado à travessia profunda e mostrou que é P-completo. Este problema de decisão é o seguinte: dado um gráfico G e dois vértices uev, decida se u aparece antes de v no passeio em profundidade que explora os vértices em ordem lexicográfica. Isso significa que o curso profundo é difícil de comparar. No entanto, a travessia em profundidade (mas não com uma ordem lexicográfica) é paralelizável em uma máquina probabilística e está na classe RNC. Em 1997, Karger et al. afirma que o problema de saber se o caminho pode ser paralelizável em uma máquina determinística está aberto.

Notas e referências

  1. Edward Lucas, mathematics Recreations ( 2 th ed.), A. Blanchard (Paris), 1891, pp. 47-55, [1] . Acesso direto à página: [2] .
  2. “Entre as várias soluções deste curioso problema de geometria situacional, que acabamos de enunciar, escolheremos, como a mais simples e elegante, aquela que nos foi gentilmente comunicada por M. Trémaux, ex-aluno do Politécnico Escola, engenheiro de telégrafos; mas modificamos ligeiramente a demonstração. » Em Recriações matemáticas , página 47.
  3. Gaston Tarry, "O problema dos labirintos", Nouvelles annales de mathematique , jornal des candidate aux écoles polytechnique et normale , Sér. 3, 14, 1895, p. 187-190 [3] "Cópia arquivada" (versão de 9 de fevereiro de 2015 no Internet Archive ) .
  4. (en) S. Dasgupta, CH Papadimitriou e UV Vazirani, Algoritmos
  5. John H. Reif , “A  pesquisa em primeiro lugar é inerentemente sequencial,  ” Information Processing Letters , vol.  20, n o  5,1985( DOI  10.1016 / 0020-0190 (85) 90024-9 )
  6. Kurt Mehlhorn e Peter Sanders , Algorithms and Data Structures: The Basic Toolbox , Springer,2008( leia online )
  7. (em) A. Aggarwal e RJ Anderson , "  A random 1-011-011-01algorithm for depth first search  " , combinatorica , vol.  8, n o  1,1 r março 1988, p.  1–12 ( ISSN  1439-6912 , DOI  10.1007 / BF02122548 , ler online , acessado em 27 de setembro de 2019 )
  8. D. Karger e R. Motwani , “  An $ \ NC $ Algorithm for Minimum Cuts  ”, SIAM Journal on Computing , vol.  26, n o  1,1 st fevereiro 1997, p.  255-272 ( ISSN  0097-5397 , DOI  10.1137 / S0097539794273083 , ler online , acessado em 27 de setembro de 2019 )

Veja também

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">