Skip to main content
Tweeted twitter.com/StackCompSci/status/1089130904369418241
edited tags
Link
hengxin
  • 9.6k
  • 3
  • 37
  • 74
"algo" --> "algorithm"
Source Link
David Richerby
  • 82.2k
  • 26
  • 144
  • 238

Confusion in CLRS's version of Prim's algoalgorithm

The algoalgorithm is as follows:

MST-PRIM(G,w,r)
1   for each u ∈ G.V   //initialization
2      u.key = ∞
3      u.π = NIL
4   r.key = 0
5   Q = G.V          //end initialization
6   while Q ≠ ∅
7      u = EXTRACT-MIN(Q)
8      for each v ∈ G.Adj[u]
9         if v ∈ Q and w(u,v) < v.key
10           v.π = u
11           v.key = w(u,v)
  • All vertices that are not in the tree reside in a min-priority queue Q based on a key attribute.
  • v.key is the minimum weight of any edge connecting v to a vertex in the tree
  • v.π points to the parent of v in the tree
  • G is a graph, w is a weight function, r is a root

The example given is as follows:

[![enter image description here][1]][1]

I am confused, why in step (c), edge $(b,c)$ is added instead of edge $(a,h)$. Below the diagram, there is a note saying:

In second step, the algorithm has a choice of adding either edge $(b,c)$ or edge $(a,h)$ to the tree since both are light edges crossing the cut.

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$. The line 8 says for **each v** ∈ G.Adj[u](i.e. 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$).

If what author says should occur, then there should be something like break construct on line 12 inside the if construct's body, which will result in exiting for loop and hence grabbing next u = EXTRACT-MIN(Q).

Am I correct? or I must be missing something very stupid. What's that? [1]: https://i.sstatic.net/TTwpR.png

Confusion in CLRS's version of Prim's algo

The algo is as follows:

MST-PRIM(G,w,r)
1   for each u ∈ G.V   //initialization
2      u.key = ∞
3      u.π = NIL
4   r.key = 0
5   Q = G.V          //end initialization
6   while Q ≠ ∅
7      u = EXTRACT-MIN(Q)
8      for each v ∈ G.Adj[u]
9         if v ∈ Q and w(u,v) < v.key
10           v.π = u
11           v.key = w(u,v)
  • All vertices that are not in the tree reside in a min-priority queue Q based on a key attribute.
  • v.key is the minimum weight of any edge connecting v to a vertex in the tree
  • v.π points to the parent of v in the tree
  • G is a graph, w is a weight function, r is a root

The example given is as follows:

[![enter image description here][1]][1]

I am confused, why in step (c), edge $(b,c)$ is added instead of edge $(a,h)$. Below the diagram, there is a note saying:

In second step, the algorithm has a choice of adding either edge $(b,c)$ or edge $(a,h)$ to the tree since both are light edges crossing the cut.

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$. The line 8 says for **each v** ∈ G.Adj[u](i.e. 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$).

If what author says should occur, then there should be something like break construct on line 12 inside the if construct's body, which will result in exiting for loop and hence grabbing next u = EXTRACT-MIN(Q).

Am I correct? or I must be missing something very stupid. What's that? [1]: https://i.sstatic.net/TTwpR.png

Confusion in CLRS's version of Prim's algorithm

The algorithm is as follows:

MST-PRIM(G,w,r)
1   for each u ∈ G.V   //initialization
2      u.key = ∞
3      u.π = NIL
4   r.key = 0
5   Q = G.V          //end initialization
6   while Q ≠ ∅
7      u = EXTRACT-MIN(Q)
8      for each v ∈ G.Adj[u]
9         if v ∈ Q and w(u,v) < v.key
10           v.π = u
11           v.key = w(u,v)
  • All vertices that are not in the tree reside in a min-priority queue Q based on a key attribute.
  • v.key is the minimum weight of any edge connecting v to a vertex in the tree
  • v.π points to the parent of v in the tree
  • G is a graph, w is a weight function, r is a root

The example given is as follows:

[![enter image description here][1]][1]

I am confused, why in step (c), edge $(b,c)$ is added instead of edge $(a,h)$. Below the diagram, there is a note saying:

In second step, the algorithm has a choice of adding either edge $(b,c)$ or edge $(a,h)$ to the tree since both are light edges crossing the cut.

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$. The line 8 says for **each v** ∈ G.Adj[u](i.e. 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$).

If what author says should occur, then there should be something like break construct on line 12 inside the if construct's body, which will result in exiting for loop and hence grabbing next u = EXTRACT-MIN(Q).

