Skip to main content
adding question 2
Source Link
hengxin
  • 9.6k
  • 3
  • 37
  • 74

Question 1: However still I think that according to the line 8 in algorithm, all adjacent vertices of $a$ not in the tree must be added first to the tree. Thus $h$ should also get added immediately after $b$, before $c$.

You are confusing the resulting MST treetree (denoted $T$) with the intermediate priority queue $Q$.

  • All the vertices are already in $Q$ at the end of initialization (Lines 1 ~ 5). However, $T = \emptyset$ at this time point.

  • A vertex $u$ is extracted from $Q$ and becomes a member of tree $T$ at line 7.

  • In the loop starting from Line 8, vertice $v$ satisfying the requirements of Line 9 are not inserted into the tree $T$; instead their keys in the priority queue $Q$ are changed (in fact, decreased).

Question 2: "My point is when the line 8 says "for each adjacent vertex $v$ of $u$", why only adjacent node $b$ of $a$ is considered, but not $h$ (which is also adjacent to $a$)."

Yes, $h$ is also considered, but in the way different from what you describe. In the iteration for $a$, both $b$ and $h$ are considered (satisfying Line 8 and Line 9): their keys are updated (i.e., decreased) in the priority queue $Q$ (Line 11) and their parents are updated accordingly (Line 10). (Note that these updates are not finalized and may be updated again during the algorithm.)

The key point is: neither $b$ nor $h$ has been added into the resulting MST tree $T$. Vertex $b$ will be extracted from $Q$ and added into $T$ in the next iteration at Line 7 (shown in step (b)).

Also note that the figure in CLRS only shows the changes on $T$; it does not show the states of $Q$.

However still I think that according to the line 8 in algorithm, all adjacent vertices of $a$ not in the tree must be added first to the tree. Thus $h$ should also get added immediately after $b$, before $c$.

You are confusing the resulting MST tree (denoted $T$) with the intermediate priority queue $Q$.

  • All the vertices are already in $Q$ at the end of initialization (Lines 1 ~ 5). However, $T = \emptyset$ at this time point.

  • A vertex $u$ is extracted from $Q$ and becomes a member of tree $T$ at line 7.

  • In the loop starting from Line 8, vertice $v$ satisfying the requirements of Line 9 are not inserted into the tree $T$; instead their keys in the priority queue $Q$ are changed (in fact, decreased).

Question 1: However still I think that according to the line 8 in algorithm, all adjacent vertices of $a$ not in the tree must be added first to the tree. Thus $h$ should also get added immediately after $b$, before $c$.

You are confusing the resulting MST tree (denoted $T$) with the intermediate priority queue $Q$.

  • All the vertices are already in $Q$ at the end of initialization (Lines 1 ~ 5). However, $T = \emptyset$ at this time point.

  • A vertex $u$ is extracted from $Q$ and becomes a member of tree $T$ at line 7.

  • In the loop starting from Line 8, vertice $v$ satisfying the requirements of Line 9 are not inserted into the tree $T$; instead their keys in the priority queue $Q$ are changed (in fact, decreased).

Question 2: "My point is when the line 8 says "for each adjacent vertex $v$ of $u$", why only adjacent node $b$ of $a$ is considered, but not $h$ (which is also adjacent to $a$)."

Yes, $h$ is also considered, but in the way different from what you describe. In the iteration for $a$, both $b$ and $h$ are considered (satisfying Line 8 and Line 9): their keys are updated (i.e., decreased) in the priority queue $Q$ (Line 11) and their parents are updated accordingly (Line 10). (Note that these updates are not finalized and may be updated again during the algorithm.)

The key point is: neither $b$ nor $h$ has been added into the resulting MST tree $T$. Vertex $b$ will be extracted from $Q$ and added into $T$ in the next iteration at Line 7 (shown in step (b)).

Also note that the figure in CLRS only shows the changes on $T$; it does not show the states of $Q$.

Source Link
hengxin
  • 9.6k
  • 3
  • 37
  • 74

However still I think that according to the line 8 in algorithm, all adjacent vertices of $a$ not in the tree must be added first to the tree. Thus $h$ should also get added immediately after $b$, before $c$.

You are confusing the resulting MST tree (denoted $T$) with the intermediate priority queue $Q$.

  • All the vertices are already in $Q$ at the end of initialization (Lines 1 ~ 5). However, $T = \emptyset$ at this time point.

  • A vertex $u$ is extracted from $Q$ and becomes a member of tree $T$ at line 7.

  • In the loop starting from Line 8, vertice $v$ satisfying the requirements of Line 9 are not inserted into the tree $T$; instead their keys in the priority queue $Q$ are changed (in fact, decreased).