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

Cancel reply

Your email address will not be published.


Cancel reply

Your email address will not be published.


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

Cancel reply

Your email address will not be published.


Cancel reply

Your email address will not be published.


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

  • 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
Cancel reply

Your email address will not be published.


Cancel reply

Your email address will not be published.


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.

  • 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
Cancel reply

Your email address will not be published.


Cancel reply

Your email address will not be published.


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?

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

Your email address will not be published.


Cancel reply

Your email address will not be published.


  • 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