# Forest (graph theory)

In graph theory, a forest is an acyclic graph. If this is connected , one speaks of a tree . Every connected component of a forest is a tree.

Sometimes it makes sense to mark a node as the root. One then speaks of a root tree . On the one hand, such roots can be defined arbitrarily. On the other hand, there are special directed graphs where a root explains itself through the structure of the edge directions, for example as the only node without an incoming / outgoing edge. Such trees are called home , or out-Trees . The in and out forests are then graphs with several such components.

## Algorithms on forests

Due to their simple structure, the complexity of algorithms working on forests can usually be estimated well. Often the algorithms with a tree as a data structure work faster than other algorithms for the same problem . For example, for the problem of sorting, the heapsort working on trees is faster than a rather naive insertion sort .

## Special role within graph theory

In order to be able to consider all nodes of a graph efficiently, trees or forests are often constructed from the graph for the reasons already mentioned. Methods such as breadth-first search or depth-first search are suitable for this purpose . The result is a spanning tree . A minimal spanning tree is constructed with separate consideration of the edge weights , as is done by the algorithm of Kruskal or the algorithm of Prim . This serves, for example, as the basis for algorithms for the traveling salesman problem .

Counterexample: directed acyclic graphs do not have to be forests

## Important statements and sentences

• All forests are bipartite . A bipartition is obtained by combining the nodes with respect to their distance modulo 2 to form an arbitrary, fixed node.
• All forests are planar .
• Exactly all directed acyclic graphs can be sorted topologically , so directed forests in particular.
• A graph is a forest if and only if its cyclomatic number is.${\ displaystyle 0}$