Home | | Programming and Data Structure II | Minimum Spanning Trees

Chapter: Programming and Data structures : Graphs

Minimum Spanning Trees

A Spanning tree of an undirected graph, G is a tree formed from graph edges that connects all vertices of G.

MINIMUM SPANNING TREES:

 

·        A Spanning tree of an undirected graph, G is a tree formed from graph edges that connects all vertices of G.

 

·        A Minimum Spanning tree of an undirected graph, G is a tree formed from graph edges that connects all vertices of G at lowest cost.

 

·        A minimum spanning tree exists if and only if G is connected. The number of edges in the minimum spanning tree is |V| -1.

 

·        The minimum spanning tree is a tree because it is acyclic, it is spanning because it covers every vertex, and it is minimum because it covers with minimum cost.

 

·        The minimum spanning tree can be created using two algorithms, that is prim’s algorithm and kruskal’s algorithm.

 

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail
Programming and Data structures : Graphs : Minimum Spanning Trees |


Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2023 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.