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ä:
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.