Minimum Spanning Tree

What is a Spanning Tree?

Given an undirected and connected graph , a spanning tree of the graph  is a tree that spans  (that is, it includes every vertex of ) and is a subgraph of  (every edge in the tree belongs to )

What is a Minimum Spanning Tree?

The cost of the spanning tree is the sum of the weights of all the edges in the tree. There can be many spanning trees. Minimum spanning tree is the spanning tree where the cost is minimum among all the spanning trees. 

There are two famous algorithms for finding the Minimum Spanning Tree:

1. Kruskal’s Algorithm
2. Prim’s Algorithm

Kruskal’s Algorithm

Kruskal's algorithm is a greedy algorithm that finds a minimum spanning tree for a connected weighted graph. It finds a tree of that graph which includes every vertex and the total weight of all the edges in the tree is less than or equal to every possible spanning tree.

Algorithm

1. Arrange all the edges of the given graph G(V,E) in ascending order as per their edge weight.
2. Choose the smallest weighted edge from the graph and check if it forms a cycle with the spanning tree formed so far.
3. If there is no cycle, include this edge to the spanning tree else discard it.
4.  Repeat Step 2 and Step 3 until (V−1) number of edges are left in the spanning tree.

1. Problem

Suppose we want to find minimum spanning tree for the following graph G using Kruskal’s algorithm.

2. Problem

Suppose we want to find minimum spanning tree for the following graph G using Kruskal’s algorithm.

From the above graph we construct the following table 

Edge No.	Vertex Pair	Edge Weight
E1	(a, b)	20
E2	(a, c)	9
E3	(a, d)	13
E4	(b, c)	1
E5	(b, e)	4
E6	(b, f)	5
E7	(c, d)	2
E8	(d, e)	3
E9	(d, f)	14

Now we will rearrange the table in ascending order with respect to Edge weight 

Edge No.	Vertex Pair	Edge Weight
E4	(b, c)	1
E7	(c, d)	2
E8	(d, e)	3
E5	(b, e)	4
E6	(b, f)	5
E2	(a, c)	9
E3	(a, d)	13
E9	(d, f)	14
E1	(a, b)	20

Since we got all the 5 edges in the last figure, we stop the algorithm and this is the minimal spanning tree and its total weight is (1+2+3+5+9)=20.

Prim's Algorithm

Prim, is a greedy algorithm that finds a minimum spanning tree for a connected weighted graph. It finds a tree of that graph which includes every vertex and the total weight of all the edges in the tree is less than or equal to every possible spanning tree. 

Algorithm

1. Initialize the minimal spanning tree with a single vertex, randomly chosen from the graph.
2. Repeat steps 3 and 4 until all the vertices are included in the tree.
3. Select an edge that connects the tree with a vertex not yet in the tree, so that the weight of the edge is minimal and inclusion of the edge does not form a cycle.
4. Add the selected edge and the vertex that it connects to the tree.

1. Problem

Suppose we want to find minimum spanning tree for the following graph G using Prim’s algorithm.

2. Problem

Suppose we want to find minimum spanning tree for the following graph G using Prim’s algorithm.

Solution

Here we start with the vertex ‘a’ and proceed.

This is the minimal spanning tree and its total weight is (1+2+3+5+9)=20

Graph Traversal - BFS

BFS (Breadth First Search)
BFS traversal of a graph produces a spanning tree as final result. Spanning Tree is a graph without loops. We use Queue data structure with maximum size of total number of vertices in the graph to implement BFS traversal.

Note:BFS Follows level order traversals of a given tree in its conclusion  


We use the following steps to implement BFS traversal...

Step 1 - Define a Queue of size total number of vertices in the graph.
Step 2 - Select any vertex as starting point for traversal. Visit that vertex and insert it into the Queue.
Step 3 - Visit all the non-visited adjacent vertices of the vertex which is at front of the Queue and insert them into the Queue.
Step 4 - When there is no new vertex to be visited from the vertex which is at front of the Queue then delete that vertex.
Step 5 - Repeat steps 3 and 4 until queue becomes empty.
Step 6 - When queue becomes empty, then produce final spanning tree by removing unused edges from the graph

Algorithm of BFS :

1. set status of all vertex=1
2. insert the starting vertex in queue and set its status=2
3. while(queue is not empty)
4.     remove front vertex in queue and set its status=3
5.     if(status of neighbors = 1)
6.     then insert neighbors in queue and set its status=2
7. end of while
8. exit

Example

Introduction To Graphs

Graph is a non-linear data structure. It contains a set of points known as nodes (or vertices) and a set of links known as edges (or Arcs). Here edges are used to connect the vertices. A graph is defined as follows...

Graph is a collection of vertices and arcs in which vertices are connected with arcs

                              OR
Graph is a collection of nodes and edges in which nodes are connected with edges

Generally, a graph G is represented as G = ( V , E )
where V is set of vertices
           E is set of edges.

Example

The following is a graph with 5 vertices and 7 edges.
This graph G can be defined as G = ( V , E )
Where V = {A,B,C,D,E} and E = {(A,B),(A,C)(A,D),(B,D),(C,D),(B,E),(E,D)}.

Graph Terminology

Vertex

Individual data element of a graph is called as Vertex. Vertex is also known as node. In above example graph, A, B, C, D & E are known as vertices.

Edge
An edge is a connecting link between two vertices. Edge is also known as Arc. An edge is represented as (startingVertex, endingVertex).For example, in above graph the link between vertices A and B is represented as (A,B). In above example graph, there are 7 edges (i.e., (A,B), (A,C), (A,D), (B,D), (B,E), (C,D), (D,E)).

Edges are three types.

Undirected Edge - An undirected egde is a bidirectional edge. If there is undirected edge between vertices A and B then edge (A , B) is equal to edge (B , A).

Directed Edge - A directed egde is a unidirectional edge. If there is directed edge between vertices A and B then edge (A , B) is not equal to edge (B , A).

Weighted Edge - A weighted egde is a edge with value (cost) on it.

Degree
Total number of edges connected to a vertex is said to be degree of that vertex.

Indegree
Total number of incoming edges connected to a vertex is said to be indegree of that vertex.

Outdegree

Total number of outgoing edges connected to a vertex is said to be outdegree of that vertex.

Self-loop
Edge (undirected or directed) is a self-loop if its two endpoints coincide with each other.

Simple Graph
A graph is said to be simple if there are no parallel and self-loop edges.

Path
A path is a sequence of alternate vertices and edges that starts at a vertex and ends at other vertex such that each edge is incident to its predecessor and successor vertex.

Types of graphs

Graph Traversal - DFS

Graph traversal is a technique used for a searching vertex in a graph. The graph traversal is also used to decide the order of vertices is visited in the search process. A graph traversal finds the edges to be used in the search process without creating loops. That means using graph traversal we visit all the vertices of the graph without getting into looping path.

There are two graph traversal techniques and they are as follows...

DFS (Depth First Search)
BFS (Breadth First Search)

DFS (Depth First Search)
DFS traversal of a graph produces a spanning tree as final result. Spanning Tree is a graph without loops. We use Stack data structure with maximum size of total number of vertices in the graph to implement DFS traversal.

Note:DFS Follows level order Preorder traversals of a given tree in its conclusion  

We use the following steps to implement DFS traversal...

Step 1 - Define a Stack of size total number of vertices in the graph.
Step 2 - Select any vertex as starting point for traversal. Visit that vertex and push it on to the Stack.
Step 3 - Visit any one of the non-visited adjacent vertices of a vertex which is at the top of stack and push it on to the stack.
Step 4 - Repeat step 3 until there is no new vertex to be visited from the vertex which is at the top of the stack.
Step 5 - When there is no new vertex to visit then use back tracking and pop one vertex from the stack.
Step 6 - Repeat steps 3, 4 and 5 until stack becomes Empty.
Step 7 - When stack becomes Empty, then produce final spanning tree by removing unused edges from the graph

Algorithm of DFS :

1. set status of all vertex=1
2. push the starting vertex onto stack and set its status=2
3. while(stack is not empty)
4.     pop the top vertex of stack and set its status=3
5.     if(status of neighbors = 1)
6.     then push onto stack and set its status=2
7. end of while
8. exit

Example:

Graph Representations

Graph data structure is represented using following representations...

Adjacency Matrix

Incidence Matrix

Adjacency List

Adjacency Matrix

In this representation, the graph is represented using a matrix of size total number of vertices by a total number of vertices. That means a graph with 4 vertices is represented using a matrix of size 4X4. In this matrix, both rows and columns represent vertices. This matrix is filled with either 1 or 0. Here, 1 represents that there is an edge from row vertex to column vertex and 0 represents that there is no edge from row vertex to column vertex.

For example, consider the following undirected graph representation

Directed graph representation...

Incidence Matrix

In this representation, the graph is represented using a matrix of size total number of vertices by a total number of edges. That means graph with 4 vertices and 6 edges is represented using a matrix of size 4X6. In this matrix, rows represent vertices and columns represents edges. This matrix is filled with 0 or 1 or -1. Here, 0 represents that the row edge is not connected to column vertex, 1 represents that the row edge is connected as the outgoing edge to column vertex and -1 represents that the row edge is connected as the incoming edge to column vertex.

