Explain Spanning Tree
GIAN Tutorials
11:05 PM
Spanning Tree Spanning tree can be defined as a sub-graph of connected, undirected graph G that is a tree produced by removing the desired number of edges from a graph. In other words, Spanning tree is a non-cyclic sub-graph of a connected and undirected graph G that connects all the vertices together. A graph G can have multiple spanning trees. Minimum Spanning Tree There can be weights assigned to every edge in a weighted graph. However, A minimum spanning tree is a spanning tree which has minimal total weight. In other words, minimum spanning tree is the one which contains the least weight among all other spanning tree of some particular graph. Shortest path algorithms In this section of the tutorial, we will discuss the algorithms to calculate the shortest path between two nodes in a graph. There are two algorithms which are being used for this purpose. Prim's Algorithm Kruskal's Algorithm
