Tree-гийн хамгийн хол хоёр node-ын зайг хоёр BFS-ээр олох арга.

IntermediateХугацаа: O(n)Санах ой: O(n)

Эхлээд жижиг бодлого

5 node-той tree: 1-2, 2-3, 3-4, 2-5. Хамгийн хол хоёр node аль вэ?

Node 1-ээс BFS явуулбал хамгийн хол нь node 4 (3 edge). Node 4-өөс дахин BFS явуулбал хамгийн хол нь node 5 бөгөөд зай нь 3: 4 → 3 → 2 → 5. Хариу 3.

Энгийн аргаас санаа руу

Энгийн арга бол node бүрээс BFS явуулж, хамгийн их зайг авах. n удаа BFS тул O(n²). n = 100 000 бол 10 тэрбум үйлдэл.

Гол санаа: дурын node-оос хамгийн хол node-ыг a гэе. a заавал хамгийн урт path-ын нэг үзүүр байдаг. Тиймээс a дээрээс дахин нэг BFS явуулахад хамгийн хол node b нь нөгөө үзүүр болно. Хоёр BFS л хангалттай.

Нэр томьёо ба тэмдэглэгээ

diameter
Tree-гийн хамгийн хол хоёр node-ын хоорондох edge-ийн тоо.
d[u]
BFS эхэлсэн node-оос u хүртэлх зай (edge-ийн тоо). -1 бол очоогүй.
bfs(s)
s-ээс BFS явуулж, хамгийн сүүлд queue-гээс гарсан node-ыг буцаана. Тэр нь s-ээс хамгийн хол node.
a, b
Хамгийн урт path-ын хоёр үзүүр.
12345678
q (queue)
хоосон

Tree-гийн хамгийн хол хоёр node хооронд хэдэн edge байх вэ? Энэ тоог diameter гэнэ. Аль нэг node-оос хамгийн хол node-ыг олоод, тэндээс дахин хамгийн хол node-ыг олно. Хоёр BFS хангалттай.

Алхам 1 / 36
Хурд
  • Одоогийн node
  • Шинээр олдсон
  • Queue-д байгаа
  • Queue-гээс гарсан
  • a ба b
  • Хамгийн урт path
Слайд 1 / 6

Хамгийн хол хоёр node

Tree-гийн аль хоёр node хамгийн хол вэ? Бүх хосыг шалгавал удаан. Хоёр BFS хангалттай.

tree-diameter.cpp
#include <bits/stdc++.h>
using namespace std;
int n, d[100005];
vector<int> g[100005];
queue<int> q;
int bfs(int s) {
for (int i = 1; i <= n; i++) d[i] = -1;
d[s] = 0;
q.push(s);
int u = s;
while (!q.empty()) {
u = q.front();
q.pop();
for (int v : g[u]) {
if (d[v] == -1) {
d[v] = d[u] + 1;
q.push(v);
}
}
}
return u;
}
int main() {
cin >> n;
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
int a = bfs(1);
int b = bfs(a);
cout << d[b] << '\n';
return 0;
}

Юунд хэрэгтэй вэ?

Сүлжээний хамгийн урт замыг олно. Tree-тэй холбоотой олон бодлогод diameter гол түлхүүр болдог.

Яаж ажилладаг вэ?

1. Аль нэг node (жишээ нь 1) дээрээс BFS явуулж, бүх node-ын зайг d array-д бичнэ. 2. BFS хамгийн сүүлд гаргасан node-ыг a гэе. Энэ бол хамгийн хол node. 3. Node a дээрээс дахин BFS явуулна. 4. Энэ удаа хамгийн сүүлд гарсан node-ыг b гэе. Энэ нь a дээрээс хамгийн хол node. 5. d[b] бол tree-гийн diameter: хамгийн урт path-ын edge-ийн тоо. Оролт: n, дараа нь n − 1 мөрөнд «u v» (tree-гийн edge).

Яагаад зөв, хэр хурдан бэ?

BFS node-уудыг зайн дарааллаар гаргадаг тул хамгийн сүүлд гарсан node хамгийн хол байна. Хамгийн урт path-ын аль нэг үзүүрээс хамгийн хол node нөгөө үзүүр нь болдог. Мөн дурын node-оос хамгийн хол node заавал ямар нэг хамгийн урт path-ын үзүүр байдаг (үгүй бол илүү урт path байгуулж болдгоор батлагддаг). Тиймээс a нь үзүүр, a дээрээс хамгийн хол b нь нөгөө үзүүр, d[b] нь diameter.

Хоёр BFS тус бүр O(n), нийт O(n). n = 100 000 дээр 200 000 орчим алхам.

Түгээмэл алдаа

  • Хоёр дахь BFS-ийн өмнө d array-г -1 болгож цэвэрлэхгүй байх. Код bfs-ийн эхэнд үүнийг хийдэг.
  • Хариу болгож node-ын тоог хэвлэх. Diameter бол edge-ийн тоо: 3 node-той гинжийн diameter 2.
  • Жинтэй tree дээр BFS ашиглах. Жинтэй бол DFS-ээр жинг нэмж зай тоол. BFS зөвхөн edge-ийн тоог л зөв олно.

Хязгаарын тохиолдол

  • n = 2: нэг edge, хариу 1.
  • Гинж (1-2-3-…-n): хариу n - 1.
  • Star (node 1 бусадтай бүгдтэй холбоотой): хариу 2.

Өөрийгөө шалга

  1. 5 node-той star (1-2, 1-3, 1-4, 1-5)-ын diameter хэд вэ?

    Хариу харах

    2. Дурын хоёр навч хооронд node 1-ээр дамжсан 2 edge-тэй path бий.

  2. Яагаад нэг BFS хангалтгүй вэ?

    Хариу харах

    Node 1 tree-гийн дунд байж болно. Тэгвэл node 1-ээс хамгийн хол зай diameter-ийн хагас орчим л болно.

Гурван дадлага

Hint-ээ нээхээс өмнө өөрөө оролдоорой.

  1. 1.6 node-той гинж 1-2, 2-3, 3-4, 4-5, 5-6 дээр a, b хоёр ямар node болох вэ? Хариу хэд вэ?

    Hint харах

    Эхний BFS node 1-ээс эхэлнэ.

    Хариу ба тайлбар

    a = 6, b = 1, хариу 5.

  2. 2.Edge бүр жинтэй (u v w) бол diameter-ийг олдог болго.

    Hint харах

    BFS-ийн оронд DFS ашиглаад d[v] = d[u] + w гэж бич. Tree-д node бүрт нэг л path байдаг.

    Хариу ба тайлбар

    dfs(u, p) нь хөрш v != p бүрт d[v] = d[u] + w гээд гүнзгийрнэ. d хамгийн их node-ыг a гэж аваад a дээрээс дахин DFS хийнэ. Хариу нь хоёр дахь DFS-ийн хамгийн их d.

  3. 3.Tree-гийн "төв" node-ыг ол: бусад бүх node хүртэлх хамгийн их зай нь хамгийн бага байх node.

    Hint харах

    Хоёр дахь BFS-ийн үед parent-ыг хадгалбал b дээрээс a хүртэлх path-ыг сэргээж болно.

    Хариу ба тайлбар

    b дээрээс parent-аар a хүртэл ухарч path-ыг цуглуул. Diameter-ийг D гэвэл path-ын D / 2 дахь node төв болно. D сондгой бол дундах хоёр node хоёулаа төв.

Жишээ

Оролт

8
1 2
1 3
2 4
2 5
3 6
6 7
7 8

Гаралт

6