Graphs Interview Questions Part 6

49. Determining the shortest path from every vertex to every other vertex in a weighted graph (with non-negative weights) using Dijkstra's algorithm takes O(V3) time. (T/F)
Ans. True -- determining the shortest path from a single vertex s to every other vertex takes O(V2) time. So determining the shortest path for every vertex will take O(V3) time.
51. Which one of the following is a faster technique to test if (x,y) is in a graph?
a. adjacency list
b. adjacency matrix
c. Kruskal’s algorithm
d. Dijkstra’s algorithm
Ans. b

52. Adjacency lists are faster to find the degree of a vertex as compared to adjacency matrix. True or False
Ans. True

53. _________ is a graph representation that occupies less memory on small graphs.
a. forest
b. adjacency list
c. adjacency matrix
d. tree
Ans. b because for adjacency list its (m+n) whereas for matrix its n^2.

54. _________ is a graph representation that occupies less memory on big graphs.
a. adjacency matrix
b. adjacency list
c. forest
d. queue
Ans. a

55. Faster traversal in a graph is possible in which representation?
a. forest
b. adjacency list
c. adjacency matrix
d. tree
Ans. b
adjacency lists vs. adjacency matrix
56. Edge insertion or deletion is better in adjacency matrices as compared to adjacency list. (True or False)
Ans. True
adjacency matrices O(1) vs. O(d)

57. Given the graph, the depth-first traversal will be

a. ACGBEFHD
b. ABCDEFGH
c. ACDBEFHG
d. ACGDEFBH
Ans. a

58. Given the following graph,the resulting depth-first traversal will be


a. BEFGHCAD b. BFEGHCAD c. BEGHFCAD d. BEFHGCAD
Ans. a

Refer Pg-565 for the resulting tree (Data Structures Using C and C++ by Tanenbaum)


59. Depth-first traversal method in a graph
i. creates a spanning forest
ii. can be used to determine if an undirected graph is connected
iii. to identify the connected components of an undirected graph
The correct options are
a. i only
b. i and ii only
c. ii only
d. i,ii and iii
Ans. d

60. Using adjacency matrix representation,the efficiency of depth-first search is
a. O(n+n²) or O(n²)
b. O(e)
c. O(n)
d. O(n+e)
Where n is the number of graph nodes and e is the number of edges in the graph.
Ans. a
Refer Pg-573 of Data Structures in c and C++ by tanenbaum
61. Using adjacency list representation,the efficiency of depth-first traversal is
a. O(n+n²)
b. O(e)
c. O(n)
d. O(n+e)
Ans. d
Traversing all successors of all nodes is O(e) and assuming that the graph nodes are organized as an array or a linked list ,visiting all n nodes is O(n).hence,efficiency is O(n+e).