13
Sometimes here I found here in the OR, questions about trees, graphs and even forests, in the most diverse languages, but
array?Perhaps an image will help to better understand this concept.
8
In graph theory, a tree is a connected graph (there is a path between any two of its vertices) and acyclic (no cycles). It would be the same principle of N-ary Tree of Research or Binary Tree, but on the Tree each node can have multiple successors but only 1 predecessor.
Take the example:
It looks like the Binary Tree:
If the graph is acyclic but not connected, it is said to be a forest. In use of Prim and Kruskal, if you stop running Kruskal in the middle of the algorithm, you can generate a forest (unconnected sub-graphs), because the tree is only generated at the end of the 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 figure out which streets could turn off the power, what would be the minimum amount of streets with the lowest possible cost that would need to be connected? This would be a use of the minimum Tree Generator.
If you generated a Forest ( multiple trees), there is probably no viable solution.
They could be compared to an array?
No, it is more like an N-Aria Tree. Where the current position has an "Arraylist" of successors and the successor has a reference to the Father.
Reading this material Search Tree can verify a basic implementation of the Tree, but it is necessary to make the adjustments to the AGM.
Moment mathematical pedanticism: If you take into account the direction of a graph, Dags (directed acyclic graphs) may not have cycles, but they may still not be trees. For example, a bipartite graph: A->1, A->2, B->1, B->2. It is not possible to leave a point and return to it, so there are no cycles.
@Jeffersonquesado "consideration direction of a graph" = Directed graph. You are talking about Hamiltonian way correct? In your case it would be a forest. As I put in the answer: "If the graph is acyclic but not connected, it is said a forest"
No, Hamiltonian path is a problem about directed graph. Look at the example I put in the comment, acyclic but not arboreal, bipartite graph with at least two elements in each partition
The generalized case of graph takes direction into account. You get a bidirectional graph from a directional graph: if the link between the points a and b is not directed, you can represent this as two directed links: a->b and b->a
Fibonacci function recursive calls can be represented by directed acyclic graphs as well. f3->f2; f3->f1; f2 -> f1; f2-> f0
6
All are graph-based data structures. Roughly speaking, a graph is a structure defined by a set of points P and a set of edges A, where an element a of the whole A has two attributes, a.origem and a.destino, both of which a.origem and a.destino belong to the set P.
A graph can be fully connected (connected graph), or it can have totally independent parts (disconnected graph). A disconnected graph means that there are points p1 and p2 such that it is not possible to navigate from p1 and get into p2 by the edges defined in A.
A tree is a type of connected graph in which every point is bound to 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 graphs and trees in this answer are great, including even very intuitive drawings.
Browser other questions tagged terminology tree
You are not signed in. Login or sign up in order to post.
Related: https://answall.com/q/22245/57801
– Don't Panic