Please enable JavaScript.
Coggle requires JavaScript to display documents.
Prim's Algorithm, Kruskal’s Algorithm - Coggle Diagram
Prim's Algorithm
Funcionamento
O algoritmo de Prim constrói uma árvore de abrangência 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 V de vértices do gráfico. Em cada iteração, o algoritmo expande a árvore atual de maneira gananciosa, simplesmente anexando
o vértice mais próximo que não está nessa árvore. (Por vértice mais próximo, queremos dizer um vértice que não está na árvore conectado a um vértice da árvore por uma aresta do menor peso. Os laços podem ser quebrados arbitrariamente.) O algoritmo para após todos os vértices do gráfico terem sido incluídos na árvore sendo construído.
Como o algoritmo expande uma árvore por exatamente um vértice em cada uma de suas iterações, o número total de tais iterações é n - 1, onde n é o número de vértices no gráfico. A árvore gerada pelo algoritmo é obtida como o conjunto de arestas utilizadas para as expansões da árvore
-
Uma árvore de abrangência de um grafo conectado não direcionado é seu subgrafo acíclico conectado (ou seja, 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 é a árvore geradora do menor peso, onde o peso de uma árvore é definido como a soma dos pesos em todas as suas arestas. O problema da árvore de abrangência mínima é o problema de encontrar uma árvore de abrangência mínima para um dado grafo conectado ponderado.
-
Kruskal’s Algorithm
Funcionamento
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 examina 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.
O algoritmo de Kruskal analisa uma árvore de abrangência mínima de um grafo conectado ponderado G = V, E como um subgrafo acíclico com | V | - 1 aresta para a qual a soma dos pesos das arestas é a menor. Consequentemente, o algoritmo constrói uma árvore de abrangência mínima como uma sequência em expansão de subgráficos que são sempre acíclicos, mas não estão necessariamente conectados nos estágios intermediários do algoritmo.
-
-
-