Graph data structure

In a simple graph, the number of edges is equal to twice the sum of the degrees of the vertices.

• True

• False

A connected graph T without any cycles is called .......

• Free graph

• no cycle graph

• non cycle graph

• circular graph

A graph is said to be ....... if every node u in G is adjacent to every other node v in G.

What would be the DFS traversal of the given Graph?

• ABCED

• AEDCB

• EDCBA

• ADECB

The topological sorting of any DAG can be done in ________ time

• cubic

• quadratic

• linear

• logarithmic

What sequence would the BFS traversal of the given graph yield?

• A F D B C E

• C B A F D

• A B D C F

• A B C D E F

Which of the following is an advantage of adjacency list representation over adjacency matrix representation of a graph?

• In adjacency list representation, space is saved for sparse graphs.

• DFS and BSF can be done in O(V + E) time for adjacency list representation. These operations take O(V^2) time in adjacency matrix representation. Here is V and E are number of vertices and edges respectively.

• Adding a vertex in adjacency list representation is easier than adjacency matrix representation.

• All of the above

Which of the following statements is/are TRUE for an undirected graph?

P: Number of odd degree vertices is even

Q: Sum of degrees of all vertices is even

• P Only

• Q Only

• Both P and Q

• Neither P nor Q

Which of the following is true?

• Prim’s algorithm initialises with a vertex

• Prim’s algorithm initialises with a edge

• Prim’s algorithm initialises with a vertex which has smallest edge

• Prim’s algorithm initialises with a forest

Consider the given graph. What is the weight of the minimum spanning tree using the Prim’s algorithm, starting from vertex a?

• 23

• 28

• 27

• 11