Minimum Spanning Tree- Prims & Kruskal | Binary Tree | Tree Traversal | Data Structure & Algorithm

Prim's Algorithm

Prim's algorithm is a greedy algorithm that is used to form a minimum spanning tree for a connected weighted undirected graph. In other words, the algorithm builds a tree that includes every vertex and a subset of the edges in such a way that the total weight of all the edges in the tree is minimized. . Algorithm Prims Step 1: Select a starting vertex Step 2: Repeat Steps 3 and 4 until there are fringe vertices Step 3: Select an edge e connecting the tree vertex and fringe vertex that has minimum weight Step 4: Add the selected edge and the vertex to the minimum spanning tree T [END Of LOOP] Step 5: EXIT Kruskal's Algorithm Kruskal's algorithm is used to find the minimum spanning tree for a connected weighted graph. The algorithm aims to find a subset of the edges that forms a tree that includes every vertex. The total weight of all the edges in the tree is minimized. However, if the graph is not connected, then it finds a minimum spanning forest. Note that a forest is a collection of trees. Similarly, a minimum spanning forest is a collection of minimum spanning trees. Kruskal's algorithm is an example of a greedy algorithm, as it makes the locally optimal choice at each stage with the hope of finding the global optimum. Kruskal Algorithm Step 1: Create a forest in such a way that each graph is a separate tree. Step 2: Create a priority queue Q that contains all the edges of the graph. Step 3: Repeat Steps 4 and 5 while Q is NOT EMPTY Step 4: Remove an edge from Q Step 5: IF the edge obtained in Step 4 connects two different trees, then Add it to the forest (for combining two trees into one tree). ELSE Discard the edge Step 6: END BINARY TREES A binary tree T is defined as a finite set of elements, called nodes, such that: (a) T is empty (called the null tree or empty tree). or (b) T contains a distinguished node R. called the root of T, and the remaining nodes of T form an ordered pair of disjoint binary trees T1 and T2. If T does contain a root R, then the two trees T1 and T2 are called, respectively, the left and right subtrees of R. If T1 is nonempty, then its root is called the left successor of R. similarly, if T2 is nonempty, then its root is called the right successor of R. Any node N in a binary tree T has either 0. 1 or 2 successors. The nodes with no successors are called terminal nodes. The above definition of the binary tree T is recursive since T is defined in terms of the binary subtrees T1 and T2. This means, in particular, that every node N of T contains a left and a right subtree. Moreover, if N is a terminal node, then both its left and right subtrees are empty. Binary trees T and T' are said to be similar if they have the same structure or, in other words, if they have the same shape. The trees are said to be copies if they are similar and if they have the same contents at corresponding nodes. Complete Binary Trees Consider any binary tree T Each node of T can have at most two children. Accordingly, one can show that level r of T can have at most 2 nodes. The tree T is said to be complete if all its levels, except possibly the last, have the maximum number of possible nodes, and if all the nodes at the last level appear as far left as possible. Thus there is a unique complete tree Tn with exactly n nodes (we are, of course, ignoring the contents of the nodes). TRAVERSING BINARY TREES There are three standard ways of traversing a binary tree T with root R. These three algorithms, called preorder, inorder and postorder, are as follows: Preorder (1) Process the root R. (2) Traverse the left subtree of R in preorder. (3) Traverse the right subtree of R in preorder. Inorder (1) Traverse the left subtree of R in inorder. (2) Process the root R. (3) Traverse the right subtree of R in inorder. Postorder (1)Traverse the left subtree of R in postorder. (2)Traverse the right subtree of R in postorder. (3)Process the root R. Observe that each algorithm contains the same three steps, and that the left subtree of R is always traversed before the right subtree. The difference between the algorithms is the time at which the root R is processed. Specifically, in the "pre" algorithm, the root R is processed before the subtrees are traversed; in the "in" algorithm, the root R is processed between the traversals of the subtrees; and in the "post" algorithm, the root R is processed after the subtrees are traversed.

for more details click here