Data Structures and Algorithms - Graph Algorithm

Avatto > > UGC NET COMPUTER SCIENCE > > PRACTICE QUESTIONS > > Data Structures and Algorithms > > Graph Algorithm

1. Consider the following directed graph:

The number of different topological ordering of the vertices of the graph is

Answer
Comment
Array

Option : A
Explanation :

So total solution 6

You must be logged in to post a comment.

You must be logged in to post a comment.

2. Write the adjacency matrix representation of the graph given in figure.

A
B
C
D

Answer
Comment
Array

Option : A
Explanation :
adjancey matrix is

You must be logged in to post a comment.

You must be logged in to post a comment.

3. Let G be a directed graph whose vertex set is the set of numbers from 1 to 100. There is an edge from a vertex i to a vertex j iff either j = i + 1 or j = 3i. The minimum number of edges in a path in G from vertex 1 to vertex 100 is

Answer
Comment
Array

Option : B
Explanation :
Edge set consist edges it j = i + 1 or j = 3i
The edge sequence with minimum no of edges is
1 – 3 – 9 – 10 – 11
|
100 – 99 – 33
Which consist 7 edges

You must be logged in to post a comment.

You must be logged in to post a comment.

4. The most efficient algorithm for finding the number of connected components in an undirected graph on n vertices and m edges has time complexity.

Answer
Comment
Array

Option : C
Explanation :
The most efficient algorithm for finding the number of connected components (articulation point) in an undirected graph on n vertices and n edges using depth-first search takes O(m + n) time.Assume n ≤ m

You must be logged in to post a comment.

You must be logged in to post a comment.

5. In an adjacency list representation of an undirected simple graph G = (V, E), each edge (u, v) has two adjacency list entries: [v] in the adjacency list of u, and [u] in the adjacency list of v. These are called twins of each other. A twin pointer is a pointer from an adjacency list entry to its twin. If |E| = m and |V| = n, and the memory size is not a constraint, what is the time complexity of the most efficient algorithm to set the twin pointer in each entry in each adjacency list?

Answer
Comment
Array

Option : B
Explanation :
Usinng BFS traversal we can set the twin pointer in each entry in each adjacency list. So it will take O(m + n) time.

You must be logged in to post a comment.

You must be logged in to post a comment.

Description

Graph Algorithms Questions can be used to give quizzes by any candidate who is preparing for UGC NET Computer Science

This Graph Algorithms Questions section will help you test your analytical skills in a tricky method, thereby giving you an edge over other students

Any student who wants to prepare for DOEACC A Level, DOEACC B Level, and DOEACC C level can also use these Objective Type Questions Answer.

All candidates who have to appear for the Kendriya Vidyalaya Entrance exam can also refer to this mcq section.

You can also get access to the Graph Algorithms MCQ ebook.

Graph Algorithms Questions can be used in the preparation of JRF, CSIR, and various other exams.

You can also download pdf for these Graph Algorithms multiple-choice questions Answers.

This Graph Algorithms Multiple Choice Questions Answers section can also be used for the preparation of various competitive exams like UGC NET, GATE, PSU, IES, and many more.

Graph Algorithms Questions can be used to gain a credit score in various undergraduate and postgraduate courses like BSc, MSc and MCA

Graph Algorithms Questions for UGC NET Computer Science

Graph Algorithms MCQ

Graph Algorithms Multiple choice questions

Related Quiz.
Graph Algorithm

Forgot your password?

I agree with the Terms.