Graph Search MCQ Quiz in తెలుగు - Objective Question with Answer for Graph Search - ముఫ్త్ [PDF] డౌన్‌లోడ్ కరెన్

• Dijkstra’s Shortest Path uses the greedy method to find the shortest path of a graph G(V, E).
• Floyd-Warshall algorithm uses dynamic programming approach to find all-pairs shortest paths of a graph G(V, E).
• Binary search on a sorted array uses divide and conquer technique to search an element
• Backtracking search on a graph is implemented using a depth-first search technique

Given any vertex, Only scan of the particular row/particular column is required to get the in degree and out degree:

int find_deg(int v, int size, int mat[])

  {

     int sum = 0;

      for(int i = 0; i

      sum+=mat[v][i];

for(int i = 0; i< size ;i++)

      sum+=mat[i][v]

      return sum;

}

Hence complexity is O(n).

The correct answer is options 1, 2 and 4.

Concept:

Depth-first search:

An algorithm for exploring a graph is called depth-first search (DFS). DFS performs the traversal using a stack data structure. More than one DFS traversal may be performed on a graph.

Option 1: Topological Sorting.

Topological Sorting problem that uses the depth-first search. A directed graph's topological sort or topological order is a linear arrangement of its vertices where u comes before v for each directed edge (UV) connecting u and v. Every order of depth-first search order is a topological sort.

Option 2: Detecting cycle in a graph.

Detecting cycle in a graph that uses the depth-first search. Check back edges of each tree for cycles to find them. Keep track of the vertices that are currently in the recursion stack of the DFS traversal algorithm to find back edges. There is a cycle in the tree if a vertex that has previously been traversed by the recursion stack is reached.

Option 3: Finding the negative weight cycle.

Finding the negative weight cycle that uses Dynamic programming. Bellman-Ford algorithm that determines whether a negative cycle is present. Perform the Nth iteration of Bellman-Ford and choose a vertex from any edge that is loosened in this iteration to output the negative cycles. The negative cycle may be generated by using this vertex and its predecessors.

Option 4: Finding strongly connected components of a graph.

Finding strongly connected components of a graph uses the depth-first search. If there is a path connecting every vertex in a directed graph to every other vertex, the graph is said to be highly linked.

Hence the correct answer is to find the negative weight cycle.

Concept:

Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures.

It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a 'search key'), and explores all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level.

Explanation:

Since in all the option traversal start with node A, Therefore A is the root node

Statement I: A B C F G E D

A → B → C → F → G (not allowed)

∵ D is at distance 2 and G is at distance 3 from root node

Statement II: A B C G F E D

A → B → C → G (not allowed)

∵ D, E and F are at distance 2 and G is at distance 3 from the root node

Statement III: A B D E C F G

A→ B → D (not possible)

Diagram: Consider that vertex is at distance 3 from the root, that is, height = 3

Traverse using BFS algorithm, number the node accordingly

Maximum value = x = 15

Minimum value = y = 8

∴ x – y = 15 – 8

(2³⁺¹ – 1) – 2³ = (2³⁺¹ – 1) – 2³ = 15 – 8 = 7

Shortcut:

In question h = 5,

(2^h+1 – 1) – 2^h = (2⁵⁺¹ – 1) – 2⁵ = 31

Answer: Option 1

Explanation:

Enqueue node 1 in the queue.

Queue: 1

Mark it as visited. Dequeue 1 and enqueue its non-visited adjacent nodes in ascending order.

Queue: 8 5 4 3 2

Mark 8 as visited. Dequeue 8 and enqueue its non-visited adjacent nodes in ascending order.

Queue: 5 4 3 2 7 6

Mark 5 as visited. Dequeue 5 and enqueue its non-visited adjacent nodes.

Queue: 4 3 2 7 6

Mark 4 as visited. Dequeue 4 and enqueue its non-visited adjacent nodes.

Queue: 3 2 7 6

Mark 3 as visited. Dequeue 3 and enqueue its non-visited adjacent nodes.

Queue: 2 7 6

Hence Option is the correct answer.

Total no of nodes  = 20.

The correct answer is 4.

Concept:

Topological orderings:

Topological sort is a linear arrangement of the vertices in such a way that if there is an edge in the DAG leading from vertex 'u' to vertex 'v', then 'u' comes before 'v' in the ordering.

Note:

• Start a node whose in-degree is zero.
• End a node whose out-degree is zero.

There are four possible topological orderings for this graph:

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

Hence the correct answer is 4.

The correct answer is option 2.

Concept:

Prim’s algorithm:

Prim's Method is a greedy algorithm that finds the shortest spanning tree. It is comparable to the shortest path first algorithm. After a brief overview of the spanning trees, Spanning trees are a subset of Graphs that cover all vertices with the fewest possible edges.

Prim’s algorithm steps:

1) 

2) 

3) 

4) 

5) 

6) 

1,2,5,6,9,8 edges are added to the spanning tree. 

Hence the correct answer is 1,2,5,6,9,8.

The correct answer is option 3.

Concept:

Min-and max-heaps:

It's either a Min Heap or a Max Heap is a Binary Heap. In a Min Binary Heap, the root key must be the smallest of all the keys in the Binary Heap. For all nodes in a Binary Tree, the same property must be true recursively. Similarly, with a Max Binary Heap, the root key must be the largest of all the keys in the Binary Heap. For all nodes in a Binary Tree, the same property must be true recursively.

Min heap and max-heap are implemented by a Priority queue. The default PriorityQueue is implemented with Min-Heap, that is the top element is the minimum one in the heap.

P. Min-and max-heaps = 2. Priority queue implementations.

B-tress:

A B-tree is a self-balancing tree data structure that keeps sorted data and permits logarithmic time searches, sequential access, insertions, and removals. B-tresses are used to implement a file system.

Q. B-tress= 1. File system implementation.

Arrays:

Insertion and Deletion operations are costlier since the memory locations are consecutive and fixed. Insertion and Deletion operations are fast and easy in a linked list.

R. Arrays= 3. Expensive insertion and deletion operations

Graphs:

The network graph is simply called a graph. It consists of a set of nodes connected by branches. In graphs, a node is a common point of two or more branches. Sometimes, only a single branch may connect to the node. A branch is a line segment that connects two nodes.

Any electric circuit or network can be converted into its equivalent graph by replacing the passive elements and voltage sources with short circuits and the current sources with open circuits. That means, the line segments in the graph represent the branches corresponding to either passive elements or voltage sources of the electric circuit.

S. Graphs= 4. Electronic circuit design analysis

Hence the correct answer is P - 2, Q - 1, R - 3, S - 4.