Texto

Busca em largura (BFS-Breadth First Seach)

 Expande a explosão dos grafos em níveis

 A partir do vértice inicial, o nível explorado é dos vértices adjacentes.

 Após a exploração deste nível, passa-se a exploração dos vértices adjacentes aos do nível anterior.

 O procedimento se repete ate que todos os vértices tenham sidos explorados.

Busca em profundidade (DFS-Depth first Search)

 A busca em profundidade explora todos os níveis de cada adjacência.

 A partir da vértice inicial ,explora-se todos os níveis possíveis de uma adjacência.

 Quando não for mais possível expandir a busca, retorna-se a busca com o ultimo nó da adjacência ainda não exploradas e retorna-se ao processo.

 A explosão é repetida ate que todos os nos tenham sido visitados.

 Critério de definição para rota de menor valor em grafo com peso (grafo valorado)

 W (e) é o peso de uma aresta

 Comprimento do caminho C é o numero w (c),dado pela soma dos pesos das arestas em C.

 A distancia d (a,b) entre dois vértices a e b ,no grafo é p menor comprimento do caminho a e b.

 Ciclos não são considerados.

 Senão existe caminho possível entre A e B a distancia d (a,b) = ∞ (infinito)

Menor caminho ou caminho inicio entre a e b ,é o caminho (direcionado ou não) de menor comprimento entre os dois

Dentre as alternativas de algoritmo para solução deste programa ,vamos estudas o algoritmo de DIJKSTRA .

 Seja um grafo valorado direcionado

 G[i][j] a distancia entre os vértices i e j

 D[i] a distancia do vértice inicial ate o vértice j

 Inicialmente d[] para cada vértice é ∞ (infinito ) exceto para o inicial que é zero.

 S é o conjunto de vértices com o calculo da distancia incompleto

 Pred [i] o vértice que antecede o vértice i no caminho mais curto do vértice inicial i.

Algoritmo distancia em português estruturado

1. Inicialmente d[i]=∞ para todo vértice i, exceto o inicial que tem valor d[inicial]=0.

2. Enquanto S não for vazio

3. Procure o vértice com a menor distancia incompleta em S chamado j.

4. Para o vértice j de S

5. Para cada vértice i vizinho de j