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

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

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

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

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