Please enable JavaScript.
Coggle requires JavaScript to display documents.
Sets and Dictionaries, Space and Time Trade-Offs, Greedy Technique
Gree -…
-
-
Greedy Technique
Gree
Prim’s Algorithm:
Uma "spanning tree" de graficos conectados indiretamente se trada de um subgrafico acíclico conectado que contem todos os vertices do grafico.
caso o grafico possua pesos assimilados a suas bordas, uma "minimum spanning tree" é uma arvore com os menores pesos, onde os pesos sao definidos pela soma dos pesos de sua borda.
Kruskal’s Algorithm
Disjoint Subsets and Union-Find Algorithms:
o algoritmo de kruskal é um numero de aplicaçãoes que necessita de partições dinamicas de alguns elementos do set S em uma coleçao, que por sua vez é subjetida a uma sequencia de uniões misturados e operaçoes de procura.
-
union(x, y):
constroi a união de sets separados Sx e Sy contendo x e y, respectivamente e adiciona para a coleção substituindo Sx e Sy.
-
Dijkstra’s Algorithm:
Encontra o caminho mais curto para os vertices do grafico em ordem a sua distancia da fonte.