Hej, nie rozumiem kilku rzeczy z MST metodą Prima:
Pytanie_1:
Załóżmy, że wierzchołki to miasta, a krawędzie to odcinki między miastami. Chcę odbyć trasę według tych krawędzi, tak jak ponizej. Dojechałem do miasta o indeksie 4, następnie 5 i muszę przecież wrócić do 4 żeby kontynuować trasę:
-dlaczego wiec nie jest brane pod uwagę to, że po dojechaniu z wierzchołka 5 muszę przecież wrócić do wierzchołka 4 aby kontynuować trasę więc do wagi powinienem dodać kolejne 2km?
Widać to na prostszym grafie:
- Czyli metodą Prima wybieram sobie wierzchołek 0.
- Porównując wagi dodaję na początku 3, a potem 4 wiec waga to 7km.
- Ale gdybym chciał odwiedzić wszystkie miasta począwszy od 0 do 1 to daje 3km, z 1 muszę wrócić do 0 więc +3km, z 0 do 2 +4km, a wiec 3+3+4=10
- screenshot-20240504030607.png (58 KB) - ściągnięć: 8
- screenshot-20240504033051.png (4 KB) - ściągnięć: 6