Test: Graphs- 2 - Computer Science Engineering (CSE) MCQ

1) Breadth First Search uses Queue
2) Depth First Search uses Stack
3) Prim's Minimum Spanning Tree uses Priority Queue.
4) Kruskal' Minimum Spanning Tree uses Union Find.

Option (A) is MNOPQR. It cannot be a BFS as the traversal starts with M, but O is visited before N and Q. In BFS all adjacent must be visited before adjacent of adjacent. Option (B) is NQMPOR. It also cannot be BFS, because here, P is visited before O. (C) and (D) match up to QMNP. We see that M was added to the queue before N and P (because M comes before NP in QMNP). Because R is M's neighbor, it gets added to the queue before the neighbor of N and P (which is O). Thus, R is visited before O.

In DFS, if 'v' is visited after 'u', then one of the following is true.

1) (u, v) is an edge.

2) 'u' is a leaf node.

In DFS, after visiting a node, we first recur for all unvisited children. If there are no unvisited children (u is leaf), then control goes back to parent and parent then visits next unvisited children.

We can check all DFSs for following properties.

In DFS, if a vertex 'v' is visited after 'u', then one of the following is true.

1) (u, v) is an edge.

2) 'u' is a leaf node.

In DFS, after visiting a node, we first recur for all unvisited children. If there are no unvisited children (u is leaf), then control goes back to parent and parent then visits next unvisited children.

Make can decide the order of building a software using topological sorting. Topological sorting produces the order considering all dependencies provide by makefile. See following for details. Topological Sorting

We can use both traversals to find if there is a path from s to t.

A back edge means a cycle in graph. So if there is a cycle, all DFS traversals would contain at least one back edge.

Consider the following graph. If we start from 'a', then there is one tree edge. If we start from 'b', then there is no tree edge. a---->b

In a graph with three nodes, r u and v, with edges (r; u) and (r; v), and r is the starting point for the DFS, u and v are siblings in the DFS tree, neither as the ancestor of the other.

In option D, 1 appears after 2 and 3 which is not possible in Topological Sorting. In the given DAG it is directly visible that there is an outgoing edge from vertex 1 to vertex 2 and 3 hence 2 and 3 cannot come before vertex 1 so clearly option D is incorrect topological sort. But for questions in which it is not directly visible we should know how to find topological sort of a DAG.

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²)

BFS always produces shortest path from source to all other vertices in an unweighted graph.

The following diagram shows the worst case situation where the recursion tree has maximum depth.

So the recursion depth is 19 (including the first node).

Below example shows that A and B are FALSE:

Below example shows C is false:

In DFS, if 'v' is visited after 'u', then one of the following is true.
1) (u, v) is an edge.

2) 'u' is a leaf node.

In DFS, after visiting a node, we first recur for all unvisited children. If there are no unvisited children (u is leaf), then control goes back to parent and parent then visits next unvisited children.

Tree edges are the edges that are part of DFS tree.  If there are x tree edges in a tree, then  x+1 vertices in the tree. The output of DFS is a forest if the graph is disconnected.  Let us see below simple example where graph is disconnected.

The above example matches with D option More Examples: 1) All vertices  of Graph are connected.  k must be n-1.  We get number of connected components  = n- k =  n - (n-1) = 1 2) No vertex is connected. k must be 0.  We get number of connected components  = n- k =  n - 0 = n

Following are different 6 Topological Sortings

a-b-c-d-e-f
a-d-e-b-c-f
a-b-d-c-e-f
a-d-b-c-e-f
a-b-d-e-c-f
a-d-b-e-c-f