Spanning Tree & Minimum Spanning Tree (MST)

Spanning Tree - A tree that contains every vertex of a connected graph G is referred to as a spanning tree. The below figure depicts the Finnish intercity roadways route as a sapnning tree.



Minimum Spanning Tree (MST) - the problem of computing a spanning tree with the smallest total weight is known as the Minimum Spanning Tree problem. The below figure depicts the MST that houses a collection of smallest weighted routes between the Finnish cities. Routes not taken into the MST are: 177,381,409.

What is a non-linear datastructure?

A non-linear data structure is a data structure in which a data item is connected to several other data items. So that a given data item has the possibility to reach one-or-more data items.

Pros

• Uses memory efficiently that the free contiguous memory in not an requirement for allocating data items
• The length of the data items is not necessary to be known prior to allocation

Cons

• Overhead of the link to the next data item

Examples of non-linear data-structures are Graphs and Trees. However Linked List and Arrays are linear data structures.