Am I correct? or I must be missing something very stupid. What's that? [1]: https://i.sstatic.net/TTwpR.png

added 186 characters in body
Source Link
Mahesha999
  • 1.8k
  • 7
  • 30
  • 45

The algo is as follows:

MST-PRIM(G,w,r)
1   for each u ∈ G.V   //initialization
2      u.key = ∞
3      u.π = NIL
4   r.key = 0
5   Q = G.V          //end initialization
6   while Q ≠ ∅
7      u = EXTRACT-MIN(Q)
8      for each v ∈ G.Adj[u]
9         if v ∈ Q and w(u,v) < v.key
10           v.π = u
11           v.key = w(u,v)
  • All vertices that are not in the tree reside in a min-priority queue Q based on a key attribute.
  • v.key is the minimum weight of any edge connecting v to a vertex in the tree
  • v.π points to the parent of v in the tree
  • G is a graph, w is a weight function, r is a root

The example given is as follows:

[![enter image description here][1]][1]

I am confused, why in step (c), edge $(b,c)$ is added instead of edge $(a,h)$. Below the diagram, there is a note saying:

In second step, the algorithm has a choice of adding either edge $(b,c)$ or edge $(a,h)$ to the tree since both are light edges crossing the cut.

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$. The line 8 says for **each v** ∈ G.Adj[u](i.e. 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$).

If what author says should occur, then there should be something like break construct on line 12 inside the if construct's body, which will result in exiting for loop and hence grabbing next u = EXTRACT-MIN(Q).

Am I correct? or I must be missing something very stupid. What's that? [1]: https://i.sstatic.net/TTwpR.png

The algo is as follows:

MST-PRIM(G,w,r)
1   for each u ∈ G.V   //initialization
2      u.key = ∞
3      u.π = NIL
4   r.key = 0
5   Q = G.V          //end initialization
6   while Q ≠ ∅
7      u = EXTRACT-MIN(Q)
8      for each v ∈ G.Adj[u]
9         if v ∈ Q and w(u,v) < v.key
10           v.π = u
11           v.key = w(u,v)
  • All vertices that are not in the tree reside in a min-priority queue Q based on a key attribute.
  • v.key is the minimum weight of any edge connecting v to a vertex in the tree
  • v.π points to the parent of v in the tree
  • G is a graph, w is a weight function, r is a root

The example given is as follows:

[![enter image description here][1]][1]

I am confused, why in step (c), edge $(b,c)$ is added instead of edge $(a,h)$. Below the diagram, there is a note saying:

In second step, the algorithm has a choice of adding either edge $(b,c)$ or edge $(a,h)$ to the tree since both are light edges crossing the cut.

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$. If what author says should occur, then there should be something like break construct on line 12 inside the if construct's body, which will result in exiting for loop and hence grabbing next u = EXTRACT-MIN(Q).

Am I correct? or I must be missing something very stupid. What's that? [1]: https://i.sstatic.net/TTwpR.png

The algo is as follows:

MST-PRIM(G,w,r)
1   for each u ∈ G.V   //initialization
2      u.key = ∞
3      u.π = NIL
4   r.key = 0
5   Q = G.V          //end initialization
6   while Q ≠ ∅
7      u = EXTRACT-MIN(Q)
8      for each v ∈ G.Adj[u]
9         if v ∈ Q and w(u,v) < v.key
10           v.π = u
11           v.key = w(u,v)
  • All vertices that are not in the tree reside in a min-priority queue Q based on a key attribute.
  • v.key is the minimum weight of any edge connecting v to a vertex in the tree
  • v.π points to the parent of v in the tree
  • G is a graph, w is a weight function, r is a root

The example given is as follows:

[![enter image description here][1]][1]

I am confused, why in step (c), edge $(b,c)$ is added instead of edge $(a,h)$. Below the diagram, there is a note saying:

In second step, the algorithm has a choice of adding either edge $(b,c)$ or edge $(a,h)$ to the tree since both are light edges crossing the cut.

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$. The line 8 says for **each v** ∈ G.Adj[u](i.e. 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$).

If what author says should occur, then there should be something like break construct on line 12 inside the if construct's body, which will result in exiting for loop and hence grabbing next u = EXTRACT-MIN(Q).

Am I correct? or I must be missing something very stupid. What's that? [1]: https://i.sstatic.net/TTwpR.png

added 12 characters in body
Source Link
Mahesha999
  • 1.8k
  • 7
  • 30
  • 45
Loading
Source Link
Mahesha999
  • 1.8k
  • 7
  • 30
  • 45
Loading