Tree Data Structure

Spanning Trees

A spanning tree is a sub-graph of an undirected connected graph, which includes all the vertices of the graph with a minimum possible number of edges. If a vertex is missed, then it is not a spanning tree. The edges may or may not have weights assigned to them.

Spanning Tree

Minimum Spanning Tree

A minimum spanning tree is a spanning tree with the minimum possible sum of edge weights. The edges may or may not have weights assigned to them.

Minimum Spanning Tree

Finding Minimum Spanning Tree

There are many algorithms to find the minimum spanning tree. The most common ones are:

  • Kruskal’s Algorithm

  • Prim’s Algorithm

Kruskal’s Algorithm

Kruskal’s algorithm is a greedy algorithm that finds a minimum spanning tree for a connected weighted graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. If the graph is not connected, then it finds a minimum spanning forest (a minimum spanning tree for each connected component).

Algorithm Steps:

  • Sort the graph edges with respect to their weights.

  • Start adding edges to the MST from the edge with the smallest weight until the edge of the largest weight.

  • Only add edges which doesn’t form a cycle , edges which connect only disconnected components.

Kruskal's Algorithm

Union Find Data Structure

Union Find is a data structure that keeps track of a set of elements partitioned into a number of disjoint (non-overlapping) subsets. It supports two operations:

  • Find: Determine which subset a particular element is in. This can be used for determining if two elements are in the same subset.

  • Union: Join two subsets into a single subset.

Amortized Analysis

Amortized analysis is a method of analyzing the costs associated with a data structure that averages the worst operations out over time.