Follow Us :

Data Structures and Algorithms - Graph Algorithm

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

6. Let G be a simple undirected graph. Let TD be a depth first search tree of G. Let TB be a breadth first search tree of G. Consider the following statements:
I. No edge of G is a cross edge with respect to TD. (A cross edge in G is between two nodes neither of which is an ancestor of the other in TD).
II. For every edge (u, v) of G, if u is at depth i and u is at depth j in TB, then |i – j | = 1.
Which of the statements above must necessarily be true?

  • Option : A
  • Explanation :
    Statement (i) is true.
    (i) No edges of G is a cross edge with respect to TD.
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 *


7. Lt G be an undirected graph. Consider a depth first traversal of G, and let T be the resulting depth-first search tree. Let u be a vertex in G and let v be the first new (unvisited) vertex visited after visiting u in the traversal. Which of the following statements is always true?

  • Option : C
  • Explanation :
    In DFS if ‘v’ is visited after ‘u’ then one of the following is true.
    (i) if (u, v) is an edge

    (ii) if ‘u’ is x leaf node
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 *


8. Consider the following graph

 Among the following sequences
 1. abeghf
 2. abfehg
 3. abfhge
 4. afghbe
 Which are depth first traversals of the above graph?

  • Option : D
  • Explanation :
    (1) a b e g h f
    (3) a b f h g e
    (4) a f g h b e is possible DFS of given graph.
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 *


9. In a depth-first traversal of a graph G with n vertices, k edges are marked as tree edges. The number of connected components in G is

  • Option : D
  • Explanation :
    If n vertex and K edges are there then the number of connected component in the graph is n – K.
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 *


10. Let T be a depth first search tree in a undirected graph G. Vertices-u and v are leaves of this tree T. The degrees of both u and v in G are at least 2. Which one of the following statements is true?

  • Option : D
  • Explanation :

    For the above graph, conducting depth First scarch:
    Stack : A
    Stack : DBC Tree : A
    Stack : EBC Tree : A / D
    Stack : BC Tree : A / D / E
    Stack : BC
    Stack : Φ Tree :

    Considering l eaf nodes E and C, t he gi ven condition is satisfied as their degrees are more than one. But none of (A), (B) or (C) hold.
    But a cycle consisting of E and all its neighbour hold.
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

    Related Quiz.
    Graph Algorithm