# Graph Traversals and Spanning Forests

**Connected Graph**

A graph is said to be **connected** if there is a path between any two of its nodes.

**Cycle**

A Path from a node to itself is called a **Cycle**. A rgaph must require at least 3 nodes to form a cycle.

**Tree**

A **Tree **is a *connected graph without cycles*.

**Spanning Forests**

A **Forest** may be defined as an acyclic graph which has each nodes having one or no predecessors. A **Tree **may be defined as a forest in which only one node has no predecessors. A Forest may be a single tree or a collection of trees. A forest is said to be ORDERED if it consists of ordered trees.

A Forest F is said to be a **Spanning Forest **of a graph G if –

- F is a sub-graph of G containing all nodes of G
- F is an ordered forest consists T1, T2 …… Tn ordered trees
- For some T, of the Spanning Forest F, the nodes contained in it are not contained in some other Tj of the same Spanning Forest.

A Spanning Forest consisting of a single tree is called a **Spanning Tree**.

Consider a Graph below –

A Spanning Forest could be drawn as shown below –

Dotted lines shows the edges in graph not present in Spanning Forest, solid line shows tree edges.

**Tree Edges** of a graph are edges present both in gaph and Spanning Forest eg: <A, D>, <A, E>, <A, B>, <B, C>.

**Forward edges **are arcs of the graph from a node to a spanning forest non-son descendant eg: <E,C>

**Back Edges **are arcs of the graphs from a spanning forest node to an ancestor eg: <CA>

**Cross edges ** are arcs of the graph from a spanning forest node to a non-descendant , non-ancestor node eg: <D,E>, <E,B>, <B,E>