DFS (Depth First Traversal) na estrutura de dados: o que é, pedidos e aplicativos

Significado de DFS na Estrutura de Dados

DFS em Estrutura de Dados, também conhecido como travessia em profundidade, é um algoritmo recursivo usado principalmente para pesquisar todos os vértices de um gráfico ou estrutura de dados em árvore. Traversal é a visita de cada nó de um grafo. O algoritmo começa a partir do nó raiz (que pode ser um nó arbitrário como o nó raiz em um grafo) e vai o mais longe possível ao longo de cada ramo antes de retroceder.

A ideia é começar da raiz ou nó arbitrário e manter o nó marcado. Depois disso, você precisa mover para o nó adjacente que está desmarcado e continuar esse loop até que não haja nenhum nó adjacente desmarcado. Em seguida, retroceda e examine os outros nós que não estão marcados e os percorra. A etapa final é imprimir os nós dentro do caminho.

Algoritmo

Formule uma função recursiva que pegará o índice do nó e um array visitado.

1. Mantenha o nó atual marcado como visitado e imprima-o.
2. Percorra todas as notas adjacentes e as não marcadas e chame a função recursiva com o índice do nó adjacente.

Explore nossos cursos populares de engenharia de software

Propriedades

A análise de tempo e espaço no DFS em Estrutura de Dados varia de acordo com sua área de aplicação. Teoricamente, DFS é usado principalmente para cruzar um grafo completo e leva tempo O(|V|+|E|) onde |V| representa o número de vértices e |E| representa o número de arestas. Este gráfico é linear.

Nessas aplicações, o espaço O(|V|) também é usado como último recurso para manter a pilha de vértices armazenada no caminho de busca e o conjunto de vértices já visitados. Portanto, a configuração dos limites de tempo e espaço é semelhante à busca em largura. Aqui, os dois algoritmos utilizados são menos dependentes de sua complexidade e mais das várias características das ordens de vértices produzidas pelos dois algoritmos.

Quando se trata de aplicações de DFS em Estrutura de Dados relacionadas a domínios específicos, como encontrar soluções em web-crawling ou AI, o gráfico que requer a travessia pode ser muito substancial para ser visitado em sua totalidade. Nesses casos, a busca é executada apenas em uma profundidade restrita; devido a recursos finitos, como espaço em disco ou memória. As estruturas de dados normalmente não são usadas para rastrear o conjunto de todos os vértices visitados anteriormente. Uma busca realizada a uma profundidade restrita ainda torna o tempo linear quando se trata da unidade de arestas e vértices expandidos.

No entanto, lembre-se que este número não tem o mesmo tamanho que todo o grafo, pois alguns dos vértices podem ser pesquisados ​​várias vezes e outros não pesquisados.

Nesses casos, o DFS também recorre a métodos heurísticos para selecionar uma ramificação mais promissora. Finalmente, quando o limite de profundidade apropriado não pode ser determinado, o DFS de aprofundamento iterativo a priori é aplicado repetidamente por meio de uma sequência de limites crescentes.

Aprenda cursos de desenvolvimento de software online das melhores universidades do mundo. Ganhe Programas PG Executivos, Programas de Certificado Avançado ou Programas de Mestrado para acelerar sua carreira.

Algoritmo de primeira pesquisa de profundidade

Cada vértice de um gráfico em uma implementação DFS padrão é dividido em duas categorias:

1. Não visitado
2. Visitou

O algoritmo é usado para identificar cada vértice e marcá-los como visitados e ao mesmo tempo evitar ciclos.

É assim que o algoritmo DFS funciona:

1. Coloque qualquer vértice particular do gráfico em uma pilha.
2. O item no topo da pilha deve ser adicionado à lista visitada.
3. Faça uma lista de nós adjacentes desse vértice e adicione aqueles que não estão na lista visitada no topo da pilha.
4. Continue repetindo as etapas anteriores até que a pilha se esvazie.

Pedido de DFS

Ordens de vértices: Existem quatro maneiras de ordenar linearmente os vértices de um grafo ou árvore no DFS:

