Let G be a connected graph with vertices a, b, c, ...,h, i. Thus |V| = 9. A list of edges, sorted by weight, is shown below. Execute both Kruskal's and Prims algorithms without drawing any part of G, as shown in class. Indicate the order edges are added to "T." Initialize Prim's with vertex a . For Kruskal's algorithm, show the connected components, as illustrated in class.

Kruskal

T = V, add cheapest (globally) edge keeping circuit-free until |E| = n-1

w(e) edge

1 cf 1 hi 2 eh 2 fi 3 bd 3 gh 4 bc 4 dg 4 fh 5 ef 6 ab 6 be 7 ad 8 de

Prim

T = {a}, add edges and vertices by adding cheapest (locally) edge connecting T to V-T until |E| = n-1

w(e) edge

1 cf 1 hi 2 eh 2 fi 3 bd 3 gh 4 bc 4 dg 4 fh 5 ef 6 ab 6 be 7 ad 8 de