Tehtävä 1 - Labyrintti¶

Labyrintin jokaisesta risteyksestä voi päästä vasemmalle, oikealle, ylös ja/tai alas.

1. Miten kuvaisit tälläisen labyrintin graafina? Kirjoita graafin solmulle sopiva C++-struct.
2. Kerro, kuinka löydät tiesi ulos sokkelosta. Sinulla on taskussasi iso pussi täynnä vanhoja kolikoita tai punainen värikynä.

Tehtävä 2 - Graafi¶

Tässä harjoituksessa oletetaan, että graafilla tai digraafilla on seuraava ominaisuus: mille tahansa kahdelle solmulle x ja y on aina polku x:stä y:hyn ja y:stä x:ään. BFS:ää suoritettaessa voidaan muodostaa ns. BF-puu. Esimerkiksi yllä olevassa graafissa, jos käytämme k:tä aloitussolmuna, yksi mahdollinen BF-puu, joka voidaan valmistaa, on seuraava:

Solmujen vieressä olevat numerot kertovat järjestyksen, jolla solmut ovat lisätty BF-puuhun. Oleta, että on tarpeen tietää, mitkä solmut ovat BF-puun lehtiä. Yllä olevan puun lehtiä ovat {d, g, e, a, f}.

Tyypillinen BFS tuottaa seuraavat tulokset:

• kunkin solmun etäisyys aloitussolmusta
• BF-puun kunkin solmun vanhempi

Kirjoita pseudokoodi BFS:lle, joka tuottaa myös joukon, joka sisältää saadun BF-puun lehdet.