Data Structures and Algorithms MCQ - Graph Algorithm

1 Consider the following directed graph:

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

So total solution 6

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

adjancey matrix is

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

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

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.

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

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?

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

Data Structures and Algorithms MCQ - Graph Algorithm

Graph Algorithms Questions for UGC NET Computer Science

Graph Algorithms MCQ

Graph Algorithms Multiple choice questions

Accessibility

Status
Q	M	N	O	P	R
2	1	1		1
2	2	1		1	1
2	2	2	1	1	1