Question

Suppose we want to find the minimum spanning tree of the following graph.

(a) Run Prim’s algorithm; whenever there is a choice of nodes, always use alphabetic ordering (e.g., start from node A). Draw a table showing the intermediate values of the cost array.

(b) Run Kruskal’s algorithm on the same graph. Show how the disjoint-sets data structure looks at every intermediate stage (including the structure of the directed trees), assuming path compression is used.

Short answer

a). The cost of the minimum spanning tree by using prim’s algorithm is 12.

b). the cost of the minimum spanning tree by using Kruskal’s algorithm is 12.

Step-by-step solution

 Introduction of Minimum spanning tree:

The minimum spanning tree is an edge-weighted graph whose weight is not more than the weight of any other spanning tree.Prim’s algorithm is based on same graph which based on set of data structure looks at every intermediate state allowing different kind of structure of directed trees.

Prim’s algorithm is based on same graph which based on set of data structure looks at every intermediate state allowing different kind of structure of directed trees.

Step 2: Determine the minimum spanning tree using Prim’s algorithm:

Procedure prim ( G,w )

Input: The graph G = (V,E) with edge weights.

Output: Minimum spanning tree.

Step1: for all $U\ddot{o}V:$

$$\begin{gathered} \cos t\left(u\right)=0 \\ prev\left(u\right)=nil \\ pickanyfirstnode{U}_0 \\ \cos t\left(U_0\right)=0 \end{gathered}$$

Step2: H = makequeue (V) (priority queue with the help of the cost-value as keys)

Step3: whileH is not empty:

Step4: v = deletemin (H)

$$\begin{gathered} foreach\left\{v,z\right\}\dot{o}E \\ checkif\cos t\left(z\right)>w(v,z): \\ \cos t\left(z\right)>w(v,z) \\ prev(z0=v \\ decreasekey(H,z) \end{gathered}$$

• Using the cost values, create a priority queue.

• Make sure the queue isn't empty.

Assign and remove the smallest node possible.

The for loop runs until the edge " E " is reached.

• Determine if the node's cost exceeds that of the minimal neighbour node.

• Include the cost of the minimal neighbour nodes.

• Assign the preceding node to the smallest neighbour node.

• Reduce the key value.

• Once all of the vertex in the MST are connected and there are N - 1edges, stop.

Execute this prim's algorithm on the given graph $U\dot{o}V$.

• Initializes the cost node '' cost (u) '' as infinite and previous node '' prev (u) '' as NIL and prefer the initial node of $U_0=A$.

Run Prim’s algorithm for finding minimum spanning tree.

a).

Refer to the network in textbook question 5.2 and assign " v = A " to the lowest node from priority queue "H". There are (A,B), (A,F), and (A,E) edges for " A " vertex. The prices for

, and are all the same. And find out the vertices with the lowest cost. The cost of is the cheapest. Assign the cost value to " ," .the previous value to " ," and the key value to "decrement." After then, the structure is as follows:

Assign " v = B " to the lowest node on prioritized queues " H ."

There really are (B,F) , (B,C), and (B,G) edges for the " B " vertex. The prices for (B,F) = 6, (B,C) = 2, and (B,G) = 6 are all the same. Look for the vertices (B,F) , (B,C), and (B,D) with the lowest cost (B, G) The cost of (B,C) = 2 is the cheapest. As a result, double the current cost by the prior value.

$$\begin{gathered} \cos t\left(z\right)=1+2 \\ =3 \end{gathered}$$

Assign the previous value as “ prev (z) = 3 ” and decrement the key value. and the minimum node from “ H ” as “ v = C ”.For “C” vertex, there are (C,D) and (C, G) edges. The cost for (C, D) = 3 and (C, G) = 2. Check for the minimum cost among the vertices The cost of is minimum. So, add the current cost with previous value.

Assign the previous value as “ ” and decrement the key value. Assign the minimum node from For “” vertex, there are edges, The cost for Check for the minimum cost among the vertices Take the cost of is minimum in priority manner.So, add the current cost with previous value.

After that assign the previous value as “ ” and decrement the key value. Now, take the cost of is minimum in priority manner. So, add the current cost with previous value.

$\begin{array}{l}\cos \left(z\right)=6+1\\ =7\end{array}$

Assign the previous value as “ prev (z) =7” and decrement the key value. Now, take the cost of (G,H) = 1 is minimum in priority manner. So, add the current cost with previous value.

$\begin{array}{l}\cos \left(z\right)=7+1\\ =8\end{array}$

Assign the previous value as “ prev(z)=8 ” and decrement the key value. Assign the minimum node from "H" as "v = D" For "D" vertex, there are (D,C) and (D,H) edges. So, ignore this vertex and there is no change in the structure. Again, assign the minimum node from "H" is "v = F" For “ F ” vertex, there are (F,E) is in the tree. So, ignore this vertex and there is no change in the structure. The minimum node from "H" is "v=E" . For “ E” vertex, there are (E,A) is not in the tree. Check whether the minimum cost from the vertices (E,A).

The cost for $\left(E,A\right)=4$.

Take the cost of $\left(E,A\right)=4$is minimum in priority. So, add the current cost with previous value.

$\begin{array}{l}\cos \left(z\right)=8+4\\ =12\end{array}$

Assign the previous value as “ prev(z) = 12 ” and decrement the key value. Assign the minimum node from "H" is "v=H" for “H” vertex, there are (H,D) is in the tree. So, ignore this vertex and there is no change in the structure. Then, the structure is shown below:

Thus, the minimum spanning tree using the Prim’s algorithm is shown below:

Table for cost Array:

Vertex in Graph	Edge in Graph	Cost
A		0
B	(A,B)	0+1=0
C	(B,C)	1+2=3
D	(C,G)	3+2=5
E	(G,D)	5+1=6
F	(G,F)	6+1=7
G	(G,H)	7+1=8
H	(E,A)	8+4=12

Therefore, the cost of the minimum spanning tree is “ 12 ”.

frfgrf

b).

Kruskal’s algorithm:

Procedure Kruskal ( G,w )

Input: G = (V , E)graph with edge weights w_e

Output: Minimum spanning tree

Step1: for all $u\in V$

make set (u)

Step2: X = { }

Step3: Sort the edges E by weight

Step4: for all edges { u ,v } localid="1659076322808" $\in$E, in order of increasing

weight: check if find (u) localid="1659076327631" $\ne$find (v):

add edge { u ,v } to X

union (u , v)

• Sort the edges in order of increasing weight.

• Add an edge to the MST as long as it does not form a cycle with edges added in previous passes.

• Stop when all of the vertices are connected and there are N - 1 edges in the MST.

For given graph, run the Kruskal’s algorithm.

1: Call themakeset (u).

2: Initialize the values X = { }.

3: Sort the edges in the increasing order.

$\left\{\begin{array}{c}1:\left(AB\right),1:(D,G),1:(F,G),1:(H,G),2:(B,C),2:(B,C),2:(C,G)3:(C,D),4:(A,E),4:(D,H)\\ 5:(E,F),6:(B,F),\\ 6:(B,G),8:(A,F)\end{array}\right\}$

4: Loop executes over the ordered edges. For edge , (A,B), (D,G), (F,G), (H,G), (B,C), (C,G), (C,D), (A,E)(D,H), (B,F), (B,G), (A,F) Then, the structure is :

5:Finally, the minimum spanning tree is shown below:

Therefore, the cost of the minimum spanning tree is .