1. A lista de vértices organizados como foram visitados primeiro pelo algoritmo DFS é conhecida como pré-ordenação. É uma maneira concisa de descrever o progresso da pesquisa.
2. A lista dos vértices na ordem em que foram visitados por último pelo algoritmo é conhecida como pós-ordenação.
3. A lista dos vértices na ordem oposta à sua primeira visita é uma pré-ordenação reversa. Portanto, não deve ser confundido com pós-encomenda.
4. A lista dos vértices na ordem oposta à sua última visita é uma pós-ordenação reversa. Não deve ser confundido com pré-encomenda.

Além disso, há ordenação inversa e ordem reversa para árvores binárias.

Pesquisa em profundidade ou DFS para um gráfico

O DFS para um gráfico é quase o mesmo que o DFS para uma árvore. A única diferença é que os grafos podem ter ciclos, ao contrário das árvores. Um nó pode ser visitado várias vezes e para evitar o processamento do nó, uma matriz booleana visitada é usada.

Saída de uma primeira pesquisa de profundidade

A busca em profundidade é mais facilmente representada em termos de uma árvore geradora dos vértices que já foram alcançados na busca. Com base nesta árvore geradora, as arestas do grafo original são divididas em três classes: as arestas frontais onde o nó da árvore é apontado para um de seus descendentes, as arestas posteriores onde o nó é apontado para um de seus ancestrais e as arestas cruzadas , que não faz nenhuma das funções anteriores.

Aplicações da primeira travessia de profundidade (DFS)

A pesquisa em profundidade é usada nos seguintes algoritmos como um bloco de construção:

• Procurando por componentes que estão conectados.
• Encontrando componentes conectados por 2 (vértices ou arestas).
• Encontrando as pontes do gráfico.
• Encontrando componentes conectados por 3 (vértices ou arestas).
• Classificação topológica.
• Encontrar componentes fortemente conectados.
• Descobrir se uma espécie é semelhante a uma ou outra espécie em uma árvore filogenética.
• Teste de planaridade.
• Produzindo palavras para determinar o conjunto limite de qualquer grupo.
• Resolvendo quebra-cabeças que têm apenas uma solução, como labirintos.
• Geração do labirinto .
• Procurando por bi-conectividade em grafos.

Pseudocódigo DFS e Implementação em Python

A função init() é executada em cada nó no pseudocódigo abaixo para garantir que todos os vértices sejam visitados. Isso é especialmente importante, pois os gráficos podem ter várias áreas desconectadas.

Segue o pseudocódigo:

DFS(G, u)

u.visitou = true

para cada v ∈ G.Adj[u]

if v.visitou == false

DFS(G,v)

iniciar() {

Para cada u ∈ G

u.visitou = false

Para cada u ∈ G

DFS(G, u)

}

Aqui está a implementação do DFS em Python:

gráfico = {

'5' : ['3','7'],

'2': ['1', '3'],

'6' : ['7'],

'3': [],

'4': ['6'],

'7': []

}

visitado = set()

def dfs(visitado, gráfico, nó):

se o nó não for visitado:

imprimir (nó)

visitou.add(nó)

para vizinho em graph[node]:

dfs(visitado, gráfico, vizinho)

print(“Este é o DFS:”)

dfs(visitado, gráfico, '5')

Resultado:

Este é o DFS: 5

Explore nossos cursos populares de engenharia de software

A complexidade da pesquisa em profundidade

John Reif explorou a complexidade computacional do Depth First Search. Para ser preciso, em um grafo, o fato dado é G, seja O a ordem padrão determinada pelo algoritmo DFS repetitivo. G representa o gráfico e O representa a saída de ordenação do algoritmo DFS redundante. Essa saída é conhecida como ordenação lexicográfica DFS.

Conclusão

O principal objetivo do algoritmo DFS é visitar cada vértice que evita ciclos nos grafos alvo. Se você deseja se envolver com implementações avançadas de operações de pesquisa ou operações de pedidos, você deve definitivamente considerar seguir um curso premium e holístico em Pesquisa em profundidade e estrutura de dados.

O upGrad possui alguns cursos DFS de primeira linha, como Master of Science in Computer Science e Specialization in Big Data .

Se você está se esforçando para dar o próximo passo e procurando por alguns conselhos de especialistas, o upGrad Mentorship procura fornecer sessões individuais com os melhores conselheiros de carreira e especialistas do setor.