Please enable JavaScript.
Coggle requires JavaScript to display documents.
MM14 - Coggle Diagram
MM14
Prim’s Algorithm
Uma arvore geradora de um graph conectado não direcionado é seu subgrah acíclico conectado (isto é, uma árvore) que contém todos os vértices do graph
Se tal graph tiver pesos atribuídos as suas arestas, uma árvore geradora mínima é sua árvore geradora de menor peso, onde o peso de uma árvore é definido como a soma dos pesos em todas as suas arestas
O problema da árvore geradora mínima é o problema de encontrar uma árvore geradora mínima para um determinado graph conectado ponderado
O algoritmo de Prim constrói uma árvore geradora mínima por meio de uma sequência de subárvores em extensão
A subárvore inicial em tal sequência consiste em um único vértice selecionado arbitrariamente do conjunto de V vértices do graph
Em cada interação, o algoritmo expande a árvore atual de maneira gananciosa, simplesmente anexando ela o vértice mais próximo que não está naquela árvore
Por vértice mais próximo, queremos dizer um vértice que não está na árvore conectado a um vértice na árvore por uma aresta de menor peso
-
O algoritmo para depois que todos os vértices do graph foram incluídos na árvore que está sendo construída
Como o algoritmo expande uma árvore exatamente em um vértice em cada uma de suas interações, o número total de tais interações é n-1, onde n é o número de vértices do graph
A árvore gerada pelo algoritmo é obtida como o conjunto de arestas utilizadas para expansão da árvore
A natureza do algoritmo de Prim torna necessário fornecer a cada vértice que não está na árvore atual a informação sobre a aresta mais curta que conecta 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(peso) da aresta correspondente
Os vértices que não são adjacentes a nenhum dos vértices da árvore podem receber um rotulo ∞ indicando sua distância “infinita” aos vértices da árvore e um rotulo nulo para o nome do vértice da árvore mais próximo
Alternativamente, podemos dividir os vértices que não estão na árvore em dois conjuntos, a “franja” e o “invisível”
A franja contém apenas os vértices que não estão na árvore, mas são adjacentes a pelo menos um vértice da árvore
-
Os vértices invisíveis são todos os outros vértices do graph, chamados de “invisíveis” porque ainda não foram afetados pelo algoritmo
Depois de identificarmos um vértice u* a ser adicionado à árvore, precisamos realizar duas operações:
-
Para cada vértice restante u em V – Vt que está conectado a u por uma aresta mais curta que o rotulo de distância atual de u, atualize seus rótulos por u entre os pesos da aresta entre u* e u, respectivamente
-
Kruskal’s Algorithm
O algoritmo de Kruskal ana,V,Elisa uma árvore geradora mínima de um graph conectado ponderado G = <V,E> como um subgraph acíclico com |V|-1 arestas para o qual a soma dos pesos da aresta é a menor
-
Consequentemente, o algoritmo constrói uma árvore geradora mínima como uma sequência em expansão de subgraph que são sempre acíclicos, mas não estão necessariamente conectados nos estágios intermediários do algoritmo
O algoritmo começa classificando as arestas do gráfico em ordem não decrescente de seus pesos. Então, começando com o subgraph vazio, ele varre essa lista ordenada, adicionando a próxima aresta da lista ao subgraph atual se tal inclusão não criar um ciclo e simplesmente pulando a aresta caso o contrário