Busca em Largura e Profundidade

Pesquisa primeiro na extensão (Busca Largura)
A pesquisa em extensão (ou largura) é um dos algoritmos mais simples para se pesquisar um grafo e é o arquétipo de muitos de grafos importantes. O algoritmo de caminhos mais curtos de origem única de Dijkstra e o algoritmo de árvore de amplitude mínima de Prim utilizam ideias semelhantes às que aparecem na pesquisa primeiro na extensão.
Dado um grafo G = (V,E) e um vértice de origem distinta s, a pesquisa em extensão explora sistematicamente as arestas de G até “descobrir” cada vértice acessível a partir de s. O algoritmo calcula a distância (menor numero de arestas) desde s até todos os vértices acessíveis deste tipo. Ele também produz uma “árvore primeiro na extensão” com raiz s que contém todos os vértices acessíveis. Para qualquer vértice v acessível a partir de s, o caminho na árvore primeiro na extensão de s até v corresponde a um “caminho mais curto” de s até v em G, ou seja, um caminho que contém o número mínimo de arestas. O algoritmo funciona sobre grafos orientados e também não orientados.
A pesquisa primeiro na extensão recebe esse nome porque expande a fronteira entre vértices descobertos e não descobertos uniformemente ao longo da extensão da fronteira. Isto é, o algoritmo descobre todos os vértices à distancia k a partir de s, antes de quaisquer vértices à distância K +1.
Para controlar o andamento, a pesquisa primeiro na extensão pinta cada vértice de branco, cinza ou preto. No inicio, todos os vértices são brancos, e mais tarde eles podem se tornar acinzentadas 3 depois pretos. Um vértice é descoberto na primeira vez em que é encontrado durante a pesquisa, e nesse momento ele se torna não branco. Portanto, vértices em cor cinza e preta foram descobertos, mas a pesquisa primeiro na extensão faz distinção entre eles para assegurar que a pesquisa continuará de maneira a seguir primeiro na extensão. Se (u,
v) e E e o vértice u é preto, então o vértice v é cinza ou preto, isto é, todos