Spanning Tree

Spanning Tree

A tree T is a spannig tree of a graph G if T is a subgraph of G that contains all of the vertices of G.

method to find a spanning tree

Breadth-First search is a method to process all the vertices on a given level before moving to the next-higher level.

Depth-First search is a method to proceeds to successive levels in a tree at the earliest possible opportunity.

Breadth-First search       Depth-First search

      

Minimal spanning tree

Let G be a weighted graph. A minimal spanning tree of G is a spanning tree of G with minimum weight.

Algorithm to find a minimal spanning tree

Prim's Algorithm begins with a single vertex. Then at each iteration, it adds to the current tree a minimum-weight edge that does not complete a cycle.

Kruskal's algorithm find the edge in the graph with smallest weight that does not complete a cycle.

Prim's Algorithm

Kruskal's algorithm