Test 3
Nasledovne ulohy vypracujte a odoslite ako jeden subor v jazyku C++, standard C++11 t.j. ziadne OS zavisle kniznice.
1. Zo suboru Graf.txt nacitaj graf a zisti kolko ma vrcholov (vrcholy su reprezentovane lubovolnymi celymi cislami - ID) (15 bodov). Graf reprezentuj ako maticu susednosti! (prave dve cisla za sebou predstavuju hranu t.j. 738 341 245 406 ma iba dve hrany a to 738 -> 341, 245 -> 406). Napln mnozinu M styrmi najmensimi ID cislami vrcholov (5 bodov)
2. Naimplementuj metodu 'bool cesta(Vrchol ID1, Vrchol ID2)', ktora zisti, ci existuje cesta medzi vrcholmi ID1->ID2. Zisti, ci existuje cesta z 0 do 56 a z 2 do 755. (20 bodov)
3. Aka je zlozitost metody cesta? (10 bodov)
4. Naimplementuj metodu, co najefektivnejsie, ktora zisti kam (do ktorych vrcholov) sa mozno dostat z mnoziny vrcholov M(vid 1.ulohu). (25 bodov) Vypiste pocet vrcholov, kam sa mozno dostat.(5 bodov)
Vysledky
(+nacitanie = 15b) Pocet uzlov : 300
(5b) Najmensie uzly : 0, 1, 2, 7
Cesta z 0 do 56 : existuje
(20b) Cesta z 2 do 755 : neexistuje
(10b) Narocnost BFS je O(|E|), cize s poctom hran 1879 je to : 1879
Algoritmus + vypis = 25b, pocet = 5b
Uzly dosiahnutelne z mnoziny M ( 299 ) : 0, 1, 2, 7, 8, 12, 15, 23, 30, 32, 34, 35, 36, 38, 39, 40, 41, 42, 47, 49, 50, 53, 55, 56, 59, 60, 61, 66, 69, 70, 79, 82, 88, 89, 93, 95, 96, 98, 109,
, 118, 121, 122, 124, 126, 127, 128, 137, 139, 140, 146, 148, 153, 154, 157, 161, 164, 169, 172, 173, 176, 181, 183, 184, 188, 190, 191, 193, 199, 204, 208, 209, 213, 220, 222, 223, 234, 236,
, 242, 245, 246, 248, 250, 253, 255, 256, 259, 262, 269, 273, 274, 281, 282, 288, 292, 295, 298, 299, 302, 303, 305, 310, 312, 313, 317, 318, 319, 321, 326, 327, 332, 333, 335, 337, 341, 342,
, 349, 350, 351, 352, 353, 354, 357, 361, 364, 368, 371, 374, 385, 386, 388, 391, 393, 398, 400, 405, 406, 411, 416, 421, 422, 424, 429, 430, 431, 441, 444, 445, 446, 466, 467, 477, 481, 483,
, 493, 495, 498, 501, 502, 503, 506, 507, 511, 512, 514, 515, 516, 521, 523, 528, 529, 533, 534, 537, 538, 544, 545, 558, 563, 568, 569, 573, 575, 576, 585, 586, 587, 588, 589, 590, 592, 595,
, 603, 606, 616, 621, 623, 624, 627, 633, 636, 638, 644, 646, 651, 655, 658, 672, 677, 678, 682, 684, 685, 687, 689, 690, 695, 696, 699, 707, 709, 710, 711, 713, 716, 717, 722, 723, 725, 729,
, 737, 738, 741, 744, 749, 753, 756, 758, 761, 762, 768, 769, 778, 779, 780, 781, 782, 786, 789, 791, 792, 796, 800, 801, 803, 805, 809, 810, 812, 818, 821, 823, 824, 826, 829, 832, 834, 835,
, 842, 843, 845, 848, 855, 857, 858, 862, 870, 871, 872, 875, 881, 883, 891, 892, 894, 896
Riesenie
Ukazkove riesenie - Test3.cpp
Dataset- Graf.txt