Início » Posts etiquetados como 'grafos'

Arquivo da tag: grafos

[ED] Aula 114 – Algoritmo de Kruskal

Olá pessoal,

Dando continuidade ao tópico árvore geradora mínima, hoje iremos ver como funciona o algoritmo de Kruskal, outro algoritmo clássico capaz de obter uma solução ótima para o problema da árvore geradora mínima.

Ele pode ter o seu funcionamento assim descrito: considerando cada vértice como uma árvore independente, o algoritmo procura a aresta de menor peso que conecte duas árvores diferentes. Os vértices das árvores selecionadas passam a fazer parte de uma mesma árvore. O processo se repete até que todos os vértices façam parte de uma mesma árvore ou quando não se pode encontrar uma aresta que satisfaça essa condição

Vamos a aula e até semana que vem.

[ED1] Aula 65 – Grafos – Busca pelo Menor Caminho

Olá a todos,

Na aula de hoje iremos ver como funciona a busca pelo menor caminho em grafos.
O menor caminho (ou caminho geodésico) entre dois vértices é o caminho que apresenta o menor comprimento dentre todos os possíveis caminhos que conectam esses vértices. No caso, o comprimento se refere ao número de arestas que conectam os dois vértices. Considerando um grafo ponderado, podemos também calcular o comprimento do caminho como sendo a soma dos pesos das arestas que compõem esse caminho.

Uma das maneiras de achar o menor caminho é utilizando o algoritmo de Dijkstra, como veremos nesta aula.

Exemplos de aplicações que usam esse tipo de busca incluem:
– achar o grau de separação entre duas pessoas em uma rede social;
– achar um trajeto em um mapa rodoviário;
– programar robôs explorar áreas;
– algoritmos de roteamento.

Até a próxima

%d blogueiros gostam disto: