Spanning Tree:
A spanning tree of a connected graph is a subgraph that includes all of the vertices of the original graph and is also a tree. This means that the spanning tree has no circuits and is connected.
• A subgraph T of a connected graph G is called spanning tree of G if T is a tree and T include all vertices of G.
Minimum Spanning Tree:
A minimum spanning tree (MST) of a connected, undirected graph is a subset of the edges of the graph that connects all the vertices of the graph with the minimum total weight.
• The weight of an edge can be any metric, such as the length of the edge, the cost of building the edge, or the time it takes to travel across the edge.
Kruskal’s algorithm:
Kruskal’s algorithm is a greedy algorithm that finds the minimum spanning tree (MST) of a connected, undirected graph. It works by sorting the edges of the graph by weight and then adding them to the tree in ascending order until all of the vertices have been added. If adding an edge would create a cycle in the tree, the edge is not added.
- Input the given connected weighted graph G with n vertices whose minimum spanning tree T, we want to find.
- Order all the edges of the graph G according to increasing weights.
- Initialize T with all vertices but do include an edge.
- Add each of the graphs G in T which does not form a cycle until n-1 edges are added.
Q): Determine the minimum spanning tree of the weighted graph shown in fig:
Solution: Using kruskal’s algorithm arrange all the edges of the weighted graph in increasing order and initialize spanning tree T with all the six vertices of G. Now start adding the edges of G in T which do not form a cycle and having minimum weights until five edges are not added as there are six vertices.
Prim`s Algorithm:
Prim’s algorithm is a greedy algorithm that finds the minimum spanning tree (MST) of a connected, undirected graph. It works by starting at a root node and greedily adding edges to the tree until all of the vertices have been added. At each step, Prim’s algorithm adds the lightest edge that connects a vertex in the tree to a vertex that is not in the tree.
