Puu on yhtenäinen ja syklitön verkko, jossa on $n$ solmua ja $n-1$ kaarta. Puussa jokaisen kahden solmun välillä on yksikäsitteinen polku.

Tutustumme tällä viikolla puiden käsittelyn perustekniikoihin, joita ovat puun juurtaminen sekä dynaaminen ohjelmointi.

Esimerkki

Tässä on esimerkkinä puu, jossa on $6$ solmua ja $5$ kaarta:

Yleensä hyvä tapa tallentaa puu on vieruslistaesitys luomalla taulukko, jossa on vektoreita. Esimerkiksi voimme tallentaa yllä olevan puun näin:

vector<int> tree[7];
tree[1].push_back(2);
tree[1].push_back(3);
tree[1].push_back(4);
tree[2].push_back(1);
tree[2].push_back(5);
tree[2].push_back(6);
tree[3].push_back(1);
tree[4].push_back(1);
tree[5].push_back(2);
tree[6].push_back(2);

Juurtaminen

Puun käsittelyä helpottaa usein, jos valitsemme yhden sen solmuista juureksi. Tyypillisesti valitsemme juureksi solmun $1$.

Esimerkiksi äskeinen puumme näyttää juurrettuna tältä:

Tämän jälkeen puun solmut asettuvat tasoittain juuren alapuolelle, ja jokaisesta solmusta alkaa alipuu, jonka juurena se on.

Läpikäynti

Voimme käydä läpi kaikki puun solmut juuresta alkaen syvyyshaulla. Esimerkiksi seuraava funktio tulostaa kaikki puun solmut:

void dfs(int node, int prev) {
    cout << "solmu " << node << "\n";
    for (auto next : tree[node]) {
        if (next == prev) continue;
        dfs(next,node);
    }
}

Tulostaminen alkaa kutsumalla funktiota dfs(1,0). Parametri node on nykyinen solmu ja parametri prev on edellinen solmu. Läpikäynti etenee kaikkiin solmuihin edellistä solmua lukuun ottamatta.

Esimerkissämme tulostus on seuraava:

solmu 1
solmu 2
solmu 5
solmu 6
solmu 3
solmu 4

Dynaaminen ohjelmointi

Voimme laskea läpikäynnin yhteydessä puun solmuihin tietoa dynaamisella ohjelmoinnilla. Esimerkiksi seuraava koodi luo taulukon count, joka kertoo jokaiselle solmulle, montako solmua sen alipuussa on:

void dfs(int node, int prev) {
    count[node] = 1;
    for (auto next : tree[node]) {
        if (next == prev) continue;
        dfs(next,node);
        count[node] += count[next];
    }
}

Seuraava koodi puolestaan laskee jokaisesta solmusta taulukkoon length, kuinka pitkä on pisin solmusta alaspäin lähtevä polku:

void dfs(int node, int prev) {
    length[node] = 0;
    for (auto next : tree[node]) {
        if (next == prev) continue;
        dfs(next,node);
        length[node] = max(length[node],length[next]+1);
    }
}

Suurin riippumaton joukko

Riippumaton joukko on joukko verkon solmuja, joille pätee, että minkään kahden solmun välillä ei ole kaarta verkossa. Yleisessä verkossa suurimman riippumattoman joukon etsiminen on NP-vaikea ongelma, mutta puussa se onnistuu melko helposti dynaamisella ohjelmoinnilla.

Ideana on luoda taulukko count, joka kertoo jokaiselle solmulle $x$, mikä on suurin riippumattoman joukon koko solmusta $x$ alkavassa alipuussa, jos $x$ on mukana (1) tai ei ole mukana (0) joukossa. Seuraava koodi luo taulukon:

void dfs(int node, int prev) {
    count[node][1] = 1;
    count[node][0] = 0;
    for (auto next : tree[node]) {
        if (next == prev) continue;
        dfs(next,node);
        count[node][1] += count[next][0];
        count[node][0] += max(count[next][0],count[next][1]);
    }
}

Kun juurena on solmu $1$, suurin riippumattoman joukon koko on suurempi taulukon kohdassa $1$ olevista luvuista.