O que seria uma árvore e uma floresta? – terminologia estrutura-de-dados árvore

Por vezes aqui, encontrei aqui no SO, perguntas sobre árvores, grafos e até florestas, nas mais diversas linguagens, mas

• Em programação, o que seria uma árvore? E o que seria uma floresta? Seria uma evolução da árvore, ou um conjunto de árvores?
• Qual a utilidade de ambas?
• Elas poderiam ser comparadas a um array?

Talvez uma imagem ajude a compreender melhor este conceito.

• Em programação, o que seria uma árvore?

Na teoria dos grafos, uma árvore é um grafo conexo (existe caminho entre quaisquer dois de seus vértices) e acíclico (não possui ciclos). Seria o mesmo princípio da Árvore N-ária de Pesquisa ou Árvore Binária, porém na Árvore cada nó pode ter vários sucessores porém apenas 1 antecessor.

Veja o exemplo:

É parecido com a Árvore Binária:

• E o que seria uma floresta?

Caso o grafo seja acíclico mas não conexo, ele é dito uma floresta. Na utilização de Prim e Kruskal, se você parar a execução de Kruskal na metade do algoritmo, você pode gerar uma floresta (sub-grafos não conexos), pois a árvore apenas é gerada no final da execução.

• Qual a utilidade de ambas?

  Vamos supor que sua cidade precise economizar energia, e que sua cidade possui N ruas, sua função é descobrir quais ruas conseguiria desligar a energia, qual seria a quantidade mínima de ruas com o menor custo possível que precisariam estar ligadas? Isso seria uma utilização da Arvore Geradora mínima.

  Se você gerou uma Floresta ( várias árvores), provavelmente não há uma solução viável.

• Elas poderiam ser comparadas a um array?

  Não, está parecido mais com uma Arvore N-Aria. Onde a posição atual possui um “ArrayList” de sucessores e o sucessor possui uma referência ao Pai.

Lendo esse material de Arvore de Pesquisa consegue verificar uma implementação básica da Árvore, porém é necessário fazer as adequações para a AGM.

Todos são estruturas de dados baseados em grafos. De grosso modo, um grafo é uma estrutura definida por um conjunto de pontos P e um conjunto de arestas A, onde um elemento a do conjunto A tem dois atributos, a.origem e a.destino, sendo que ambos a.origem e a.destino pertencem ao conjunto P.

Um grafo pode ser totalmente conectado (grafo conexo), ou ele pode ter partes totalmente independentes (grafo desconexo). Um grafo desconexo significa que existem pontos p1 e p2 tais que não é possível navegar de p1 e chegar em p2 pelas arestas definidas em A.

Uma árvore é um tipo de grafo conexo em que todo ponto seja destino de apenas uma única origem.

Uma floresta é um grafo possivelmente desconexo tal que, para cada unidade conexa, você tem uma árvore. Uma floresta conexa é uma árvore.

Como o @Everson comentou na pergunta, a explicação de grafos e árvores nesta resposta estão ótimas, incluindo até mesmo desenhos bem intuitivos.