Answer the following questions about the MysteryPath algorithm below, which take

Question

Answer the following questions about the MysteryPath algorithm below, which take in a graph and returns a path. Input: G- (V, E): graph with n vertices and m edges Input: m, n: size and order of G, respectively 1 Algorithm: MysteryPath 2 count-Map(V Z); 3 foreachvEV do count[u] = deg(u); s end 6 path= {}; V1]: 8 while count[u] 0 do Add to path; 10 1foreach u E N(v) do if count(u-x then count count u- 16 Let be the neighbor of u with the smallest value of count; 17 en 1s Add v to path; 19 return path;

Explanation / Answer

1) The following path will be the return:

V1 V3 V7 V4 V2V5 V6

2) The time complexity of the algorithm by using adjacency list representation is:

O(VE)

First, for loop execute V times.

While loop executes V times

to check adjacency within while it will take no. of edges appear in adjacency list corresponding vertex, it can exceed the number of edges in any case.

therefore time complexity will be :

T(n)= V+ V*(any number of edges within any subset of edges)

= V+V(E)

T(n)=O(VE)

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---