Graph

What would be the number of zeros in the adjacency matrix of the given graph?

• 10

• 6

• 16

• 0

Which of these adjacency matrices represents a simple graph?

• [ [1, 0, 0], [0, 1, 0], [0, 1, 1] ]

• [ [1, 1, 1], [1, 1, 1], [1, 1, 1] ]

• [ [0, 0, 1], [0, 0, 0], [0, 0, 1] ]

• [ [0, 0, 1], [1, 0, 1], [1, 0, 0] ]

What would be the DFS traversal of the given Graph?

• AEDCB

• ABCED

• EDCBA

• ADECB

Consider an undirected unweighted graph G. Let a breadth-first traversal of G be done starting from a node r. Let d(r, u) and d(r, v) be the lengths of the shortest paths from r to u and v respectively, in G. lf u is visited before v during the breadth-first traversal, which of the following statements is correct?

• d(r, u) < d (r, v)

• d(r, u) > d(r, v)

• d(r, u) <= d (r, v)

• None of the above

Consider the following undirected graph with edge weights as shown:

The number of minimum-weight spanning trees of the graph is ___________

• 2.5

• 3.4

• 1.6

• 0.7

Consider the following C++ code

• 0 1 3 2

• 0 2 3 1

• 0 1 2 3

• 0 2 1 3

Which of the following algorithms can be used to most efficiently determine the presence of a cycle in a given graph ?

• Depth First Search

• Breadth First Search

• 
  Prim's Minimum Spanning Tree Algorithm

• Kruskal's Minimum Spanning Tree Algorithm

Let G be a graph with n vertices and m edges. What is the tightest upper bound on the running time on Depth First Search of G? Assume that the graph is represented using adjacency matrix.

• O(n)

• O(m+n)

• O(n²)

• O(mn)

Answer explanation

Depth First Search of a graph takes O(m+n) time when the graph is represented using adjacency list. In adjacency matrix representation, graph is represented as an "n x n" matrix. To do DFS, for every vertex, we traverse the row corresponding to that vertex to find all adjacent vertices (In adjacency list representation we traverse only the adjacent vertices of the vertex). Therefore time complexity becomes O(n²).