Skip to main content

Difference between Spanning tree and Minimal Spanning Tree

Spanning Tree
A spanning tree of a connected, undirected graph G can also be defined as a maximal set of edges of G that contains no cycle, or as a minimal set of edges that connect all vertices.


A sub-graph T of a connected graph G(V,E) is called a Spanning Tree if T is a tree and if T includes every vertex of G i.e. V(T)=V(G).
If |V|=n and |E|=m, then the spanning tree of G must have n vertices and hence n-1 edges.
The resultant spanning ensure that the graph remain connected and further there is no circuit in it.


Two algorithms for finding a spanning tree are BFS (Breadth First Search) and DFS (Depth First Search).


Minimum Spanning Tree
A minimum spanning tree (MST) or minimum weight spanning tree is then a spanning tree with weight less than or equal to the weight of every other spanning tree.


Two algorithms commonly used, Prim's algorithm and Kruskal's algorithm.


Note:- Difference between Spanning tree and Minimal Spanning Tree is that 
          Spanning Tree is applicable for Graphs without Weights.
          Minimal Spanning Tree is applicable for Weighted Graphs



Labels:

Comments

Post a Comment

Popular posts from this blog

Use Case Diagram for Online Book Store

Post a Comment
Read more

Online Movie Ticket Booking Sequence Diagram

Post a Comment
Read more

Linear search & Binary search using Template

Write a program to search an element from a list. Give user the option to perform Linear or Binary search. Use Template functions. #include<iostream> using namespace std; template <class T> void Lsearch(T *a, T item, int n) { int z=0; for(int i=0;i<n;i++) { if(a[i]== item) { z=1; cout<<"\n Item found at position = "<<i+1<<"\n\n"; } else if(z!=1) { z=0; } } if(z==0) cout<<"\n Item not found in the list\n\n"; } template <class T> void Bsearch(T *a, T item, int n) { int beg=0,end=n-1; int mid=beg+end/2; while((a[mid]!=item) && (n>0)) { if(item>a[mid]) beg=mid; else end=mid; mid=(beg+end)/2; n--; } if(a[mid]==item) cout<<"\n Item found at position = "<<mid+1<<"\n\n"; else cout<<"\n Item not found in the list\n\n"; } void main() { int iarr[10] = {2,42,56,86,87,99,323,546,767,886};
Post a Comment
Read more