(Choose 1 answer)
Given the graph G = (V.E) and X is a vertex of G. Suppose there exists at least one Hamilton Cycle for the graph. The following is a backtracking algorithm for finding the first Hamilton cycle from the vertex X:
declare an empty array H (which will contain Hamilton cycle)
(1) Put the vertex X to H
2) Check if H is a Hamilton cycle then stop, else go to (3)(
(3) Consider the last vertex Y in H, if there is/are vertex(es)
adjacent to Y, select the first adjacent vertex Z (by alphabet order) and put it to H. If there no adjacent vertex, remove Y from H and denote it as a bad selection (so you do not select it in the
same way again).
Go to (2)
Suppose a G is given below (view picture). Which of the followings is the Hamilton cycle from the vertex B. created by above algorithm?
A. b. e, d. c. a, b
B. b. a, c, d, e, b
C. b a, e, d, c, b
D. b, e, a, d, c, b
E. b, c, d, e, a, b
h
Exit 16
