Algoritmi → Grafovi i stabla → Stabla: pojmovi, obilazak, podstabla i prečnik

Stabla: pojmovi, obilazak, podstabla i prečnik

Šta je stablo?

Graf sa n čvorova je stablo ako važi bilo koje od ovih (sva su jednaka): povezan je i nema ciklus; povezan je i ima tačno n − 1 granu; između svaka dva čvora postoji tačno jedan put.

          1            dubina 0
        / | \
       2  3  4         dubina 1
      / \     \
     5   6     7       dubina 2
                \
                 8     dubina 3

Obilazak stabla: roditelji i dubine

Stablo se zadaje kao n − 1 grana. Obilazak u dubinu (DFS) iz korena određuje roditelja i dubinu svakog čvora. Umesto niza posecen dovoljno je ne vraćati se u roditelja – u stablu nema drugih ciklusa.

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> graf;
vector<int> roditelj, dubina;

void dfs(int v, int r) {              // r = roditelj čvora v
    roditelj[v] = r;
    for (int u : graf[v]) {
        if (u == r) continue;         // ne vraćamo se nazad
        dubina[u] = dubina[v] + 1;
        dfs(u, v);
    }
}

int main() {
    int n;
    cin >> n;
    graf.resize(n + 1);
    roditelj.resize(n + 1);
    dubina.assign(n + 1, 0);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        graf[u].push_back(v);
        graf[v].push_back(u);
    }
    dfs(1, 0);                        // koren je 1, njegov "roditelj" je 0
    for (int v = 1; v <= n; v++)
        cout << v << ": roditelj " << roditelj[v] << ", dubina " << dubina[v] << endl;
    return 0;
}

Veličina podstabla

Veličina podstabla čvora v je 1 (sam v) plus zbir veličina podstabala njegove dece. Deca se obrađuju pre roditelja, pa veličinu računamo posle rekurzivnih poziva (obilazak „posle“, postorder).

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> graf;
vector<int> velicina;

void dfs(int v, int r) {
    velicina[v] = 1;                  // sam čvor v
    for (int u : graf[v]) {
        if (u == r) continue;
        dfs(u, v);
        velicina[v] += velicina[u];   // dodaj podstablo deteta
    }
}

int main() {
    int n;
    cin >> n;
    graf.resize(n + 1);
    velicina.assign(n + 1, 0);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        graf[u].push_back(v);
        graf[v].push_back(u);
    }
    dfs(1, 0);
    for (int v = 1; v <= n; v++) cout << velicina[v] << " ";
    cout << endl;
    return 0;
}

Prečnik stabla

Prečnik je najveće rastojanje (broj grana) između dva čvora stabla. Postoji lep trik sa dva obilaska:

1. iz bilo kog čvora nađi najudaljeniji čvor A;
2. iz A nađi najudaljeniji čvor B;
3. rastojanje od A do B je prečnik.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int n;
vector<vector<int>> graf;

// BFS iz čvora s; vraća udaljenosti svih čvorova od s
vector<int> bfs(int s) {
    vector<int> d(n + 1, -1);
    queue<int> q;
    d[s] = 0;
    q.push(s);
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (int u : graf[v])
            if (d[u] == -1) {
                d[u] = d[v] + 1;
                q.push(u);
            }
    }
    return d;
}

int main() {
    cin >> n;
    graf.resize(n + 1);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        graf[u].push_back(v);
        graf[v].push_back(u);
    }
    vector<int> d1 = bfs(1);
    int A = 1;
    for (int v = 1; v <= n; v++) if (d1[v] > d1[A]) A = v;   // najdalji od 1
    vector<int> d2 = bfs(A);
    int B = A;
    for (int v = 1; v <= n; v++) if (d2[v] > d2[B]) B = v;   // najdalji od A
    cout << "precnik = " << d2[B] << endl;
    return 0;
}

U primeru je prečnik put 5 – 2 – 1 – 4 – 7 – 8 dužine 5. BFS je ovde korišćen umesto DFS-a da ne bi bilo duboke rekurzije.

Stablo zadato nizom roditelja

Često se stablo zadaje drugačije: za svaki čvor osim korena dat je njegov roditelj (p[2], p[3], …, p[n]). Tada graf pravimo tako što svakom roditelju dodamo dete: deca[p[v]].push_back(v). Ako je uvek p[v] < v, veličine podstabala mogu se izračunati i bez rekurzije – prolaskom od n unazad do 2: vel[p[v]] += vel[v].

Zadaci za vežbu

Za svaki zadatak postoji primer, uputstvo i rešenje. Rešenja su provereno tačna na primerima iz teksta.

Proveri znanje