Conteúdo principal
Análise da busca em largura
Quanto tempo a busca em largura leva para um gráfico de vértice definido como e borda definida como ? A resposta é de tempo.
Vamos ver o que de tempo significa. Assuma que , que é o caso para a maioria dos gráficos especialmente os que vamos executar a busca em largura. Então . Porque nós ignoramos fatores constantes na notação assintótica, vemos que quando , significa realmente . Se, no entanto, nós temos , então , e então realmente significa . Nós podemos colocar os dois casos juntos dizendo que realmente significa . Em geral, se nós temos parâmetros e , então realmente significa .
(A propósito, note que um gráfico é ligado se há um caminho que conecta todos os vértices. O número mínimo de arestas que um gráfico pode ter e ainda estar ligado é . Um gráfico no qual é chamado de árvore sem raiz.)
Como essa busca em largura é executada ? Ela demora de tempo para iniciar a distância e o prdecessor para cada vértice ( de tempo, na verdade). Cada vértice é visitado no máximo uma vez, porque só na primeira vez que a distância é alcançada de tempo para visitar os vértices.
null
, e então cada vértice é enfileirado no máximo uma vez. Desde que nós examinamos o incidente de bordas em um vértice somente quando visitamos, cada aresta é examinada no máximo duas vezes, já que para a maioria das vezes o vértice sobre. Então, a pesquisa de amplitude gasta Este conteúdo é uma colaboração entre os professores de ciência da computação da Universidade de Dartmouth, Thomas Cormen e Devin Balkcom, juntamente com a equipe do currículo de computação da Khan Academy. O conteúdo é licenciado CC-BY-NC-SA.
Quer participar da conversa?
Nenhuma postagem por enquanto.