Spanning Tree

A spanning tree is a graph in computer science which composes of vertices and edges with connected nodes that form no cycle in the graph. A more refined definition would be that a spanning tree is synonymous to a graph that has a minimal or maximal set of edges that has no cycle which connects all vertices. The study spanning tree has derived some important algorithms such as depth-first search (DFS), and breath-first search (BFS). Depth-first search (DFS) is a searching algorithm that starts at the root of the graph or tree and explores every possible branch before traversing back to the root to explore the next branch. The Breath-first search (BFS) is another searching algorithm which also starts at a defined root but explores all neighboring nodes and determines each unexplored nearing nodes and explores them to reach the goal. Of course each of these algorithms was developed to optimize a way to traverse a graph or tree. Many problems were used to simulate the algorithm such as the Hamiltonian path problem, which focuses on whether a given graph has a Hamiltonian path.

A programmer spends most of his/her time studying algorithm and implementing them for each set of problems that come up.