Please enable JavaScript.
Coggle requires JavaScript to display documents.
Algoritmo de Primm, Algoritmo de Kruskal, Subconjuntos disjuntos e…
Algoritmo de Primm
como funciona
Inicialmente, escolhemos um vértice arbitrário do grafo e o adicionamos na árvore geradora mínima.
Em seguida, encontramos a aresta de menor peso que conecta o vértice escolhido na etapa anterior a um vértice que ainda não está na árvore geradora mínima e a adicionamos na árvore geradora mínima.
-
-
Em cada iteração, o algoritmo expande a árvore atual de maneira gulosa, simplesmente anexando a ela o vértice mais próximo que não está nessa árvore.
Como o algoritmo expande uma árvore em 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 grafo.
A árvore gerada pelo algoritmo é obtida como o conjunto de arestas utilizadas para as expansões da árvore.
Em particular, se um gráfico é representado por sua matriz de peso e a fila de prioridade é implementada como uma array não ordenado, o tempo de execução do algoritmo será em (|V |2), ou seja quadratico
Algoritmo de Kruskal
como funciona?
Inicialmente, ordenamos todas as arestas do grafo por peso, em ordem crescente.
Em seguida, selecionamos a aresta de menor peso e a adicionamos na árvore geradora mínima, desde que não forme um ciclo com as arestas já selecionadas.
-
-
O algoritmo de Kruskal considera uma árvore geradora mínima de um grafo conectado ponderado G = ⟨V , E⟩ como um subgrafo acíclico com |V | − 1 arestas para as quais a soma dos pesos das arestas é a menor.
a cada uma de suas iterações, o algoritmo de Kruskal deve verificar se a adição da próxima aresta às arestas já selecionadas criaria um ciclo
um novo ciclo é criado se e somente se a nova aresta conecta dois vértices já conectados por um caminho, ou seja, se e somente se os dois vértices pertencem ao mesmo componente conectado
Com um algoritmo union-find eficiente, o tempo de execução do algoritmo de Kruskal será dominado pelo tempo necessário para classificar os pesos das arestas de um determinado grafo. Portanto, com um algoritmo de ordenação eficiente, a eficiência de tempo do algoritmo de Kruskal será O(|E| log |E|).
-