VERKKOTEORIAA

Verkon läpikäynti

Usein on pystyttävä käymään verkon kaikki solmut (tai kaaret) läpi, esimerkiksi jotain tietoa haettaessa. Haku voidaan suorittaa eri järjestyksissä. Verkon tyypilliset läpikäyntijärjestykset ovat Depth-First-Search (DFS) (syvyyssuuntainen läpikäynti) Breadth-First-Serach (BFS) (leveyssuuntainen läpikäynti). Läpikäynnissä on tärkeää muistaa missä solmuissa on jo käyty, helpoiten tämä voidaan toteuttaa värittämällä jo läpikäydyt solmut.

DFS - haku määritellään rekursiivisesti. Käydään verkon kaikki solmut läpi seuraavalla tavalla:

1) Vieraile solmussa

2) Tutki, onko solmun viereisissä solmuissa vierailtu

3) Jos jossakin naapuri solmussa ei ole vierailtu, kutsu DFS:ää tälle solmulle

Haussa lähdetään siis yhdestä solmusta muodostamaan ketjua niin, ettei vierailla missään solmussa kuin kerran; kun joudutaan umpikujaan, palataan edelliseen risteykseen ja tutkitaan seuraava reitti

BFS haussa taas lähdetään yhdestä solmusta ja edetään kaikkia siitä lähteviä ketjuja, seuraavista solmuista taas kaikkia jne.

DFS ja BFS menetelmien etuna on se, että niitä voidaan sopivasti modifoituina käyttää moniin ongelmiin, esimerkiksi verkon yhtenäisyyden testaukseen. Monissa verkkoalgoritmeissa on osana verkon (tai sen aliverkkojen) yhtenäisyyden testauksia. Verkko on yhtenäinen, jos DFS tai BFS menetelmällä tullaan vierailleeksi kaikissa solmuissa.

Esimerkki 5 DFS läpikäynti

Esimerkki 6 DFS läpikäynti

Esimerkki 7 BFS läpikäynti

Harjoitustehtävä 5 Onko verkko 4 yhtenäinen? Jos on, osoita se BFS menetelmällä.

Kuva 11: Verkko 4

Harjoitustehtävä 6 Osoita Verkon 4 yhtenäisyys myös DFS menetelmällä.

Harjoitustehtävien ratkaisut