ITI0140: Ülesanne 18
Dr Graafi operatsioonid
Olles tutvunud graafi otsingualgoritmidega on Sinu seekordseks ülesandeks järjekordselt tõestada tulnukrahvale oma suurepäraseid programmeerimisoskusi. Sinu ülesandeks on implementeerida laiuti otsing kahel erineval viisil:
1) Mäluta - kasutada järjekorda (queue) järgmise tipu valikuks ja ei jäta meelde tippe, mis on juba läbi käidud või mida on juba nähtud.
2) Mäluga - Kasutada järjekorda järgmise tipu valikuks ja hulka (set), et jätta meelde tipud, mis on juba läbi käidud.
Näide laiuti otsingust (joonisel paremal):
Mallis EX18.py on antud kaks funktsiooni, millest teine tagastab True/False õnnestunud otsingu ja ebaõnnestunud otsingu korral ja esimene hulga külastatud tippudest. Mõlemas funktsioonis tuleb esmalt luua juhuslik graaf etteantud node-tippude ja probability-kaarte moodustamise tõenäosuse abil kasutades NetworkX moodulit.
Näide:
1.funktsiooni vastavate parameetritega (bfs_memory(20,0.2,2,18)) juhusliku graafi genereerimisel võite saada järgmise pildi:
...mille korral tagastaks laiuti otsing järgmise hulga:
2, 8, 16, 17, 0, 3, 5, 6, 10, 12, 19, 15, 11, 14, 4, 7, 1, 18
Pildil on punasena teekond kujutatud alates algusest kuni 7-nda liikmeni.
Vastava dokumentatsiooni juhusliku graafi genereerimiseks leiab siit:
https://networkx.github.io/documentation/latest/reference/generators.html