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]: (https://drive.google.com/file/d/1gCMm3s72kLakZike8aaPnhxLMQFjDAqw/view?usp=sharing)
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
20:56:13
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
20:56:13
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
→ Найти пользователя
→ Прямой эфир
[Help] How does Prim's algorithm prevent cycles in the MST?
Правка en1, от RahulHarpal, 2024-02-26 16:40:07
История
Правки
| Rev. | Язык | Кто | Когда | Δ | Комментарий | |
|---|---|---|---|---|---|---|
| en23 |
|
RahulHarpal | 2024-02-26 17:47:43 | 0 | (published) | |
| en22 |
|
RahulHarpal | 2024-02-26 17:47:00 | 0 | (saved to drafts) | |
| en21 |
|
RahulHarpal | 2024-02-26 17:29:40 | 0 | (published) | |
| en20 |
|
RahulHarpal | 2024-02-26 17:28:40 | 105 | ||
| en19 |
|
RahulHarpal | 2024-02-26 17:27:32 | 85 | ||
| en18 |
|
RahulHarpal | 2024-02-26 17:27:03 | 58 | ||
| en17 |
|
RahulHarpal | 2024-02-26 17:24:13 | 79 | ||
| en16 |
|
RahulHarpal | 2024-02-26 17:21:12 | 23 | ||
| en15 |
|
RahulHarpal | 2024-02-26 17:20:38 | 2 | Tiny change: 'ication:\n1. T is ' -> 'ication:\n\n1. T is ' | |
| en14 |
|
RahulHarpal | 2024-02-26 17:20:19 | 2 | Tiny change: 'added.**\n**Key po' -> 'added.**\n\n**Key po' | |
| en13 |
|
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 |
|
RahulHarpal | 2024-02-26 17:18:28 | 77 | ||
| en11 |
|
RahulHarpal | 2024-02-26 17:17:19 | 115 | ||
| en10 |
|
RahulHarpal | 2024-02-26 17:12:39 | 4 | ||
| en9 |
|
RahulHarpal | 2024-02-26 17:12:20 | 75 | ||
| en8 |
|
RahulHarpal | 2024-02-26 17:11:13 | 2 | Tiny change: 'QED!"_**\nFor clar' -> 'QED!"_**\n\nFor clar' | |
| en7 |
|
RahulHarpal | 2024-02-26 17:10:58 | 914 | ||
| en6 |
|
RahulHarpal | 2024-02-26 16:57:55 | 185 | ||
| en5 |
|
RahulHarpal | 2024-02-26 16:52:34 | 16 | ||
| en4 |
|
RahulHarpal | 2024-02-26 16:52:09 | 7 | ||
| en3 |
|
RahulHarpal | 2024-02-26 16:48:36 | 336 | ||
| en2 |
|
RahulHarpal | 2024-02-26 16:40:53 | 3 | Tiny change: 'e [slides]:\n(https://d' -> 'e [slides](https://d' | |
| en1 |
|
RahulHarpal | 2024-02-26 16:40:07 | 490 | Initial revision (saved to drafts) |
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 22.11.2024 20:38:47 (j1).
Десктопная версия, переключиться на мобильную.
При поддержке
