What would a tree and a forest be?

12

Sometimes here, I found here in the OS , questions about trees, graphs and even forests, in the most diverse languages, but

  • In programming, what would a tree be? And what would a forest be? Is it an evolution of the tree, or a set of trees?
  • What is the use of both?
  • Could they be compared to a array ?

Perhaps an image will help you better understand this concept.

    
asked by anonymous 30.06.2017 / 15:12

2 answers

7
  • In programming, what would a tree be?
In graph theory, a tree is a connected graph (there is path between any two of its vertices) and acyclic (no cycles). It would be the same principle as the Narya Research Tree or Binary Tree , but in the Tree each node can have several successors but only 1 predecessor.

See the example:

It'ssimilartoBinaryTree:

  • Andwhatwouldaforestbe?

Ifthegraphisacyclicbutnotconnected,itissaidtobeaforest.In Prim and Kruskal , if you stop running Kruskal in the middle of the algorithm, you can generate a forest (unrelated sub-graphs) because the tree is only generated at the end of execution.

  • What is the use of both?

    Let's assume that your city needs to save energy, and that your city has N streets, its function is to find out which streets could turn off the power, what would be the minimum amount of streets with the lowest possible cost that they would need to be connected? This would be a minimal Generating Tree usage.

    If you have spawned a Forest (several trees), there is probably no viable solution.

  • Could they be compared to an array?

    No, it's more like an N-Aryan Tree. Where the current position has an "ArrayList" of successors and the successor has a reference to the parent.

Reading this Research Tree Material can verify a basic implementation of the Tree, however it is necessary to make the adjustments for the AGM.

    
30.06.2017 / 15:48
5

All are graph-based data structures. In general, a graph is a structure defined by a set of points P and a set of A edges, where a a element of the A set has two attributes, a.origem and a.destino both a.origem and a.destino belong to the P set.

A graph can be fully connected (connected graph), or it can have totally independent parts (disconnected graph). A disconnected graph means that there are p1 and p2 points such that it is not possible to navigate from p1 to p2 by the edges defined in A .

A tree is a type of connected graph where every point is the destination of only one source.

A forest is a possibly disconnected graph such that for each connected unit you have a tree. A connected forest is a tree.

As @Everson commented on the question, the explanation of trees in this answer is great, including even intuitive designs.

    
30.06.2017 / 15:27