7.dol← EXTRACT-MIN(Q) 8 for each∈Ad/al 9 do ifv E O and w(u, v)<key(v) then v] keyv←w(u,v) MAKE-SET(x) 1.p{x]←x 2. rank[x]←0 FIND-SET(x) 2. then x FIND-SET(pExD) 3. return plx UNION(x, y) 1. LINK(FIND-SET(), FIND-SETO)) LINK(x, y) 1. if rank]> rankly 2. then ply 3. else p{x]←y then rankb]← rankly]+1 6. Answer quest a. This algorithm will not work for cyclic graph b. The algorithm is equal to DFS .O(+E) 7. Find all-pairs shortest paths 03729 1122 030-45x=5134 471109 -5 5152 8. Fill the blanks (b)q←x{q (c)q←q+17. do u ← EXTRACT-MIN(Q) 8. for each v ∈ Adj[u] 9. do if v ∈ Q and w(u, v) < key(v) 10. then π[v] ← u 11. key[v] ← w(u, v) MAKE-SET(x) 1. p[x] ← x 2. rank[x] ← 0 FIND-SET(x) 1. if x ≠ p[x] 2. then x ← FIND-SET(p[x]) 3. return p[x] UNION(x, y) 1. LINK(FIND-SET(x), FIND-SET(y)) LINK(x, y) 1. if rank[x] > rank[y] 2. then p[y] ← x 3. else p[x] ← y 4. if rank[x] = rank[y] 5. then rank[y] ← rank[y] + 1 6. Answer questions a. This algorithm will not work for cyclic graphs b. The algorithm is equal to DFS. c. O(V + E) 7. Find all-pairs shortest paths 0 3 7 29 1 0 8 16 0 3 0 45 4 7 11 0 9 5 2 2 30 D ⎡ ⎤ ⎢ ⎥ − = − ⎣ ⎦ −− − 1122 5 522 51 34 515 4 5152 π ⎡∅ ⎤ ⎢ ⎥ ∅ ⎢ ⎥ = ⎢ ∅ ⎥ ⎢ ⎥ ⎢ ∅ ⎥ ⎢ ∅⎥ ⎣ ⎦ 8. Fill the blanks (a) q > 0 (b) q ← π [q] (c) q ← q + 1 (d) q = m (e) q ← π [q]