Tree
Tree
Tree
An undirected graph in which any two vertices are connected by exactly one path, or equivalently a connected acyclic undirected graph.
An undirected graph in which any two vertices are connected by exactly one path, or equivalently a connected acyclic undirected graph.
In a tree, there is a unique path connecting any 2 vertices.
In a tree, there is a unique path connecting any 2 vertices.
Minimum Spanning Tree
Minimum Spanning Tree
A weighted undirected graph that connects all the vertices together with the minimum possible total edge weight.
A weighted undirected graph that connects all the vertices together with the minimum possible total edge weight.
In the applet below, the length of the edge is taken as the edge weight. It represents the least length of edges that will connect all the vertices together.
In the applet below, the length of the edge is taken as the edge weight. It represents the least length of edges that will connect all the vertices together.