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. Show, for each iteration of the algorithm, the values with which the data structure remains until reaching the solution.
Given PRIM's pseudocode
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.
Show, for each iteration of the algorithm, the values with which the data structure remains until reaching the solution.
Step by step
Solved in 3 steps with 5 images