Implementation (Part 2)
Lição 6 de 9 do curso Algoritmo de Prim - Algoritmos de Grafos da Coddy.
Agora expanda a árvore, sempre adicionando a aresta de travessia mais barata.
Desafio
MédioAgora faça a árvore inteira crescer.
Escreva uma função chamada prim que receba n e o array plano edges (triplas, não direcionadas) de um grafo conectado, e retorne o peso total da Árvore Geradora Mínima (Minimum Spanning Tree), iniciando a árvore a partir do vértice 0.
Mantenha uma flag inTree por vértice. A cada rodada, encontre a aresta mais barata com exatamente uma extremidade na árvore, adicione seu peso e traga sua extremidade externa para dentro da árvore.
Experimente você mesmo
#include <stdlib.h>
int prim(int n, int* edges, int edges_size) {
// Escreva o código aqui
return 0;
}
Teste seus conhecimentosEsta lição inclui um quiz rápido. Comece a lição para respondê-lo e acompanhar seu progresso.
Todas as lições de Algoritmo de Prim - Algoritmos de Grafos
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity