Unit 3

Tree
Tree represents the nodes connected by edges. We will discuss binary tree or binary
search tree specifically.
Binary Tree is a special datastructure used for data storage purposes. A binary tree has
a special condition that each node can have a maximum of two children. A binary tree
has the benefits of both an ordered array and a linked list as search is as quick as in a
sorted array and insertion or deletion operation are as fast as in linked list.

Important Terms
Following are the important terms with respect to tree.
• Path − Path refers to the sequence of nodes along the edges of a tree.
• Root − The node at the top of the tree is called root. There is only one root per
tree and one path from the root node to any node.
• Parent − Any node except the root node has one edge upward to a node called
parent.
• Child − The node below a given node connected by its edge downward is called
its child node.
• Leaf − The node which does not have any child node is called the leaf node.
• Subtree − Subtree represents the descendants of a node.
• Visiting − Visiting refers to checking the value of a node when control is on the
node.
 • Traversing − Traversing means passing through nodes in a specific order.
• Levels − Level of a node represents the generation of a node. If the root node is
at level 0, then its next child node is at level 1, its grandchild is at level 2, and so
on.
• keys − Key represents a value of a node based on which a search operation is to
be carried out for a node.

Tree Traversals
Traversal is a process to visit all the nodes of a tree and may print their values too.
Because, all nodes are connected via edges (links) we always start from the root (head)
node. That is, we cannot randomly access a node in a tree. There are three ways which
we use to traverse a tree −

• In-order Traversal
• Pre-order Traversal
• Post-order Traversal
Generally, we traverse a tree to search or locate a given item or key in the tree or to
print all the values it contains.

In-order Traversal
In this traversal method, the left subtree is visited first, then the root and later the right
sub-tree. We should always remember that every node may represent a subtree itself.
If a binary tree is traversed in-order, the output will produce sorted key values in an
ascending order.
We start from A, and following in-order traversal, we move to its left subtree B. B is also
traversed in-order. The process goes on until all the nodes are visited. The output of
inorder traversal of this tree will be −
D→B→E→A→F→C→G
Algorithm
Until all nodes are traversed −
Step 1 − Recursively traverse left subtree.
Step 2 − Visit root node.
Step 3 − Recursively traverse right subtree.

Pre-order Traversal
In this traversal method, the root node is visited first, then the left subtree and finally the
right subtree.

We start from A, and following pre-order traversal, we first visit A itself and then move to
its left subtree B. B is also traversed pre-order. The process goes on until all the nodes
are visited. The output of pre-order traversal of this tree will be −
A→B→D→E→C→F→G
Algorithm
Until all nodes are traversed −
Step 1 − Visit root node.
Step 2 − Recursively traverse left subtree.
Step 3 − Recursively traverse right subtree.

Post-order Traversal
In this traversal method, the root node is visited last, hence the name. First we traverse
the left subtree, then the right subtree and finally the root node.

We start from A, and following Post-order traversal, we first visit the left subtree B. B is
also traversed post-order. The process goes on until all the nodes are visited. The
output of post-order traversal of this tree will be −
D→E→B→F→G→C→A
Types of Binary Tree
1. Complete Binary Tree
2. Perfect Binary Tree
3. Full Binary Tree
4. Almost complete Binary Tree

Binary Search tree

In this article, we will discuss the Binary search tree. This article will be very helpful and
informative to the students with technical background as it is an important topic of their
course.

Before moving directly to the binary search tree, let's first see a brief description of the
tree.
What is a tree?
A tree is a kind of data structure that is used to represent the data in hierarchical form. It
can be defined as a collection of objects or entities called as nodes that are linked
together to simulate a hierarchy. Tree is a non-linear data structure as the data in a tree
is not stored linearly or sequentially.

Now, let's start the topic, the Binary Search tree.

What is a Binary Search tree?

A binary search tree follows some order to arrange the elements. In a Binary search tree,
the value of left node must be smaller than the parent node, and the value of right node
must be greater than the parent node. This rule is applied recursively to the left and
right subtrees of the root.

Let's understand the concept of Binary search tree with an example.

In the above figure, we can observe that the root node is 40, and all the nodes of the left
subtree are smaller than the root node, and all the nodes of the right subtree are
greater than the root node.

Similarly, we can see the left child of root node is greater than its left child and smaller
than its right child. So, it also satisfies the property of binary search tree. Therefore, we
can say that the tree in the above image is a binary search tree.
Suppose if we change the value of node 35 to 55 in the above tree, check whether the
tree will be binary search tree or not.

In the above tree, the value of root node is 40, which is greater than its left child 30 but
smaller than right child of 30, i.e., 55. So, the above tree does not satisfy the property of
Binary search tree. Therefore, the above tree is not a binary search tree.

Advantages of Binary search tree

o Searching an element in the Binary search tree is easy as we always
have a hint that which subtree has the desired element.
o As compared to array and linked lists, insertion and deletion
operations are faster in BST.

Example of creating a binary search tree

Now, let's see the creation of binary search tree using an example.

Suppose the data elements are - 45, 15, 79, 90, 10, 55, 12, 20, 50

o First, we have to insert 45 into the tree as the root of the tree.
o Then, read the next element; if it is smaller than the root node, insert
it as the root of the left subtree, and move to the next element.
o Otherwise, if the element is larger than the root node, then insert it as
the root of the right subtree.
Now, let's see the process of creating the Binary search tree using the given data
element. The process of creating the BST is shown below -

Step 1 - Insert 45.

Step 2 - Insert 15.

As 15 is smaller than 45, so insert it as the root node of the left subtree.

Step 3 - Insert 79.

As 79 is greater than 45, so insert it as the root node of the right subtree.
Step 4 - Insert 90.

90 is greater than 45 and 79, so it will be inserted as the right subtree of 79.

Step 5 - Insert 10.

10 is smaller than 45 and 15, so it will be inserted as a left subtree of 15.

Step 6 - Insert 55.

55 is larger than 45 and smaller than 79, so it will be inserted as the left subtree of 79.

Step 7 - Insert 12.

12 is smaller than 45 and 15 but greater than 10, so it will be inserted as the right
subtree of 10.
Step 8 - Insert 20.

20 is smaller than 45 but greater than 15, so it will be inserted as the right subtree of 15.
Step 9 - Insert 50.

50 is greater than 45 but smaller than 79 and 55. So, it will be inserted as a left subtree
of 55.

Now, the creation of binary search tree is completed. After that, let's move towards the
operations that can be performed on Binary search tree.

We can perform insert, delete and search operations on the binary search tree.

Let's understand how a search is performed on a binary search tree.

Searching in Binary search tree

Searching means to find or locate a specific element or node in a data structure. In
Binary search tree, searching a node is easy because elements in BST are stored in a
specific order. The steps of searching a node in Binary Search tree are listed as follows -

1. First, compare the element to be searched with the root element of

the tree.
 2. If root is matched with the target element, then return the node's
location.
3. If it is not matched, then check whether the item is less than the root
element, if it is smaller than the root element, then move to the left
subtree.
4. If it is larger than the root element, then move to the right subtree.
5. Repeat the above procedure recursively until the match is found.
6. If the element is not found or not present in the tree, then return
NULL.

Now, let's understand the searching in binary tree using an example. We are taking the
binary search tree formed above. Suppose we have to find node 20 from the below tree.

Step1:

Step2:
 Step3:

Now, let's see the algorithm to search an element in the Binary search tree.

Algorithm to search an element in Binary search tree

1. Search (root, item)
2. Step 1 - if (item = root → data) or (root = NULL)
3. return root
4. else if (item < root → data)
5. return Search(root → left, item)
6. else
7. return Search(root → right, item)
8. END if
9. Step 2 - END

Now let's understand how the deletion is performed on a binary search tree. We will
also see an example to delete an element from the given tree.

Deletion in Binary Search tree

In a binary search tree, we must delete a node from the tree by keeping in mind that the
property of BST is not violated. To delete a node from BST, there are three possible
situations occur -

o The node to be deleted is the leaf node, or,

o The node to be deleted has only one child, and,
o The node to be deleted has two children

We will understand the situations listed above in detail.

When the node to be deleted is the leaf node

It is the simplest case to delete a node in BST. Here, we have to replace the leaf node
with NULL and simply free the allocated space.

We can see the process to delete a leaf node from BST in the below image. In below
image, suppose we have to delete node 90, as the node to be deleted is a leaf node, so
it will be replaced with NULL, and the allocated space will free.

When the node to be deleted has only one child

In this case, we have to replace the target node with its child, and then delete the child
node. It means that after replacing the target node with its child node, the child node
will now contain the value to be deleted. So, we simply have to replace the child node
with NULL and free up the allocated space.

We can see the process of deleting a node with one child from BST in the below image.
In the below image, suppose we have to delete the node 79, as the node to be deleted
has only one child, so it will be replaced with its child 55.

So, the replaced node 79 will now be a leaf node that can be easily deleted.

When the node to be deleted has two children

This case of deleting a node in BST is a bit complex among other two cases. In such a
case, the steps to be followed are listed as follows -

o First, find the inorder successor of the node to be deleted.

o After that, replace that node with the inorder successor until the
target node is placed at the leaf of tree.
o And at last, replace the node with NULL and free up the allocated
space.

The inorder successor is required when the right child of the node is not empty. We can
obtain the inorder successor by finding the minimum element in the right child of the
node.

We can see the process of deleting a node with two children from BST in the below
image. In the below image, suppose we have to delete node 45 that is the root node, as
the node to be deleted has two children, so it will be replaced with its inorder successor.
Now, node 45 will be at the leaf of the tree so that it can be deleted easily.

Now let's understand how insertion is performed on a binary search tree.

Insertion in Binary Search tree

A new key in BST is always inserted at the leaf. To insert an element in BST, we have to
start searching from the root node; if the node to be inserted is less than the root node,
then search for an empty location in the left subtree. Else, search for the empty location
in the right subtree and insert the data. Insert in BST is similar to searching, as we always
have to maintain the rule that the left subtree is smaller than the root, and right subtree
is larger than the root.

Now, let's see the process of inserting a node into BST using an example.
The complexity of the Binary Search tree
Let's see the time and space complexity of the Binary search tree. We will see the time
complexity for insertion, deletion, and searching operations in best case, average case,
and worst case.

1. Time Complexity
Operations Best case time Average case time Worst case time
 complexity complexity complexity

Insertion O(log n) O(log n) O(n)

Deletion O(log n) O(log n) O(n)

Search O(log n) O(log n) O(n)

Where 'n' is the number of nodes in the given tree.

AVL Trees

Advertisements

Previous Page

Next Page
What if the input to binary search tree comes in a sorted (ascending or descending) manner? It
will then look like this −
It is observed that BST's worst-case performance is closest to linear search algorithms, that is
Ο(n). In real-time data, we cannot predict data pattern and their frequencies. So, a need arises to
balance out the existing BST.
Named after their inventor Adelson, Velski & Landis, AVL trees are height balancing binary
search tree. AVL tree checks the height of the left and the right sub-trees and assures that the
difference is not more than 1. This difference is called the Balance Factor.
Here we see that the first tree is balanced and the next two trees are not balanced −

In the second tree, the left subtree of C has height 2 and the right subtree has height 0, so the
difference is 2. In the third tree, the right subtree of A has height 2 and the left is missing, so it is
0, and the difference is 2 again. AVL tree permits difference (balance factor) to be only 1.
BalanceFactor = height(left-sutree) − height(right-sutree)
If the difference in the height of left and right sub-trees is more than 1, the tree is balanced using
some rotation techniques.
AVL Rotations
To balance itself, an AVL tree may perform the following four kinds of rotations −

• Left rotation
• Right rotation
• Left-Right rotation
• Right-Left rotation
The first two rotations are single rotations and the next two rotations are double rotations. To
have an unbalanced tree, we at least need a tree of height 2. With this simple tree, let's
understand them one by one.
Left Rotation
If a tree becomes unbalanced, when a node is inserted into the right subtree of the right subtree,
then we perform a single left rotation −

In our example, node A has become unbalanced as a node is inserted in the right subtree of A's
right subtree. We perform the left rotation by making A the left-subtree of B.

Right Rotation
AVL tree may become unbalanced, if a node is inserted in the left subtree of the left subtree. The
tree then needs a right rotation.
As depicted, the unbalanced node becomes the right child of its left child by performing a right
rotation.
Left-Right Rotation
Double rotations are slightly complex version of already explained versions of rotations. To
understand them better, we should take note of each action performed while rotation. Let's first
check how to perform Left-Right rotation. A left-right rotation is a combination of left rotation
followed by right rotation.

State Action

A node has been inserted into the right subtree of the left
subtree. This makes C an unbalanced node. These
scenarios cause AVL tree to perform left-right rotation.

We first perform the left rotation on the left subtree of C.

This makes A, the left subtree of B.

Node C is still unbalanced, however now, it is because of

the left-subtree of the left-subtree.
 We shall now right-rotate the tree, making B the new root
node of this subtree. C now becomes the right subtree of
its own left subtree.

The tree is now balanced.

Right-Left Rotation
The second type of double rotation is Right-Left Rotation. It is a combination of right rotation
followed by left rotation.

State Action

A node has been inserted into the left subtree of the right
subtree. This makes A, an unbalanced node with balance
factor 2.

First, we perform the right rotation along C node,

making C the right subtree of its own left subtree B.
Now, B becomes the right subtree of A.
 Node A is still unbalanced because of the right subtree of
its right subtree and requires a left rotation.

A left rotation is performed by making B the new root

node of the subtree. A becomes the left subtree of its
right subtree B.

The tree is now balanced.

Difference between BST and AVL Tree

Binary Search tree AVL tree

Every binary search tree is a binary tree because Every AVL tree is also a binary tree because AVL
both the trees contain the utmost two children. tree also has the utmost two children.

In BST, there is no term exists, such as balance In the AVL tree, each node contains a balance
factor. factor, and the value of the balance factor must
be either -1, 0, or 1.

Every Binary Search tree is not an AVL tree Every AVL tree is a binary search tree because the
because BST could be either a balanced or an AVL tree follows the property of the BST.
unbalanced tree.

Each node in the Binary Search tree consists of Each node in the AVL tree consists of four fields,
three fields, i.e., left subtree, node value, and the i.e., left subtree, node value, right subtree, and
right subtree. the balance factor.

In the case of Binary Search tree, if we want to In the case of AVL tree, first, we will find the
insert any node in the tree then we compare the suitable place to insert the node. Once the node
node value with the root value; if the value of is inserted, we will calculate the balance factor of
node is greater than the root node value then the each node. If the balance factor of each node is
node is inserted to the right subtree otherwise the satisfied, the insertion is completed. If the balance
node is inserted to the left subtree. Once the factor is greater than 1, then we need to perform
node is inserted, there is no need of checking the some rotations to balance the tree.
height balance factor for the insertion to be
completed.

In Binary Search tree, the height or depth of the In AVL tree, the height or depth of the tree is
tree is O(n) where n is the number of nodes in the O(logn).
Binary Search tree.

It is simple to implement as we have to follow the It is complex to implement because in AVL tree,
Binary Search properties to insert the node. we have to first construct the AVL tree, and then
we need to check height balance. If the height is
imbalance then we need to perform some
rotations to balance the tree.

BST is not a balanced tree because it does not AVL tree is a height balanced tree because it
follow the concept of the balance factor. follows the concept of the balance factor.

Searching is inefficient in BST when there are Searching is efficient in AVL tree even when there
large number of nodes available in the tree are large number of nodes in the tree because
because the height is not balanced. the height is balanced.

Heap
Heap is a special case of balanced binary tree data structure where the root-node key is
compared with its children and arranged accordingly. If α has child node β then −
key(α) ≥ key(β)
As the value of parent is greater than that of child, this property generates Max Heap.
Based on this criteria, a heap can be of two types −
For Input → 35 33 42 10 14 19 27 44 26 31
Min-Heap − Where the value of the root node is less than or equal to either of its
children.

Max-Heap − Where the value of the root node is greater than or equal to either of its
children.

Both trees are constructed using the same input and order of arrival.

Unit 4

Searching
1.Linear search

2.Binary Search 3

3.Interpolation Search

For searching follow this link

https://www.tutorialspoint.com/data_structures_algorithms/linear_search_algorith
m.htm

Sorting
Bubble Sort
Counting Sort
Heap Sort
Insertion Sort
Merge Sort
Quick Sort
Radix Sort
Selection Sort
Shell Sort

For sorting follow this link https://www.javatpoint.com/bubble-sort

Difference between Linear search and binary search

Basis of Linear search Binary search

comparison

Definition The linear search starts It finds the position of the searched element by
searching from the first finding the middle element of the array.
element and compares
each element with a
searched element till the
element is not found.

Sorted data In a linear search, the The pre-condition for the binary search is that the
elements don't need to be elements must be arranged in a sorted order.
 arranged in sorted order.

Implementation The linear search can be The implementation of binary search is limited as it
implemented on any linear can be implemented only on those data structures
data structure such as an that have two-way traversal.
array, linked list, etc.

Approach It is based on the It is based on the divide and conquer approach.

sequential approach.

Size It is preferrable for the It is preferrable for the large-size data sets.
small-sized data sets.

Efficiency It is less efficient in the It is more efficient in the case of large-size data sets.
case of large-size data
sets.

Worst-case In a linear search, the In a binary search, the worst-case scenario for finding
scenario worst- case scenario for the element is O(log2n).
finding the element is
O(n).

Best-case In a linear search, the In a binary search, the best-case scenario for finding
scenario best-case scenario for the first element in the list is O(1).
finding the first element in
the list is O(1).

Dimensional It can be implemented on It can be implemented only on a multidimensional

array both a single and array.
multidimensional array.

Unit 5

Graph

Graph
A graph can be defined as group of vertices and edges that are used to connect these vertices. A
graph can be seen as a cyclic tree, where the vertices (Nodes) maintain any complex relationship
among them instead of having parent child relationship.
Definition
A graph G can be defined as an ordered set G(V, E) where V(G) represents the set of vertices
and E(G) represents the set of edges which are used to connect these vertices.

A Graph G(V, E) with 5 vertices (A, B, C, D, E) and six edges ((A,B), (B,C), (C,E), (E,D),
(D,B), (D,A)) is shown in the following figure.

Directed and Undirected Graph

A graph can be directed or undirected. However, in an undirected graph, edges are not associated
with the directions with them. An undirected graph is shown in the above figure since its edges
are not attached with any of the directions. If an edge exists between vertex A and B then the
vertices can be traversed from B to A as well as A to B.

In a directed graph, edges form an ordered pair. Edges represent a specific path from some vertex
A to another vertex B. Node A is called initial node while node B is called terminal node.

A directed graph is shown in the following figure.

Graph Terminology
Path
A path can be defined as the sequence of nodes that are followed in order to reach some terminal
node V from the initial node U.

Closed Path
A path will be called as closed path if the initial node is same as terminal node. A path will be
closed path if V0=VN.

Simple Path
If all the nodes of the graph are distinct with an exception V0=VN, then such path P is called as
closed simple path.

Cycle
A cycle can be defined as the path which has no repeated edges or vertices except the first and
last vertices.

Connected Graph
A connected graph is the one in which some path exists between every two vertices (u, v) in V.
There are no isolated nodes in connected graph.
Complete Graph
A complete graph is the one in which every node is connected with all other nodes. A complete
graph contain n(n-1)/2 edges where n is the number of nodes in the graph.

Weighted Graph
In a weighted graph, each edge is assigned with some data such as length or weight. The weight
of an edge e can be given as w(e) which must be a positive (+) value indicating the cost of
traversing the edge.

Digraph
A digraph is a directed graph in which each edge of the graph is associated with some direction
and the traversing can be done only in the specified direction.

Loop
An edge that is associated with the similar end points can be called as Loop.

Adjacent Nodes
If two nodes u and v are connected via an edge e, then the nodes u and v are called as neighbours
or adjacent nodes.

Degree of the Node

A degree of a node is the number of edges that are connected with that node. A node
with degree 0 is called as isolated node.

Graph representation
In this article, we will discuss the ways to represent the graph. By Graph representation,
we simply mean the technique to be used to store some graph into the computer's
memory.

A graph is a data structure that consist a sets of vertices (called nodes) and edges. There
are two ways to store Graphs into the computer's memory:

o Sequential representation (or, Adjacency matrix representation)

o Linked list representation (or, Adjacency list representation)
In sequential representation, an adjacency matrix is used to store the graph. Whereas in
linked list representation, there is a use of an adjacency list to store the graph.

In this tutorial, we will discuss each one of them in detail.

Now, let's start discussing the ways of representing a graph in the data structure.

Sequential representation
In sequential representation, there is a use of an adjacency matrix to represent the
mapping between vertices and edges of the graph. We can use an adjacency matrix to
represent the undirected graph, directed graph, weighted directed graph, and weighted
undirected graph.

If adj[i][j] = w, it means that there is an edge exists from vertex i to vertex j with weight
w.

An entry Aij in the adjacency matrix representation of an undirected graph G will be 1 if

an edge exists between Vi and Vj. If an Undirected Graph G consists of n vertices, then
the adjacency matrix for that graph is n x n, and the matrix A = [aij] can be defined as -

aij = 1 {if there is a path exists from Vi to Vj}

aij = 0 {Otherwise}

It means that, in an adjacency matrix, 0 represents that there is no association exists

between the nodes, whereas 1 represents the existence of a path between two edges.

If there is no self-loop present in the graph, it means that the diagonal entries of the
adjacency matrix will be 0.

Now, let's see the adjacency matrix representation of an undirected graph.

In the above figure, an image shows the mapping among the vertices (A, B, C, D, E), and
this mapping is represented by using the adjacency matrix.

There exist different adjacency matrices for the directed and undirected graph. In a
directed graph, an entry Aij will be 1 only when there is an edge directed from Vi to Vj.

Adjacency matrix for a directed graph

In a directed graph, edges represent a specific path from one vertex to another vertex.
Suppose a path exists from vertex A to another vertex B; it means that node A is the
initial node, while node B is the terminal node.

Consider the below-directed graph and try to construct the adjacency matrix of it.
In the above graph, we can see there is no self-loop, so the diagonal entries of the
adjacent matrix are 0.

Adjacency matrix for a weighted directed graph

It is similar to an adjacency matrix representation of a directed graph except that instead

of using the '1' for the existence of a path, here we have to use the weight associated
with the edge. The weights on the graph edges will be represented as the entries of the
adjacency matrix. We can understand it with the help of an example. Consider the below
graph and its adjacency matrix representation. In the representation, we can see that the
weight associated with the edges is represented as the entries in the adjacency matrix.

In the above image, we can see that the adjacency matrix representation of the
weighted directed graph is different from other representations. It is because, in this
representation, the non-zero values are replaced by the actual weight assigned to the
edges.

Adjacency matrix is easier to implement and follow. An adjacency matrix can be used
when the graph is dense and a number of edges are large.

Though, it is advantageous to use an adjacency matrix, but it consumes more space.

Even if the graph is sparse, the matrix still consumes the same space.

Linked list representation

An adjacency list is used in the linked representation to store the Graph in the
computer's memory. It is efficient in terms of storage as we only have to store the values
for edges.

Let's see the adjacency list representation of an undirected graph.

In the above figure, we can see that there is a linked list or adjacency list for every node
of the graph. From vertex A, there are paths to vertex B and vertex D. These nodes are
linked to nodes A in the given adjacency list.

An adjacency list is maintained for each node present in the graph, which stores the
node value and a pointer to the next adjacent node to the respective node. If all the
adjacent nodes are traversed, then store the NULL in the pointer field of the last node of
the list.

The sum of the lengths of adjacency lists is equal to twice the number of edges present
in an undirected graph.

Now, consider the directed graph, and let's see the adjacency list representation of that
graph.
For a directed graph, the sum of the lengths of adjacency lists is equal to the number of
edges present in the graph.

Now, consider the weighted directed graph, and let's see the adjacency list
representation of that graph.

In the case of a weighted directed graph, each node contains an extra field that is called
the weight of the node.

In an adjacency list, it is easy to add a vertex. Because of using the linked list, it also
saves space.

Spanning tree
In this article, we will discuss the spanning tree and the minimum spanning tree. But
before moving directly towards the spanning tree, let's first see a brief description of the
graph and its types.
Graph
A graph can be defined as a group of vertices and edges to connect these vertices. The
types of graphs are given as follows -

o Undirected graph: An undirected graph is a graph in which all the

edges do not point to any particular direction, i.e., they are not
unidirectional; they are bidirectional. It can also be defined as a graph
with a set of V vertices and a set of E edges, each edge connecting
two different vertices.
o Connected graph: A connected graph is a graph in which a path
always exists from a vertex to any other vertex. A graph is connected
if we can reach any vertex from any other vertex by following edges in
either direction.
o Directed graph: Directed graphs are also known as digraphs. A graph
is a directed graph (or digraph) if all the edges present between any
vertices or nodes of the graph are directed or have a defined
direction.

Now, let's move towards the topic spanning tree.

What is a spanning tree?

A spanning tree can be defined as the subgraph of an undirected connected graph. It
includes all the vertices along with the least possible number of edges. If any vertex is
missed, it is not a spanning tree. A spanning tree is a subset of the graph that does not
have cycles, and it also cannot be disconnected.

A spanning tree consists of (n-1) edges, where 'n' is the number of vertices (or nodes).
Edges of the spanning tree may or may not have weights assigned to them. All the
possible spanning trees created from the given graph G would have the same number
of vertices, but the number of edges in the spanning tree would be equal to the number
of vertices in the given graph minus 1.

A complete undirected graph can have nn-2 number of spanning trees where n is the
number of vertices in the graph. Suppose, if n = 5, the number of maximum possible
spanning trees would be 55-2 = 125.
Applications of the spanning tree
Basically, a spanning tree is used to find a minimum path to connect all nodes of the
graph. Some of the common applications of the spanning tree are listed as follows -

o Cluster Analysis
o Civil network planning
o Computer network routing protocol

Now, let's understand the spanning tree with the help of an example.

Example of Spanning tree

Suppose the graph be -

As discussed above, a spanning tree contains the same number of vertices as the graph,
the number of vertices in the above graph is 5; therefore, the spanning tree will contain
5 vertices. The edges in the spanning tree will be equal to the number of vertices in the
graph minus 1. So, there will be 4 edges in the spanning tree.
Some of the possible spanning trees that will be created from the above graph are given
as follows -

Properties of spanning-tree
Some of the properties of the spanning tree are given as follows -

o There can be more than one spanning tree of a connected graph G.

o A spanning tree does not have any cycles or loop.
o A spanning tree is minimally connected, so removing one edge from
the tree will make the graph disconnected.
o A spanning tree is maximally acyclic, so adding one edge to the tree
will create a loop.
o There can be a maximum nn-2 number of spanning trees that can be
created from a complete graph.
o A spanning tree has n-1 edges, where 'n' is the number of nodes.
o If the graph is a complete graph, then the spanning tree can be
constructed by removing maximum (e-n+1) edges, where 'e' is the
number of edges and 'n' is the number of vertices.

So, a spanning tree is a subset of connected graph G, and there is no spanning tree of a
disconnected graph.
Minimum Spanning tree
A minimum spanning tree can be defined as the spanning tree in which the sum of the
weights of the edge is minimum. The weight of the spanning tree is the sum of the
weights given to the edges of the spanning tree. In the real world, this weight can be
considered as the distance, traffic load, congestion, or any random value.

Example of minimum spanning tree

Let's understand the minimum spanning tree with the help of an example.

The sum of the edges of the above graph is 16. Now, some of the possible spanning
trees created from the above graph are -
So, the minimum spanning tree that is selected from the above spanning trees for the
given weighted graph is -

Applications of minimum spanning tree

The applications of the minimum spanning tree are given as follows -

o Minimum spanning tree can be used to design water-supply

networks, telecommunication networks, and electrical grids.
o It can be used to find paths in the map.

Algorithms for Minimum spanning tree

A minimum spanning tree can be found from a weighted graph by using the algorithms
given below -

o Prim's Algorithm
o Kruskal's Algorithm

Let's see a brief description of both of the algorithms listed above.

Prim's algorithm - It is a greedy algorithm that starts with an empty spanning tree. It is
used to find the minimum spanning tree from the graph. This algorithm finds the subset
of edges that includes every vertex of the graph such that the sum of the weights of the
edges can be minimized.

To learn more about the prim's algorithm, you can click the below link -
https://www.javatpoint.com/prim-algorithm

Kruskal's algorithm - This algorithm is also used to find the minimum spanning tree for
a connected weighted graph. Kruskal's algorithm also follows greedy approach, which
finds an optimum solution at every stage instead of focusing on a global optimum.

To learn more about the prim's algorithm, you can click the below link -
https://www.javatpoint.com/kruskal-algorithm

So, that's all about the article. Hope the article will be helpful and informative to you.
Here, we have discussed spanning tree and minimum spanning tree along with their
properties, examples, and applications.

BFS vs. DFS

Before looking at the differences between BFS and DFS, we first should know about BFS
and DFS separately.

What is BFS?
BFS

stands for Breadth First Search. It is also known as level order traversal. The
Queue data structure is used for the Breadth First Search traversal. When we use
the BFS algorithm for the traversal in a graph, we can consider any node as a root
node.

Let's consider the below graph for the breadth first search traversal.
Suppose we consider node 0 as a root node. Therefore, the traversing would be started
from node 0.

Once node 0 is removed from the Queue, it gets printed and marked as a visited node.

Once node 0 gets removed from the Queue, then the adjacent nodes of node 0 would
be inserted in a Queue as shown below:

Now the node 1 will be removed from the Queue; it gets printed and marked as a
visited node
Once node 1 gets removed from the Queue, then all the adjacent nodes of a node 1 will
be added in a Queue. The adjacent nodes of node 1 are 0, 3, 2, 6, and 5. But we have to
insert only unvisited nodes in a Queue. Since nodes 3, 2, 6, and 5 are unvisited;
therefore, these nodes will be added in a Queue as shown below:

The next node is 3 in a Queue. So, node 3 will be removed from the Queue, it gets
printed and marked as visited as shown below:

Once node 3 gets removed from the Queue, then all the adjacent nodes of node 3
except the visited nodes will be added in a Queue. The adjacent nodes of node 3 are 0,
1, 2, and 4. Since nodes 0, 1 are already visited, and node 2 is present in a Queue;
therefore, we need to insert only node 4 in a Queue.

Now, the next node in the Queue is 2. So, 2 would be deleted from the Queue. It gets
printed and marked as visited as shown below:
Once node 2 gets removed from the Queue, then all the adjacent nodes of node 2
except the visited nodes will be added in a Queue. The adjacent nodes of node 2 are 1,
3, 5, 6, and 4. Since the nodes 1 and 3 have already been visited, and 4, 5, 6 are already
added in the Queue; therefore, we do not need to insert any node in the Queue.

The next element is 5. So, 5 would be deleted from the Queue. It gets printed and
marked as visited as shown below:

Once node 5 gets removed from the Queue, then all the adjacent nodes of node 5
except the visited nodes will be added in the Queue. The adjacent nodes of node 5 are 1
and 2. Since both the nodes have already been visited; therefore, there is no vertex to be
inserted in a Queue.

The next node is 6. So, 6 would be deleted from the Queue. It gets printed and marked
as visited as shown below:
Once the node 6 gets removed from the Queue, then all the adjacent nodes of node 6
except the visited nodes will be added in the Queue. The adjacent nodes of node 6 are 1
and 4. Since the node 1 has already been visited and node 4 is already added in the
Queue; therefore, there is not vertex to be inserted in the Queue.

The next element in the Queue is 4. So, 4 would be deleted from the Queue. It gets
printed and marked as visited.

Once the node 4 gets removed from the Queue, then all the adjacent nodes of node 4
except the visited nodes will be added in the Queue. The adjacent nodes of node 4 are
3, 2, and 6. Since all the adjacent nodes have already been visited; so, there is no vertex
to be inserted in the Queue.

What is DFS?
DFS

stands for Depth First Search. In DFS traversal, the stack data structure is used,
which works on the LIFO (Last In First Out) principle. In DFS, traversing can be
started from any node, or we can say that any node can be considered as a root
node until the root node is not mentioned in the problem.

In the case of BFS, the element which is deleted from the Queue, the adjacent nodes of
the deleted node are added to the Queue. In contrast, in DFS, the element which is
removed from the stack, then only one adjacent node of a deleted node is added in the
stack.

Let's consider the below graph for the Depth First Search traversal.
Consider node 0 as a root node.

First, we insert the element 0 in the stack as shown below:

The node 0 has two adjacent nodes, i.e., 1 and 3. Now we can take only one adjacent
node, either 1 or 3, for traversing. Suppose we consider node 1; therefore, 1 is inserted
in a stack and gets printed as shown below:
Now we will look at the adjacent vertices of node 1. The unvisited adjacent vertices of
node 1 are 3, 2, 5 and 6. We can consider any of these four vertices. Suppose we take
node 3 and insert it in the stack as shown below:

Consider the unvisited adjacent vertices of node 3. The unvisited adjacent vertices of
node 3 are 2 and 4. We can take either of the vertices, i.e., 2 or 4. Suppose we take
vertex 2 and insert it in the stack as shown below:
The unvisited adjacent vertices of node 2 are 5 and 4. We can choose either of the
vertices, i.e., 5 or 4. Suppose we take vertex 4 and insert in the stack as shown below:

Now we will consider the unvisited adjacent vertices of node 4. The unvisited adjacent
vertex of node 4 is node 6. Therefore, element 6 is inserted into the stack as shown
below:
After inserting element 6 in the stack, we will look at the unvisited adjacent vertices of
node 6. As there is no unvisited adjacent vertices of node 6, so we cannot move beyond
node 6. In this case, we will perform backtracking. The topmost element, i.e., 6 would
be popped out from the stack as shown below:
The topmost element in the stack is 4. Since there are no unvisited adjacent vertices left
of node 4; therefore, node 4 is popped out from the stack as shown below:
The next topmost element in the stack is 2. Now, we will look at the unvisited adjacent
vertices of node 2. Since only one unvisited node, i.e., 5 is left, so node 5 would be
pushed into the stack above 2 and gets printed as shown below:
Now we will check the adjacent vertices of node 5, which are still unvisited. Since there is
no vertex left to be visited, so we pop the element 5 from the stack as shown below:

We cannot move further 5, so we need to perform backtracking. In backtracking, the

topmost element would be popped out from the stack. The topmost element is 5 that
would be popped out from the stack, and we move back to node 2 as shown below:
Now we will check the unvisited adjacent vertices of node 2. As there is no adjacent
vertex left to be visited, so we perform backtracking. In backtracking, the topmost
element, i.e., 2 would be popped out from the stack, and we move back to the node 3 as
shown below:
Now we will check the unvisited adjacent vertices of node 3. As there is no adjacent
vertex left to be visited, so we perform backtracking. In backtracking, the topmost
element, i.e., 3 would be popped out from the stack and we move back to node 1 as
shown below:
After popping out element 3, we will check the unvisited adjacent vertices of node 1.
Since there is no vertex left to be visited; therefore, the backtracking will be performed.
In backtracking, the topmost element, i.e., 1 would be popped out from the stack, and
we move back to node 0 as shown below:
We will check the adjacent vertices of node 0, which are still unvisited. As there is no
adjacent vertex left to be visited, so we perform backtracking. In this, only one element,
i.e., 0 left in the stack, would be popped out from the stack as shown below:
As we can observe in the above figure that the stack is empty. So, we have to stop the
DFS traversal here, and the elements which are printed is the result of the DFS traversal.

Differences between BFS and DFS

The following are the differences between the BFS and DFS:

BFS DFS

Full form BFS stands for Breadth First DFS stands for Depth First Search.
Search.

Technique It a vertex-based technique It is an edge-based technique because

to find the shortest path in a the vertices along the edge are
graph. explored first from the starting to the
end node.

Definition BFS is a traversal technique DFS is also a traversal technique in

in which all the nodes of the which traversal is started from the
same level are explored first, root node and explore the nodes as
 and then we move to the far as possible until we reach the node
next level. that has no unvisited adjacent nodes.

Data Structure Queue data structure is used Stack data structure is used for the
for the BFS traversal. BFS traversal.

Backtracking BFS does not use the DFS uses backtracking to traverse all
backtracking concept. the unvisited nodes.

Number of BFS finds the shortest path In DFS, a greater number of edges are
edges having a minimum number required to traverse from the source
of edges to traverse from the vertex to the destination vertex.
source to the destination
vertex.

Optimality BFS traversal is optimal for DFS traversal is optimal for those
those vertices which are to graphs in which solutions are away
be searched closer to the from the source vertex.
source vertex.

Speed BFS is slower than DFS. DFS is faster than BFS.

Suitability for It is not suitable for the It is suitable for the decision tree.
decision tree decision tree because it Based on the decision, it explores all
requires exploring all the the paths. When the goal is found, it
neighboring nodes first. stops its traversal.

Memory It is not memory efficient as It is memory efficient as it requires

it requires more memory
efficient than DFS. less memory than BFS.

Shortest Path Algorithms

1. Floyd Warshall’s

2. Dijkstra’s Algorithm

3. Bellman Ford

Above all three covered in class with example.

All the best