Please enable JavaScript.
Coggle requires JavaScript to display documents.
Algoritmo de Prim, Algoritmo de Kruskal, Algoritmos Union-Find - Coggle…
Algoritmo de Prim
É um algoritmo Greedy usado para encontrar uma árvore geradora mínima num grafo conectado, valorado e não direcionado.
Árvore geradora mínima
é um subgrafo, o qual é uma árvore que conecta todos os vértices. Um único grafo pode ter diferentes árvores de extensão. Pode-se assinalar um peso a cada aresta, que é um número que representa quão desfavorável ela é, e atribuir um peso a árvore de extensão calculado pela soma dos pesos das arestas que a compõem. Uma árvore de extensão mínima é então uma árvore de extensão com peso menor ou igual a cada uma das outras árvores de extensão possíveis.
execução:
escolhe um vértice qualquer, na próxima iteração procuraremos uma aresta com o menor peso e que conecte um vértice que não faça parte da sub-árvore com um que faça parte da subárvore
O algoritmo é repetido até que todos os vértices façam parte da subarvore ou até que não existam mais vértices que satisfaçam tal propriedade
Algoritmo de Kruskal
-
é um algoritmo greedy que busca uma árvore geradora mínima para um grafo conexo com pesos. Isto significa que ele encontra um subconjunto das arestas que forma uma árvore que inclui todos os vértices, onde o peso total, dado pela soma dos pesos das arestas da árvore, é minimizado.
Algoritmos Union-Find
é uma estrutura de dados que mantém o controle de um conjunto de elementos particionados em subconjuntos disjuntos
Para implementar essa estrutura, cada elemento armazena um id (número de identificação), um ponteiro para o pai, e, em algoritmos eficientes, o tamanho do conjunto ou um valor de classificação. Inicialmente, cada elemento representa um subconjunto.
aplicações:
podemos representar as funções de buscas de diversas formas, por exemplo:
-
-
-
