Graph Traversal and Spanning Forests

Graph Traversal

In computer science, graph traversal is the process of visiting (checking and/or updating) each node of a graph. Such traversals are classified by the order of visiting of the nodes. Unlike a tree traversal, graph traversal may involvethe same node being visited more than once, which is undesirable. So, there needs to be maintained another way of specifying that a node has already been visited. This is often done using the 'color' parameter associated with the node.

All the graph traversal algorithms result in a tree containing all the nodes of the graph. DFS (Depth First Search) and BFS (Breadth First Search) are the most common graph traversal algorithms. They will be covered in the upcoming section.

Spanning Forest

A forest may be defined as an acyclic graph in which every node has one or no predecessor. Spanning tree T of an undirected graph G is a subgraph that includes all of the vertice of G that is a tree.

A minimum spanning tree is a subgraph of an undirected weighted graph G, such that

• It is a tree (i.e it is acyclic)
• It covers all the vertices V
  • contains |V|-1 edges
• The total cost associated with tree edges is the minimum among all possible spanning trees
• Not necessarily unique

References

1. Karumanchi, N. "Data Structures and Algorithms Made Easy"

2. Y. Langsam, M. J. Augenstein and A. M Tenenbaum, “Data Structures using C and C++”

3. R. L. Kruse, B. P. Leung, C. L. Tondo, “Data Structure and Program design in C”

4. https://en.wikipedia.org/wiki/Graph_traversal