Please enable JavaScript.
Coggle requires JavaScript to display documents.
Algoritmos, //Input: A weighted connected graph G = V,E, //Output: ET ,…
Algoritmos
Prim's Algorithm
Dados n pontos, conecte-os da maneira mais barata possível para que haja um caminho entre cada par de pontos.
Aplicações
-
-
-
Soluções aproximadas para mais problemas difíceis, como o problema do caixeiro viajante
-
-
-
-
Kruskal's Algorithm
-
Implementação
//Input: A weighted connected graph G = V,E
//Output: ET , the set of edges composing a minimum spanning tree of G
-
-
-
-
-
-
-
-
-
Eficiencia Temporal
o tempo de execução do algoritmo de Kruskal será dominado pelo tempo necessário para classificar os pesos das arestas de um determinado gráfico. Portanto, com um algoritmo de classificação eficiente, a eficiência do tempo do algoritmo de Kruskal estará em O (| E | log | E |).
-
//Input: A weighted connected graph G = V,E
-
//Output: ET , the set of edges composing a minimum spanning tree of G
-
-
-
-
find a minimum-weight edge e∗ = (v∗, u∗) among all the edges (v, u)
-
-
-
-
-