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. Required fields are marked *


Cancel reply

Your email address will not be published. Required fields are marked *


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

Cancel reply

Your email address will not be published. Required fields are marked *


Cancel reply

Your email address will not be published. Required fields are marked *


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. Required fields are marked *


Cancel reply

Your email address will not be published. Required fields are marked *


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. Required fields are marked *


Cancel reply

Your email address will not be published. Required fields are marked *


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. Required fields are marked *


Cancel reply

Your email address will not be published. Required fields are marked *


  • 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