Direktno rešenje

Naivno rešenje podrazumeva da za svaki čvor \(s \in V\) algoritmom pretragom u širinu pronađemo najudaljeniji čvor \(u \in V\). Tada će dijametar drveta \(T\) biti najveće rastojanje ovakvih parova čvorova. Složenost ovog pristupa je \(O(|V|^2)\), jer imamo \(|V|\) poziva algoritma pretrage u širinu nad drvetom čija je složenost \(O(|V|)\).

Rešenje koje koristi dva poziva algoritma pretrage u širinu

Bolje rešenje dobijamo tako što iz proizvoljnog čvora \(s \in V\) pokrenemo algoritam pretrage u širinu. Čvor \(a \in V\) koji je poslednji posećen tokom pretrage je čvor drveta \(T\) koji je na najvećem rastojanju od čvora \(s\). Sada iz čvora \(a\) pokrenemo algoritam pretrage u širinu i, ponovo, evidentiramo poslednjih posećeni čvor \(b\) – on će biti čvor koji je na najvećem rastojanju od čvrova \(a\) u drvetu \(T\). Tvrdimo da će \(d(a, b)\) biti dijametar drveta. Složenost algoritma je \(O(|V|)\), jer imamo samo dva poziva pretrage u širinu nad drvetom \(T\).

Pokažimo sada korektnost ovog algoritma. U dokazu koristimo činjenicu da postoji jedinstveni put između svaka dva čvora drveta, kao i da je \(d(x, y) = d(y, x)\).

Neka je \(T=(V, E)\) drvo, \(s \in V\) njegov proizvoljni čvor, i neka je \(u \in V\) čvor koji najudaljeniji od \(s\), odnosno koji je poslednji pronađen u pretrazi u širinu iz \(s\). Takođe, neka je \(d(a, b)\) dijametar drveta \(T\), gde su \(a \in V\) i \(b \in V\). Jasno je da \(a\), \(b\) i \(u\) moraju biti listovi, jer u protivnom \(d(a, b)\) ne bi bio dijametar i \(u\) ne bi bio poslednji pronađen u pretrazi u širinu. Neka je \(t\) najniži zajednički predak čvorova \(a\) i \(b\) u drvetu \(T\).

Pokažimo da \(t\) mora biti predak od \(u\). Pretpostavimo da \(t\) nije predak od \(u\), odnosno neka je \(r\) najniži zajednički predak od \(u\) i \(t\). Onda važi \(d(u, s) \geq d(u, r)\). Kako je \(u\) pronađen poslednji u pretrazi u širinu, onda važi \(d(u, r) + d(r, s) = d(u, s) \geq d(a, s) = d(a, r) + d(r, s)\), te \(d(u, r) \geq d(a, r)\). Kako je \(r\) predak od \(t\), i \(r \neq t\), imamo \(d(a, r) = d(a, t) + d(t, r) \geq d(a, t) + 1 > d(a, t)\). Iz ove nejednakosti, zajedno sa \(d(u, r) \geq d(a, r)\), sledi: \(d(u, r) > d(a, t)\). Iz čega važi \(d(u, r) + d(r, t) + d(t, b) > d(a, t) + d(t, b)\), te je \(d(u, b) > d(a, b)\). Što je u suprotnosti sa činjenicom da je \(d(a, b)\) dijametar. Zaključujemo da \(t\) mora biti predak od \(u\).

Kako je \(u\) poslednji posećen tokom pretrage u širinu važi \(d(s, t) + d(t, u) = d(s, u) \geq d(s, a) = d(s, t) + d(t, a)\), te je \(d(t, u) \geq d(t, a)\). Iz ovoga sledi \(d(b, t) + d(t, u) \geq d(b, t) + d(t, a)\), te je \(d(b, u) \geq d(b, a)\). Iz ove nejednakosti, zajedno sa činjenicom da je \(d(a, b)\) dijametar, tj. \(d(b, a) \geq d(b, u)\), važi \(d(u, b) = d(a, b)\). Zbog toga, \(u\) mora biti krajnji čvor nekog dijametra, te će druga pretraga u širinu, pokrenuta iz čvora \(u\), pronaći najduži put koji mora biti dijametar.

#include <iostream>
#include <vector>
#include <map>
#include <queue>

using namespace std;

class Graph
{
private:
    int number_of_nodes;
    vector<vector<int>> neighbours_list;

private:
    pair<int, int> bfs(int source) {
        vector<int> distances(number_of_nodes, -1);

        queue<int> q;
        q.push(source);
        distances[source] = 0;

        int last_visited = source;

        while (!q.empty()) {
            int u = q.front();
            q.pop();

            for (auto v : neighbours_list[u]) {
                if (distances[v] == -1) {
                    distances[v] = distances[u] + 1;
                    q.push(v);
                    last_visited = v;
                }
            }
        }

        return { last_visited, distances[last_visited] };
    }

public:
    Graph(int number_of_nodes) {
        this->number_of_nodes = number_of_nodes;
        neighbours_list.resize(number_of_nodes);
    }

    void add_edge(int u, int v) {
        neighbours_list[u].push_back(v);
        neighbours_list[v].push_back(u);
    }

    int diameter() {
        auto [first_end_point, _] = bfs(0);
        auto [second_end_point, diameter] = bfs(first_end_point);
        return diameter;
    }
};

int main() {
    int number_of_nodes;
    cin >> number_of_nodes;

    Graph *G = new Graph(number_of_nodes);

    int u, v;
    for (int i = 0; i < number_of_nodes - 1; i++) {
        cin >> u >> v;
        G->add_edge(u, v);
    }

    cout << G->diameter() << endl;

    delete G;
    return 0;
}