[Help] How does Prim's algorithm prevent cycles in the MST?

Revision en6, by RahulHarpal, 2024-02-26 16:57:55

Hello, I have enrolled in my college's "Design and Analysis of Algorithms" course. Recently we were studying Greedy algorithms and proving their correctness. I have a doubt about the correctness proof of Prim's Algorithm. How do we prove that it does not form a cycle during its execution? In the following snippet from our lecture slides, it says:

"No cycles ever get created in T. Why? Consider any iteration with current sets X and T. Suppose e gets added. Key point: e is the first edge crossing (X, V-X) that gets added to T -> its addition can't create a cycle in T (by Lonely Cut Corollary). QED!"

slide
dupe list

Tags graphs, minimun spanning tree, greedy

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en23 English RahulHarpal 2024-02-26 17:47:43 0 (published)
en22 English RahulHarpal 2024-02-26 17:47:00 0 (saved to drafts)
en21 English RahulHarpal 2024-02-26 17:29:40 0 (published)
en20 English RahulHarpal 2024-02-26 17:28:40 105
en19 English RahulHarpal 2024-02-26 17:27:32 85
en18 English RahulHarpal 2024-02-26 17:27:03 58
en17 English RahulHarpal 2024-02-26 17:24:13 79
en16 English RahulHarpal 2024-02-26 17:21:12 23
en15 English RahulHarpal 2024-02-26 17:20:38 2 Tiny change: 'ication:\n1. T is ' -> 'ication:\n\n1. T is '
en14 English RahulHarpal 2024-02-26 17:20:19 2 Tiny change: 'added.**\n**Key po' -> 'added.**\n\n**Key po'
en13 English RahulHarpal 2024-02-26 17:19:46 40 Tiny change: 'p=sharing), it says' -> 'p=sharing) (from Page No. 58, the MST part starts), it says'
en12 English RahulHarpal 2024-02-26 17:18:28 77
en11 English RahulHarpal 2024-02-26 17:17:19 115
en10 English RahulHarpal 2024-02-26 17:12:39 4
en9 English RahulHarpal 2024-02-26 17:12:20 75
en8 English RahulHarpal 2024-02-26 17:11:13 2 Tiny change: 'QED!"_**\nFor clar' -> 'QED!"_**\n\nFor clar'
en7 English RahulHarpal 2024-02-26 17:10:58 914
en6 English RahulHarpal 2024-02-26 16:57:55 185
en5 English RahulHarpal 2024-02-26 16:52:34 16
en4 English RahulHarpal 2024-02-26 16:52:09 7
en3 English RahulHarpal 2024-02-26 16:48:36 336
en2 English RahulHarpal 2024-02-26 16:40:53 3 Tiny change: 'e [slides]:\n(https://d' -> 'e [slides](https://d'
en1 English RahulHarpal 2024-02-26 16:40:07 490 Initial revision (saved to drafts)