Given Prim's pseudocode algorithm used as voraz algorithm (Figure 1) Where (pi) are the ancestors of the vertex in question and Q are the vertices that can be considered for expansion. Find the...

Given Prim's pseudocode algorithm used as voraz algorithm (Figure 1)

Where (pi) are the ancestors of the vertex in question and Q are the vertices that can be considered for expansion. Find the minimum generation tree for the graph in Figure 2

To carry out the exercise, the data structure shown in the second Table will be used.

(First Table: PRIM data structure)

Vertex	a	b	c	d	e	f	g	h	i
weight	0	inf.	inf.	inf.	inf.	inf.	inf.	inf.	inf.
pi	null	null	null	null	null	null	null	null	null
Q	X	X	X	X	X	X	X	X	X

* inf. = infinity symbol

In an initial stage, the vertex a is selected and therefore we start with a weight of 0. Then, the neighbors are updated (for example, the neighbors of a are b and h). They will only be updated if the update is a lower weight than an already known one. For example, from vertex a it expands to vertex b and h leaving the table as shown below:

(Second Table: First iteration)

Vertex	a	b	c	d	e	f	g	h	i
weight	0	4	inf.	inf.	inf.	inf.	inf.	8	inf.
pi	null	a	null	null	null	null	null	a	null
Q	X	---	X	X	X	X	X	X	X

To find the most promising one, we must go through the list of weights to find the one with the lowest weight, which in this case is from vertex b. This is marked with "---" in Q because now b is part of the solution.

What is the operational cost of the algorithm? How could it be improved? Explain for both cases.

Extracted text: while Q + {} do u+ extractMininum(Q) X + XU{(u,7[u])} // if u # r foreach v E Adj[u] do if (v E Q) and (w(u, v) < weight|[v])="" then="" weight="" (u]="" +-="" w(и,="" v)п[u]="" +-="" и="" end="" if="" end="" for="" end="" while="" return="">


Extracted text: 8 7 b d 4 2 9. a а) 11 i 4 14 e 6 8 7 10 h f 1 2.