Tag: Data Structures and Algorithms

Tree Data Structure | Tree Terminology

Data Structures

Tree Data Structure-

 

Tree data structure may be defined as-

 

Tree is a non-linear data structure which organizes data in a hierarchical structure and this is a recursive definition.

OR

A tree is a connected graph without any circuits.

OR

If in a graph, there is one and only one path between every pair of vertices, then graph is called as a tree.

 

Example-

 

 

Properties-

 

The important properties of tree data structure are-

  • There is one and only one path between every pair of vertices in a tree.
  • A tree with n vertices has exactly (n-1) edges.
  • A graph is a tree if and only if it is minimally connected.
  • Any connected graph with n vertices and (n-1) edges is a tree.

 

To gain better understanding about Tree Data Structure,

Watch this Video Lecture

 

Tree Terminology-

 

The important terms related to tree data structure are-

 

 

1. Root-

 

  • The first node from where the tree originates is called as a root node.
  • In any tree, there must be only one root node.
  • We can never have multiple root nodes in a tree data structure.

 

Example-

 

 

Here, node A is the only root node.

 

2. Edge-

 

  • The connecting link between any two nodes is called as an edge.
  • In a tree with n number of nodes, there are exactly (n-1) number of edges.

 

Example-

 

 

3. Parent-

 

  • The node which has a branch from it to any other node is called as a parent node.
  • In other words, the node which has one or more children is called as a parent node.
  • In a tree, a parent node can have any number of child nodes.

 

Example-

 

 

Here,

  • Node A is the parent of nodes B and C
  • Node B is the parent of nodes D, E and F
  • Node C is the parent of nodes G and H
  • Node E is the parent of nodes I and J
  • Node G is the parent of node K

 

4. Child-

 

  • The node which is a descendant of some node is called as a child node.
  • All the nodes except root node are child nodes.

 

Example-

 

 

Here,

  • Nodes B and C are the children of node A
  • Nodes D, E and F are the children of node B
  • Nodes G and H are the children of node C
  • Nodes I and J are the children of node E
  • Node K is the child of node G

 

5. Siblings-

 

  • Nodes which belong to the same parent are called as siblings.
  • In other words, nodes with the same parent are sibling nodes.

 

Example-

 

 

Here,

  • Nodes B and C are siblings
  • Nodes D, E and F are siblings
  • Nodes G and H are siblings
  • Nodes I and J are siblings

 

6. Degree-

 

  • Degree of a node is the total number of children of that node.
  • Degree of a tree is the highest degree of a node among all the nodes in the tree.

 

Example-

 

 

Here,

  • Degree of node A = 2
  • Degree of node B = 3
  • Degree of node C = 2
  • Degree of node D = 0
  • Degree of node E = 2
  • Degree of node F = 0
  • Degree of node G = 1
  • Degree of node H = 0
  • Degree of node I = 0
  • Degree of node J = 0
  • Degree of node K = 0

 

7. Internal Node-

 

  • The node which has at least one child is called as an internal node.
  • Internal nodes are also called as non-terminal nodes.
  • Every non-leaf node is an internal node.

 

Example-

 

 

Here, nodes A, B, C, E and G are internal nodes.

 

8. Leaf Node-

 

  • The node which does not have any child is called as a leaf node.
  • Leaf nodes are also called as external nodes or terminal nodes.

 

Example-

 

 

Here, nodes D, I, J, F, K and H are leaf nodes.

 

9. Level-

 

  • In a tree, each step from top to bottom is called as level of a tree.
  • The level count starts with 0 and increments by 1 at each level or step.

 

Example-

 

 

10. Height-

 

  • Total number of edges that lies on the longest path from any leaf node to a particular node is called as height of that node.
  • Height of a tree is the height of root node.
  • Height of all leaf nodes = 0

 

Example-

 

 

Here,

  • Height of node A = 3
  • Height of node B = 2
  • Height of node C = 2
  • Height of node D = 0
  • Height of node E = 1
  • Height of node F = 0
  • Height of node G = 1
  • Height of node H = 0
  • Height of node I = 0
  • Height of node J = 0
  • Height of node K = 0

 

11. Depth-

 

  • Total number of edges from root node to a particular node is called as depth of that node.
  • Depth of a tree is the total number of edges from root node to a leaf node in the longest path.
  • Depth of the root node = 0
  • The terms “level” and “depth” are used interchangeably.

 

Example-

 

 

Here,

  • Depth of node A = 0
  • Depth of node B = 1
  • Depth of node C = 1
  • Depth of node D = 2
  • Depth of node E = 2
  • Depth of node F = 2
  • Depth of node G = 2
  • Depth of node H = 2
  • Depth of node I = 3
  • Depth of node J = 3
  • Depth of node K = 3

 

12. Subtree-

 

  • In a tree, each child from a node forms a subtree recursively.
  • Every child node forms a subtree on its parent node.

 

Example-

 

 

13. Forest-

 

A forest is a set of disjoint trees.

 

Example-

 

 

To gain better understanding about Tree Terminology,

Watch this Video Lecture

 

Download Handwritten Notes Here-

 

 

Next Article- Binary Tree | Types of Binary Trees

 

Get more notes and other study material of Data Structures.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Difference Between Prim’s and Kruskal’s Algorithm

Design & Analysis of Algorithms

Prim’s and Kruskal’s Algorithms-

 

Before you go through this article, make sure that you have gone through the previous articles on Prim’s Algorithm & Kruskal’s Algorithm.

 

We have discussed-

  • Prim’s and Kruskal’s Algorithm are the famous greedy algorithms.
  • They are used for finding the Minimum Spanning Tree (MST) of a given graph.
  • To apply these algorithms, the given graph must be weighted, connected and undirected.

 

Some important concepts based on them are-

 

Concept-01:

 

If all the edge weights are distinct, then both the algorithms are guaranteed to find the same MST.

 

Example-

 

Consider the following example-

 

 

Here, both the algorithms on the above given graph produces the same MST as shown.

 

Concept-02:

 

  • If all the edge weights are not distinct, then both the algorithms may not always produce the same MST.
  • However, cost of both the MSTs would always be same in both the cases.

 

Example-

 

Consider the following example-

 

 

Here, both the algorithms on the above given graph produces different MSTs as shown but the cost is same in both the cases.

 

Concept-03:

 

Kruskal’s Algorithm is preferred when-

  • The graph is sparse.
  • There are less number of edges in the graph like E = O(V)
  • The edges are already sorted or can be sorted in linear time.

 

Prim’s Algorithm is preferred when-

  • The graph is dense.
  • There are large number of edges in the graph like E = O(V2).

 

Concept-04:

 

Difference between Prim’s Algorithm and Kruskal’s Algorithm-

 

Prim’s Algorithm Kruskal’s Algorithm
The tree that we are making or growing always remains connected. The tree that we are making or growing usually remains disconnected.
Prim’s Algorithm grows a solution from a random vertex by adding the next cheapest vertex to the existing tree. Kruskal’s Algorithm grows a solution from the cheapest edge by adding the next cheapest edge to the existing tree / forest.
Prim’s Algorithm is faster for dense graphs. Kruskal’s Algorithm is faster for sparse graphs.

 

To gain better understanding about Difference between Prim’s and Kruskal’s Algorithm,

Watch this Video Lecture

 

Next Article- Linear Search

 

Get more notes and other study material of Design and Analysis of Algorithms.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Kruskal’s Algorithm | Kruskal’s Algorithm Example | Problems

Design & Analysis of Algorithms

Kruskal’s Algorithm-

 

  • Kruskal’s Algorithm is a famous greedy algorithm.
  • It is used for finding the Minimum Spanning Tree (MST) of a given graph.
  • To apply Kruskal’s algorithm, the given graph must be weighted, connected and undirected.

 

Kruskal’s Algorithm Implementation-

 

The implementation of Kruskal’s Algorithm is explained in the following steps-

 

Step-01:

 

  • Sort all the edges from low weight to high weight.

 

Step-02:

 

  • Take the edge with the lowest weight and use it to connect the vertices of graph.
  • If adding an edge creates a cycle, then reject that edge and go for the next least weight edge.

 

Step-03:

 

  • Keep adding edges until all the vertices are connected and a Minimum Spanning Tree (MST) is obtained.

 

Thumb Rule to Remember

 

The above steps may be reduced to the following thumb rule-

  • Simply draw all the vertices on the paper.
  • Connect these vertices using edges with minimum weights such that no cycle gets formed.

 

Kruskal’s Algorithm Time Complexity-

 

Worst case time complexity of Kruskal’s Algorithm

= O(ElogV) or O(ElogE)

 

Analysis-

 

  • The edges are maintained as min heap.
  • The next edge can be obtained in O(logE) time if graph has E edges.
  • Reconstruction of heap takes O(E) time.
  • So, Kruskal’s Algorithm takes O(ElogE) time.
  • The value of E can be at most O(V2).
  • So, O(logV) and O(logE) are same.

 

Special Case-

 

  • If the edges are already sorted, then there is no need to construct min heap.
  • So, deletion from min heap time is saved.
  • In this case, time complexity of Kruskal’s Algorithm = O(E + V)

 

Also Read- Prim’s Algorithm

 

PRACTICE PROBLEMS BASED ON KRUSKAL’S ALGORITHM-

 

Problem-01:

 

Construct the minimum spanning tree (MST) for the given graph using Kruskal’s Algorithm-

 

 

Solution-

 

To construct MST using Kruskal’s Algorithm,

  • Simply draw all the vertices on the paper.
  • Connect these vertices using edges with minimum weights such that no cycle gets formed.

 

Step-01:

 

 

Step-02:

 

 

Step-03:

 

 

Step-04:

 

 

Step-05:

 

 

Step-06:

 

 

Step-07:

 

 

Since all the vertices have been connected / included in the MST, so we stop.

Weight of the  MST

= Sum of all edge weights

= 10 + 25 + 22 + 12 + 16 + 14

= 99 units

 

To gain better understanding about Kruskal’s Algorithm,

Watch this Video Lecture

 

To practice previous years GATE problems based on Kruskal’s Algorithm,

Watch this Video Lecture

 

Next Article- Prim’s Algorithm Vs Kruskal’s Algorithm

 

Get more notes and other study material of Design and Analysis of Algorithms.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Prim’s Algorithm | Prim’s Algorithm Example | Problems

Design & Analysis of Algorithms

Prim’s Algorithm-

 

  • Prim’s Algorithm is a famous greedy algorithm.
  • It is used for finding the Minimum Spanning Tree (MST) of a given graph.
  • To apply Prim’s algorithm, the given graph must be weighted, connected and undirected.

 

Prim’s Algorithm Implementation-

 

The implementation of Prim’s Algorithm is explained in the following steps-

 

Step-01:

 

  • Randomly choose any vertex.
  • The vertex connecting to the edge having least weight is usually selected.

 

Step-02:

 

  • Find all the edges that connect the tree to new vertices.
  • Find the least weight edge among those edges and include it in the existing tree.
  • If including that edge creates a cycle, then reject that edge and look for the next least weight edge.

 

Step-03:

 

  • Keep repeating step-02 until all the vertices are included and Minimum Spanning Tree (MST) is obtained.

 

Prim’s Algorithm Time Complexity-

 

Worst case time complexity of Prim’s Algorithm is-

  • O(ElogV) using binary heap
  • O(E + VlogV) using Fibonacci heap

 

Time Complexity Analysis

 

  • If adjacency list is used to represent the graph, then using breadth first search, all the vertices can be traversed in O(V + E) time.
  • We traverse all the vertices of graph using breadth first search and use a min heap for storing the vertices not yet included in the MST.
  • To get the minimum weight edge, we use min heap as a priority queue.
  • Min heap operations like extracting minimum element and decreasing key value takes O(logV) time.

 

So, overall time complexity

= O(E + V) x O(logV)

= O((E + V)logV)

= O(ElogV)

 

This time complexity can be improved and reduced to O(E + VlogV) using Fibonacci heap.

 

PRACTICE PROBLEMS BASED ON PRIM’S ALGORITHM-

 

Problem-01:

 

Construct the minimum spanning tree (MST) for the given graph using Prim’s Algorithm-

 

 

Solution-

 

The above discussed steps are followed to find the minimum cost spanning tree using Prim’s Algorithm-

 

Step-01:

 

 

Step-02:

 

 

Step-03:

 

 

Step-04:

 

 

Step-05:

 

 

Step-06:

 

 

Since all the vertices have been included in the MST, so we stop.

 

Now, Cost of Minimum Spanning Tree

= Sum of all edge weights

= 10 + 25 + 22 + 12 + 16 + 14

= 99 units

 

Problem-02:

 

Using Prim’s Algorithm, find the cost of minimum spanning tree (MST) of the given graph-

 

 

Solution-

 

The minimum spanning tree obtained by the application of Prim’s Algorithm on the given graph is as shown below-

 

 

Now, Cost of Minimum Spanning Tree

= Sum of all edge weights

= 1 + 4 + 2 + 6 + 3 + 10

= 26 units

 

To gain better understanding about Prim’s Algorithm,

Watch this Video Lecture

 

To practice previous years GATE problems based on Prim’s Algorithm,

Watch this Video Lecture

 

Next Article- Kruskal’s Algorithm

 

Get more notes and other study material of Design and Analysis of Algorithms.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Topological Sort | Topological Sort Examples

Design & Analysis of Algorithms

Topological Sort-

 

Topological Sort is a linear ordering of the vertices in such a way that

if there is an edge in the DAG going from vertex ‘u’ to vertex ‘v’,

then ‘u’ comes before ‘v’ in the ordering.

 

It is important to note that-

  • Topological Sorting is possible if and only if the graph is a Directed Acyclic Graph.
  • There may exist multiple different topological orderings for a given directed acyclic graph.

 

Topological Sort Example-

 

Consider the following directed acyclic graph-

 

 

For this graph, following 4 different topological orderings are possible-

  • 1 2 3 4 5 6
  • 1 2 3 4 6 5
  • 1 3 2 4 5 6
  • 1 3 2 4 6 5

 

Applications of Topological Sort-

 

Few important applications of topological sort are-

  • Scheduling jobs from the given dependencies among jobs
  • Instruction Scheduling
  • Determining the order of compilation tasks to perform in makefiles
  • Data Serialization

 

PRACTICE PROBLEMS BASED ON TOPOLOGICAL SORT-

 

Problem-01:

 

Find the number of different topological orderings possible for the given graph-

 

 

Solution-

 

The topological orderings of the above graph are found in the following steps-

 

Step-01:

 

Write in-degree of each vertex-

 

 

Step-02:

 

  • Vertex-A has the least in-degree.
  • So, remove vertex-A and its associated edges.
  • Now, update the in-degree of other vertices.

 

 

Step-03:

 

  • Vertex-B has the least in-degree.
  • So, remove vertex-B and its associated edges.
  • Now, update the in-degree of other vertices.

 

 

Step-04:

 

There are two vertices with the least in-degree. So, following 2 cases are possible-

 

In case-01,

  • Remove vertex-C and its associated edges.
  • Then, update the in-degree of other vertices.

 

In case-02,

  • Remove vertex-D and its associated edges.
  • Then, update the in-degree of other vertices.

 

 

Step-05:

 

Now, the above two cases are continued separately in the similar manner.

 

In case-01,

  • Remove vertex-D since it has the least in-degree.
  • Then, remove the remaining vertex-E.

 

In case-02,

  • Remove vertex-C since it has the least in-degree.
  • Then, remove the remaining vertex-E.

 

 

Conclusion-

 

For the given graph, following 2 different topological orderings are possible-

  • A B C D E
  • A B D C E

 

Problem-02:

 

Find the number of different topological orderings possible for the given graph-

 

 

Solution-

 

The topological orderings of the above graph are found in the following steps-

 

Step-01:

 

Write in-degree of each vertex-

 

 

Step-02:

 

  • Vertex-1 has the least in-degree.
  • So, remove vertex-1 and its associated edges.
  • Now, update the in-degree of other vertices.

 

 

Step-03:

 

There are two vertices with the least in-degree. So, following 2 cases are possible-

 

In case-01,

  • Remove vertex-2 and its associated edges.
  • Then, update the in-degree of other vertices.

 

In case-02,

  • Remove vertex-3 and its associated edges.
  • Then, update the in-degree of other vertices.

 

 

Step-04:

 

Now, the above two cases are continued separately in the similar manner.

 

In case-01,

  • Remove vertex-3 since it has the least in-degree.
  • Then, update the in-degree of other vertices.

 

In case-02,

  • Remove vertex-2 since it has the least in-degree.
  • Then, update the in-degree of other vertices.

 

 

Step-05:

 

In case-01,

  • Remove vertex-4 since it has the least in-degree.
  • Then, update the in-degree of other vertices.

 

In case-02,

  • Remove vertex-4 since it has the least in-degree.
  • Then, update the in-degree of other vertices.

 

 

Step-06:

 

In case-01,

  • There are 2 vertices with the least in-degree.
  • So, 2 cases are possible.
  • Any of the two vertices may be taken first.

 

Same is with case-02.

 

 

Conclusion-

 

For the given graph, following 4 different topological orderings are possible-

  • 1 2 3 4 5 6
  • 1 2 3 4 6 5
  • 1 3 2 4 5 6
  • 1 3 2 4 6 5

 

Problem-03:

 

Consider the directed graph given below. Which of the following statements is true?

 

 

  1. The graph does not have any topological ordering.
  2. Both PQRS and SRPQ are topological orderings.
  3. Both PSRQ and SPRQ are topological orderings.
  4. PSRQ is the only topological ordering.

 

Solution-

 

  • The given graph is a directed acyclic graph.
  • So, topological orderings exist.
  • P and S must appear before R and Q in topological orderings as per the definition of topological sort.

 

Thus, Correct option is (C).

 

Problem-04:

 

Consider the following directed graph-

 

 

The number of different topological orderings of the vertices of the graph is ________ ?

 

Solution-

 

Number of different topological orderings possible = 6.

Thus, Correct answer is 6.

 

(The solution is explained in detail in the linked video lecture.)

 

To gain better understanding about Topological Sort,

Watch this Video Lecture

 

To practice previous years GATE problems on Topological Sort,

Watch this Video Lecture

 

Next Article- Shortest Path Problems

 

Other Popular Sorting Algorithms-

 

 

Get more notes and other study material of Design and Analysis of Algorithms.

Watch video lectures by visiting our YouTube channel LearnVidFun.