MCQs Graph Based Algorithms

1. Dijkstra’s algorithm :

• Has greedy approach to find all shortest paths
• Has both greedy and Dynamic approach to find all shortest paths
• Has greedy approach to compute single source shortest paths to all other vertices
• Has both greedy and dynamic approach to compute single source shortest paths to all other vertices.

Ans: (c) Has greedy approach to compute single source shortest paths to all other vertices

2. Consider the DAG with Consider V = {1, 2, 3, 4, 5, 6}, shown below.

Which of the following is NOT a topological ordering?

• 1 2 3 4 5 6
• 1 3 2 4 5 6
• 1 3 2 4 6 5
• 3 2 4 1 6 5

Ans: (d) 3 2 4 1 6 5

3. Which of the following condition is sufficient to detect cycle in a directed graph?

• There is an edge from currently being visited node to an already visited node.
• There is an edge from currently being visited node to an ancestor of currently visited node in DFS forest.
• Every node is seen twice in DFS.
• None of the listed options

Ans: (b) There is an edge from currently being visited node to an ancestor of currently visited node in DFS forest.

4. Make is a utility that automatically builds executable programs and libraries from source code by reading files called makefiles which specify how to derive the target program. Which of the following standard graph algorithms is used by Make.

• Strongly Connected Components
• Topological Sorting
• Breadth First Search
• Dijkstra’s Shortest Path

Ans: (b) Topological Sorting

5. What are the appropriate data structures for following algorithms?

1) Breadth First Search
2) Depth First Search
3) Prim’s Minimum Spanning Tree
4) Kruskal’ Minimum Spanning Tree

1) Stack 2) Queue 3) Priority Queue 4) Union Find

1) Queue 2) Stack 3) Priority Queue 4) Union Find

1) Stack 2) Queue 3) Union Find 4) Priority Queue

1) Priority Queue 2) Queue 3) Stack 4) Union FindNext

Ans: (b) 1) Queue 2) Stack 3) Priority Queue 4) Union Find

6. 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’ Minimum Spanning Tree AlgorithmNext

Ans: (a) Depth First Search

7. A tour of G is a closed walk of graph G which includes every edge G at least once. A ….. tour of G is a tour which includes every edge of G exactly once ?

• Hamiltonian
• Planar
• Isomorphic
• Euler

Ans: (d) Euler

8. The complete graph K, has… different spanning trees? [ ^ – raised to for exponent]

• n^2
• n^n-2
• n*n
• n^n

Ans: (b) n^n-2

Happy Learning – If you require any further information, feel free to contact me.