Please enable JavaScript.
Coggle requires JavaScript to display documents.
ALGORITMO DE PRIM, ALGORITMO DE KRUSKAL - Coggle Diagram
ALGORITMO DE PRIM
Na ciência da computação o algoritmo de Prim é um algoritmo guloso (greedy algorithm) empregado para encontrar uma árvore geradora mínima (minimal spanning tree) num grafo conectado, valorado e não direcionado
Uma árvore geradora de um grafo conectado não direcionado é seu subgrafo acíclico conectado(isto é, uma árvore) que contém todos os vértices do grafo. Se tal gráfico tiver pesos atribuídos às suas arestas, uma árvore geradora mínima é sua árvore geradora de menor peso, onde o peso de uma árvore é definida como a soma dos pesos em todas as suas arestas. O problema de árvore geradora mínima é encontrar uma árvore de abrangência mínima para um dado grafo conectado ponderado.
Outros algoritmos conhecidos para encontrar árvores geradoras mínimas são o algoritmo de Kruskal e algoritmo de Boruvka, onde este último pode ser empregado em grafos desconexos, enquanto o algoritmo de Prim e o Algoritmo de Kruskal precisam de um grafo conexo.
O algoritmo encontra um subgrafo do grafo original no qual a soma total das arestas é minimizada e todos os vértices estão interligados
A natureza do algoritmo de Prim torna necessário fornecer a cada vértice que não está na árvore atual as informações sobre a aresta mais curta conectando o vértice a um vértice da árvore. Podemos fornecer essas informações anexando dois rótulos a um vértice: o nome do vértice da árvore mais próximo e o comprimento (o peso) da aresta correspondente
O algoritmo de Prim constrói uma árvore geradora mínima por meio de uma sequência de subárvores em expansão. A subárvore inicial em tal sequência consiste em um único vértice selecionado arbitrariamente do conjunto dos vértices do gráfico. Em cada iteração, o algoritmo expande a árvore atual de maneira gananciosa, simplesmente anexando a ela o vértice mais próximo que não está nessa árvore
ALGORITMO DE KRUSKAL
-
O algoritmo de Kruskal é um algoritmo em teoria dos grafos que busca uma árvore geradora mínima para um grafo conexo com pesos
Se o grafo não for conexo, então ele encontra uma floresta geradora mínima (uma árvore geradora mínima para cada componente conexo do grafo). O algoritmo de Kruskal é um exemplo de um algoritmo guloso (também conhecido como ganancioso ou greedy).
O algoritmo começa classificando as arestas do gráfico em ordem não decrescente de seus pesos. Então, começando com o subgráfico vazio, ele varre essa lista classificada, adicionando a próxima aresta da lista ao subgráfico atual se tal inclusão não criar um ciclo e simplesmente pulando a aresta de outra forma.
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
Ao fim do algoritmo, a floresta tem apenas um componente e forma uma árvore geradora mínima do grafo.
Com o uso de uma estrutura de dados eficiente, o algoritmo de Kruskal possui complexidade de tempo igual a O (m log n), onde m representa o número de arestas e n o número de vértices