13

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.

1

2 Respostas 2

8
  • 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:

inserir a descrição da imagem aqui

É parecido com a Árvore Binária:

inserir a descrição da imagem aqui

  • 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.

5
  • Momento pedantismo matemático: Se você levar em consideração direção de um grafo, DAGs (grafos direcionados acíclicos) podem não ter ciclos, mas mesmo assim não ser árvore. Por exemplo, um grafo bipartido: A->1, A->2, B->1, B->2. Não é possível sair de um ponto e voltar para ele, portanto não há ciclos. Commented 30/06/2017 às 14:04
  • @JeffersonQuesado "consideração direção de um grafo" = Grafo Dirigido. Você está falando de Caminho hamiltoniano correto? No seu caso seria uma floresta. Como coloquei na resposta: "Caso o grafo seja acíclico mas não conexo, ele é dito uma floresta" Commented 30/06/2017 às 14:12
  • Não, caminho hamiltoniano é um problema sobre grafo direcionado. Olhe o exemplo que coloquei no comentário, acíclico porém não arbóreo, grafo bipartido com pelo menos dois elementos em cada partição Commented 30/06/2017 às 14:14
  • O caso generalizado de grafo leva em consideração a direção. Você obtém um grafo bidirecional a partir de um grafo direcional: se a ligação entre os pontos a e b for não direcionada, você pode representar isso como duas ligações direcionadas: a->b e b->a Commented 30/06/2017 às 14:17
  • As chamadas recursivas da função de Fibonacci podem ser representadas por grafos direcionados acíclicos também. f3->f2; f3->f1; f2 -> f1; f2-> f0 Commented 30/06/2017 às 14:20
6

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.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .