Data structure question with solution

 Note remember page numbers

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 -

• 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.
• 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.
• 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

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 n^n-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 5^5-2 = 125.

In this program, we need to find out the maximum height of the binary tree. The height of the binary tree can be defined as the number of nodes between root and a leaf. Maximum height will be the number of levels between root and deepest leaf. To solve this problem, we traverse through the left subtree and calculate the height of the left subtree. Again, calculate the height of the right subtree by traversing through it. Maximum height will be maximum of the height of the left subtree and right subtree.

Height of left subtree is 2.
Height of right subtree is 4.
MaxHeight = Max(leftHeight, rightHeight) + 1; Here, 1 Represents root node's height

The maximum height of the given binary tree is (4 + 1) = 5 denoted by white dotted line.

A graph G is a tree if and only if it is minimally connected.

Proof: Let the graph G is minimally connected, i.e; removal of one edge make it disconnected. Therefore, there is no circuit. Hence graph G is a tree

A graph G = (V, E) consists of a set of vertices V = { V1, V2, . . . } and set of edges E = { E1, E2, . . . }. The set of unordered pairs of distinct vertices whose elements are called edges of graph G such that each edge is identified with an unordered pair (Vi, Vj) of vertices.
The vertices (Vi, Vj) are said to be adjacent if there is an edge Ek which is associated to Vi and Vj. In such a case Vi and Vj are called end points and the edge Ek is said to be connect/joint of Vi and Vj

What is an Algorithm?

An algorithm is a process or a set of rules required to perform calculations or some other problem-solving operations especially by a computer. The formal definition of an algorithm is that it contains the finite set of instructions which are being carried in a specific order to perform the specific task. It is not the complete program or code; it is just a solution (logic) of a problem, which can be represented either as an informal description using a Flowchart or Pseudocode.

computational complexity that describes the amount of computer time it takes to run an algorithm. 

Recurrence Relation

A recurrence is an equation or inequality that describes a function in terms of its values on smaller inputs. To solve a Recurrence Relation means to obtain a function defined on the natural numbers that satisfy the recurrence.

1. First Iteration (Compare and Swap)

1. Starting from the first index, compare the first and the second elements.
2. If the first element is greater than the second element, they are swapped.
3. Now, compare the second and the third elements. Swap them if they are not in order.
4. The above process goes on until the last element.

2. Remaining Iteration

The same process goes on for the remaining iterations.

After each iteration, the largest element among the unsorted elements is placed at the end.

In each iteration, the comparison takes place up to the last unsorted element.

The array is sorted when all the unsorted elements are placed at their correct positions.

Linear Search vs Binary Search

Before understanding the differences between the linear and binary search, we should first know the linear search and binary search separately.

What is a linear search?

A linear search is also known as a sequential search that simply scans each element at a time. Suppose we want to search an element in an array or list; we simply calculate its length and do not jump at any item.

Step 1: Start Step 2: Input Sorted array in "a[]" and element to be searched in "x" and size of array in "size" Step 3: Initialize low=0, high=size-1 Step 4: Repeat until low>=high Step 4.1: mid=(low+high)/2 Step 4.2: If a[mid] is equal to x, then, print index value of mid and Goto step 6 Else If a[mid]<x low=mid+1 else high=mid-1 Step 5: Print x not found in the list Stop 6: Stop