Please enable JavaScript.

Coggle requires JavaScript to display documents.

ALGORITMO DE PRIM, ALGORITMO DE KRUSKAL - Coggle Diagram

- - - - O problema da arvore estendida minima: Encontrar esta arvore para um dado grafo conexo.
        
        Nisso entra o algoritmo de Prim, este construirá uma arvore estendida minima atraves de uma sequencia de expansão de subarvores.
        
        A subarvore inicial consiste em um unico vertice selecionado arbitrariamente do conjunto V de vertices do grafo. A cada iteração o algoritmo expande a arvore atual simplesmente conectando o novo vertice ao vertice fora da arvore mais proximo (aresta de menor peso). O algoritmo para depois que todos os vertices do grafo tiverem sido icluidos na arvore construida.
        
        Como o algoritmo expande a arvore a cada iteração, teremos um total de n-1 iterações, onde n é o num de vertices do grafo.
        
        É necessario fornecer informações sobre os vertices de fora da arvore, como a aresta menor.
        
        Damos 2 categorias ao vertice
        
        Nome do vertice da arvore que esta mais proximo
        
        Comprimento(peso) da aresta correspondente
        
        Vertices não adjacentes a nenhum dos vertices da arvore ganham a classificação de distancia "infinita"
        
        Ler pág 320
- - - - O Algoritmo inicia pelo ordenamento das arestas do grafo em ordem crescente de seus pesos. Então, iniciando com o subgrafo vazio ele lê a lista ordenada, adiciona a proxima aresta à lista do subgrafo atual se essa inclusão não criar um ciclo ou pula a aresta em caso contrario.
        
        A corretude de um akgortimo de Kruskal pode ser provada atraves de repetições de passos essenciais da prova do algoritmo de Prim.
        
        Apos algumas observações, é possivek considerar as operações do algoritmo como uma progressão atraves de uam serie de florestas que contem todos os vertices de um grafo e alguns destes vertices.
        
        A floresta inicial consiste de |V| arvores triviais, cada uma contendo um unico vertice do grafo. A floresta final consiste de uma unica arvore que é MST.
        
        A cada iteração o algoritmo seleciona o proximo vertice (u,v) da lista ordenada das arestas do grafo, encontra as arvores contendo u e v e, se estas arvores não forem as mesmas, elas serão unidas em uma arvore maior.
        
        Existem algoritmos para fazer isso: Algoritmos Union-find
- - - - Usa array indexado para os elementos do conjunto S. O valor do array indica os representantes dos subconjuntos que contem aqueles elementos. cada subconjunto é uma lista ligada, cuja cabeça contem ponteiros para os primeiros e ultimos elementos da lista.
    - - Usa uma arvore enraizada. Os nós da arvore contem os elementos do subconjunto(um por nó), com o elemento da raiz sendo o representante do subconjunto