Paieška grafuose

Išbandyti grafų vaizdavimo kompiuteryje būdus bei paieškos gilyn ir platyn algoritmus.
1.Pasirinkite 5–7 viršūnių orientuotą arba neorientuotą grafą, nubraižydami jį ant popieriaus lapo.
2. Nubraižytąjį grafą pavaizduokite vienu iš kompiuterinių grafų vaizdavimo būdų (pvz. Gretutinumo matricos pavidalų).
3. Pasirinkite bet kurį kitą, negu “2” užduotyje naudotas, grafo vaizdavimo būdą, ir parašykite programa, pervedančią grafą iš “2” užduotyje pasirinkto vaizdavimo būdo į “3” užduotyje pasirinktą būdą(pvz. į gretinumo sąrašą); patikrinkite programos teisingumą.
4. Sukurkite programą, kuri “2” ar “3” užduotyje pasirinktu būdu pavaizduotame grafe paieškos gilyn arba platyn metodu tikrintų, ar egzistuoja kelias tarp pasirinktos viršūnės v0 ir kitos pasirinktos viršūnės vg; patikrinkite programos teisingumą.
Užduoties sprendimo rezultatai ir pastebėjimai:
1. Nubraižykim neorientuotą grafą:
(1)
2. Tam, kad atlikti paieška platyn arba gilyn kompiuteriu, toks vaizdavimo būdas(1) yra nepatogus. Tokiu atveju mums reikia pavaizduoti grafa vienu iš kitų keturių būdų. Pasirinkim gretinumo matrica(2). Gretimumo matrica. Ir eilutėse ir stulpeliuose atidedamos viršūnės, o elementai, atitinkantys dvi viršūnes, kurios jungiamos tarpusavyje, žymimi “1”. Kiti elementai žymimi “0”. Ji atrodis taip:
(2)
Pastaba: toks grafo vaizdavimo būdas(2) yra patogiausias tam, kad atlikti paieška platyn arba gilyn kompiuteriu, nes šio atveju yra lengviausiai nustatyti viršūnių gretinumą.
3. Pervesim (2) vaizdavimo būda į gretimumo sąrašo vaizdavimo būdą(3). Gretinumo sąraše kiekvienai viršūnei pateikiamos jai gretimos. Musų atveju jis atrodis taip:
(3)
4. Aprašykime grafą G=(V,L), kur V – viršūnių aibė, L – lankų aibė. Mes žinome,...

Daugiau informacijos...

★ Klientai rekomenduoja

Šį rašto darbą rekomenduoja mūsų klientai. Ką tai reiškia?

Mūsų svetainėje pateikiama dešimtys tūkstančių skirtingų rašto darbų, kuriuos įkėlė daugybė moksleivių ir studentų su skirtingais gabumais. Būtent šis rašto darbas yra patikrintas specialistų ir rekomenduojamas kitų klientų, kurie po atsisiuntimo įvertino šį mokslo darbą teigiamai. Todėl galite būti tikri, kad šis pasirinkimas geriausias!