Consider the following graph for each of the two subproblems. Each subproblem ca

Question

Consider the following graph for each of the two subproblems. Each subproblem can be answer

Consider the following graph for each of the two subproblems. Each subproblem can be answered (or left blank) independently of the other (subject to the 4 total blank for partial credit rule). The graph is drawn twice, so that you can use one for work for each subproblem. You are running Prim's algorithm on the graph below and left, starting with vertex c. You are about to take vertex i out of the min-heap, but have not done so yet. For that instant in time, directly label edges (every one of them) on the graph, using categories from the following list: Already know to be in the graph. The edge has not been seen yet. The edge has been seen, and is known to not be in the graph. The edge has been seen, and is stored with a vertex in the heap. Other. You are in the middle of running Kruskal's Minimum Weight Spanning Tree algorithm, using the Disjoint Set data structure, with union by size and path compression. Use the graph above right. You are about to consider the edge with weight 9. Draw the corresponding disjoint set data structure for the graph, before, and after the edge with weight 9. Assume that, for each edge of the graph, the edge is called with the alphabetically first vertex first, mid that for sets of the same size, the first set joins to the second.

Explanation / Answer

a) cg->2, ga->11,ai->1

b) ai,cg,hi,bd,fe,ec,ad->before adding edge 9,

after adding 9 just add bc to the set.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.