Árvore de extensão mínima: diferenças entre revisões

O primeiro algoritmo a encontrar uma arvoreárvore de extensão mínima foi desenvolvido pelo cientista checo [[Otakar Borůvka]] em [[1926]] (veja [[algoritmo de Boruvka]]). Seu propósito era fornecer uma cobertura elétrica eficiente na área rural da cidade de [[Morávia do Sul (região)|Morávia do Sul]]. Existem hoje dois algoritmos comummente usados, o [[algoritmo de Prim]] e o [[algoritmo de Kruskal]]. Todos são [[algoritmo guloso|algoritmos gulosos]] que rodam em tempo polinomial, então o problema de encontrar tais árvores pertence a classe de complexidade [[p (complexidade)|P]].