Complexidade do tempo do DFS

DFS significa pesquisa em profundidade. Refere -se a como os nós de uma árvore são visitados até que o nó desejado esteja localizado. Por simplicidade, todos os nós deste artigo devem ser visitados. A idéia é ver todos os nós, com cada nó visitado uma vez. Um nó também é chamado de vértice. Primeira pesquisa em profundidade pode estar em um dos três pedidos: pré-encomenda, em ordem ou pós-ordem. A travessia de pré-encomenda é usada neste artigo. Este artigo usa a seguinte árvore é usada para ilustrar a pré-venda para a primeira pesquisa:

Um galho na árvore é chamado de vantagem. Este artigo tem como objetivo ilustrar o que é conhecido como complexidade do tempo para a primeira pesquisa de profundidade. O DFS é explicado brevemente. C ++ é usado para ilustração de código.

Travessal de pré-encomenda para busca de profundidade primeiro

O algoritmo é o seguinte:

1) Visite o vértice atual.
2) Travesse a sub-árvore esquerda do vértice atual de maneira recursiva.
3) Travesse a sub-árvore direita do vértice atual de maneira recursiva.

Para a árvore anterior, o primeiro vértice a ser visitado é um. Este é o vértice atual. Atravessando recursivamente a sub-árvore esquerda e, em seguida, a sub-árvore direita significa visita B enquanto a visita de C é registrada na memória para ser visitada posteriormente.

Em B, B é o vértice atual. Atravessando recursivamente a sub-árvore esquerda e, em seguida, a sub-árvore direita significa visitar e enquanto a visita de f é registrada na memória para ser visitada posteriormente.

Em e, e é o vértice atual. E não tem sub-árvore esquerda ou direita (sem bordas). A última gravação em memória para visitar foi a sub-árvore certa (Edge) para B. O sub-árvore direito para B consiste em F precedido por sua borda. Neste ponto, F é visitado.

A gravação anterior em memória para visitar agora é a sub-árvore certa (Edge) para um. O sub-árvore direito para um gravado consiste em C, seguido de suas bordas e crianças. Neste ponto, C é visitado. C tem três arestas. De acordo com o algoritmo, a borda esquerda é acessada primeiro.

Quando a borda esquerda é acessada, G é visitado. Não há filho para G. Pelo algoritmo, H compartilha o mesmo pai com g e, como está à direita de G, é visitado a seguir.

"Eu" está à direita de H e compartilha o mesmo pai com H. Pelo algoritmo, qualquer nó à direita de outro nó deve ser visitado depois que o nó foi visitado. Não importa se o nó acabou de visitar está à direita de outro nó. Então "eu" é visitado a seguir.

Não há nó à direita de "eu". C e todos os seus descendentes foram visitados. No entanto, observe que há um nó à direita de C. Este nó é D. Pelo algoritmo, qualquer nó à direita de outro nó deve ser visitado após o nó (visitado). Não importa se o nó visitado estava à direita de algum outro nó. Então D é visitado a seguir.

D tem dois filhos, J e K. J está à esquerda de k. J é visitado primeiro antes de k.

O algoritmo de pesquisa em profundidade pode ser resumido da seguinte. Do vértice mais baixo da esquerda, visite os irmãos certos daquele vértice e depois suba a árvore, para a direita e descendo de tempos em tempos adequadamente.

Com isso, a sequência do DFS da árvore anterior é: a, b, e, f, c, g, h, i, d, j, k.

Complexidade do tempo

A árvore anterior tem 11 vértices e 10 arestas. Se a árvore estiver bem armazenada, a varredura de toda a árvore envolverá 11 vértices e 10 arestas. Esta é uma apreciação da velocidade de operação da pesquisa em profundidade. É complexidade do tempo. Está escrito como:

O (| v |+| e |)

Onde | v | é o número de vértices (nós) e | e | é o número de bordas. Para esta árvore, o total é 21 = 11 + 10. O "O" tem que estar lá.

Estrutura para a árvore

A organização das árvores pode ser descrita da seguinte forma:

Vértice A: Filhos: B, C, D
Vertex B: Filhos: E, F
Vértice c: filhos: g, h, eu
Vertex D: Filhos: J, K
Vértice e
Vértice f
Vértice g
Vértice h
Vértice i
Vértice j
Vértice k

A árvore anterior será armazenada em um não -ordenado de vetores. Um vértice é uma chave, e as crianças são os valores do vetor da chave. Vértices de E para K não têm filhos.

Codificação C ++

O programa pode começar com o seguinte título:

#incluir
#incluir
#incluir
usando namespace std;

C ++ codificando para os não-ordenados

O UNODERED_MAP-OF-VECTORS é criado com o seguinte código:

UNODERED_MAP > umv = 'a', 'b', 'c', 'd',
'B', 'e', 'f',
'C', 'g', 'h', 'i',
'D', 'j', 'k',
'E', ,
'F', ,
'G', ,
'H', ,
'EU', ,
'J', ,
'K', ;

Isso pode ser colocado logo abaixo do título anterior.

A função de profundidade primeiro

É uma função recursiva que imprime cada vértice (nó) visitado. Isso é:

Void DepthfirstSearch (Char Parent)
cout << parent << "; //print vertex
para (int i = 0; idepthfirstSearch (umv [pai] [i]);

Depois de imprimir o vértice esquerdo, o loop for imprimido os vértices direito. O loop for o recall.

Função principal C ++

Uma função principal adequada para o programa é:

int main (int argc, char ** argv)

depthfirstSearch ('a');
cout << endl;
retornar 0;

O algoritmo para pesquisa de profundidade é o seguinte:

1) Visite o vértice atual.
2) Travesse a sub-árvore esquerda do vértice atual de maneira recursiva.
3) Travesse a sub-árvore direita do vértice atual de maneira recursiva.

Isso pode ser interpretado da seguinte. Do vértice mais baixo da esquerda, visite os irmãos certos daquele vértice e suba a árvore recursivamente, para a direita, descendo de tempos em tempos, adequadamente.

A complexidade do tempo para o algoritmo de pesquisa de profundidade é:

O (| v |+| e |)

Conclusão

DFS significa pesquisa em profundidade. Refere -se a como os nós de uma árvore são visitados até que o nó desejado esteja localizado. Por simplicidade, todos os nós da árvore deste artigo foram visitados. A idéia é visitar todos os nós, com cada nó visitado uma vez. Um nó também é chamado de vértice. Primeira pesquisa em profundidade pode estar em um dos três pedidos: pré-encomenda, em ordem ou pós-ordem. Neste artigo, a travessal de pré-encomenda foi usada.