For example, consider the following directed graph representation

Adjacency List
In this representation, every vertex of a graph contains list of its adjacent vertices.


For example, consider the following directed graph representation implemented using linked list.

This representation can also be implemented using an array as follows

Threaded Binary Tree

       Inorder traversal of a Binary tree can either be done using recursion or with the use of a auxiliary stack. The idea of threaded binary trees is to make inorder traversal faster and do it without stack and without recursion. A binary tree is made threaded by making all right child pointers that would normally be NULL point to the inorder successor of the node (if it exists).

In memory representation of threaded binary tree node is represented by

LThread

Data

RThread

Each node of any binary tree stores the three fields. The left field stores the left thread value and the right field stores the right thread value. The middle field contains the actual value of the node i.e.., data.

There are two types of threaded binary trees.

Single Threaded: Where a NULL right pointers is made to point to the inorder successor (if successor exists)

        In one way inorder threading the right child of the node would point to the next node in the sequence of the inorder traversal, such a threading tree is called “Right in threaded binary tree”. Also, the left child of the node would point to the previous node in the sequence of inorder traversal, this type of tree is called as “Left in threaded binary tree”. In case both the children of the nodes point to other nodes then such a tree is called “Fully threaded binary tree”.

         Figure(1) describes the working of right in threaded binary tree in which one can see that the right child of the node points to the node in the sequence of the inorder traversal method.

Example:

        The inorder traversal shown in fig(1) will be as D B H E A F C G. Two dangling pointers are shown to point a header node as

Rchild of D is made to point to B

Rchild of E is made to point to A

Rchild of F is made to point to C
Rchild of H is made to point to E

Fig (2) describes the working of “left in threaded binary tree”.

In this case the left child of node points to the previous node in the sequence of inorder traversal. As shown in fig (2), thread of E points to B. Here B is the predecessor of E in inorder traversal. Hence, the pointer points to B. In this type of tree the pointers pointing to other nodes are as follows.

Lchild of H is made to point to B

Lchild of F is made to point to A
Lchild of G is made to point to C

Double Threaded: Where both left and right NULL pointers are made to point to inorder predecessor and inorder successor respectively. The predecessor threads are useful for reverse inorder traversal and postorder traversal.

Fig illustrates the operation of fully threaded binary tree

Right and left children are used for pointing to the nodes in inorder traversal method.

Rchild of A is made to point to C

Lchild of A is made to point to B

Rchild of B is made to point to A

Lchild of B is made to point to D

Rchild of D is made to point to B

Lchild of D is made to point to DUMMY NODE

Lchild of C is made to point to A

Rchild of C is made to point to E

Rchild of E is made to point to DUMMY NODE

Lchild of E is made to point to C

Binary Search Tress - Insertion & Deletion

Binary Search Tree is a node-based binary tree data structure which has the following properties:

·       The left subtree of a node contains only nodes with keys lesser than the node’s key.

·       The right subtree of a node contains only nodes with keys greater than the node’s key.

·    The left and right subtree each must also be a binary search tree.

Basic Operations: Following are the basic operations of a tree 

Search − Searches an element in a tree.

Insert − Inserts an element in a tree.

Pre-order Traversal − Traverses a tree in a pre-order manner.

In-order Traversal − Traverses a tree in an in-order manner.

Post-order Traversal − Traverses a tree in a post-order manner.

Binary Search Tree (Search and Insertion)

Binary Search Tree, is a node-based binary tree data structure which has the following properties:

• The left subtree of a node contains only nodes with keys lesser than the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key.
• The left and right subtree each must also be a binary search tree.
• There must be no duplicate nodes.

Search Operation

        Whenever an element is to be searched, start searching from the root node. Then if the data is less than the key value, search for the element in the left subtree. Otherwise, search for the element in the right subtree. Follow the same algorithm for each node.

Insert Operation

      Whenever an element is to be inserted, first locate its proper location. Start searching from the root node, then if the data is less than the key value, search for the empty location in the left subtree and insert the data. Otherwise, search for the empty location in the right subtree and insert the data.

• Binary Search Tress - Insertion

Binary Search Tress -  Deletion :Deletion of a node is performed as follows,

Deleting node has no child, therefore just delete the node(made to point NULL)

Deleting node has 1 child, swap the key with the child and delete the child.

Deleting node has 2 children, in this case swap the key with inorder successor of the deleting node. It should be noted, inorder successor will be the minimum key in the right subtree (of the deleting node).