Skip to content

Latest commit

 

History

History
37 lines (29 loc) · 1.73 KB

21.1.md

File metadata and controls

37 lines (29 loc) · 1.73 KB
Raw

Exercises 21.1-1

Suppose that CONNECTED-COMPONENTS is run on the undirected graph G = (V, E), where V = {a, b, c, d, e, f, g, h, i, j, k} and the edges of E are processed in the following order: (d, i), (f, k), (g, i), (b, g), (a, h), (i, j), (d, k), (b, j), (d, f), (g, j), (a, e), (i, d). List the vertices in each connected component after each iteration of lines 3-5.

Answer

{a} {b} {c} {d} {e} {f} {g} {h} {i} {j} {k}

  1. (d,i) => {a} {b} {c} {d i} {e} {f} {g} {h} {j} {k}
  2. (f,k) => {a} {b} {c} {d i} {e} {f k} {g} {h} {j}
  3. (g,i) => {a} {b} {c} {d g i} {e} {f k} {h} {j}
  4. (b,g) => {a} {b d g i} {c} {e} {f k} {h} {j}
  5. (a,h) => {a h} {b d g i} {c} {e} {f k} {j}
  6. (i,j) => {a h} {b d g i j} {c} {e} {f k}
  7. (d,k) => {a h} {b d g i j f k} {c} {e}
  8. (b,j) => {a h} {b d g i j f k} {c} {e}
  9. (d,f) => {a h} {b d g i j f k} {c} {e}
  10. (g,j) => {a h} {b d g i j f k} {c} {e}
  11. (a,e) => {a e h} {b d g i j f k} {c}

Exercises 21.1-2

Show that after all edges are processed by CONNECTED-COMPONENTS, two vertices are in the same connected component if and only if they are in the same set.

Answer

If two vertices are not in the same set, meaning that no edge connecting the set of one vertice with the other. So two vertices are in the same connected component if and only if they are in the same set.

Exercises 21.1-3

During the execution of CONNECTED-COMPONENTS on an undirected graph G = (V, E) with k connected components, how many times is FIND-SET called? How many times is UNION called? Express your answers in terms of |V|, |E|, and k.

Answer

  • FIND-SET : 2|E|
  • UNION : |V| - k

Follow @louis1992 on github to help finish this task.