29.3 spanning tree และ Kruskal

อำเภอหนึ่งมีหมู่บ้าน N แห่ง และมีแนวถนนที่สร้างได้ M แนว แต่ละแนวมีราคา งบมีจำกัด จึงอยากเลือกสร้างแค่บางเส้น ให้ทุกหมู่บ้านไปมาหากันได้ และราคารวมน้อยที่สุด โจทย์แบบนี้ซ่อนอยู่ในข้อสอบค่าย 2 และ TOI หลายรูปแบบ ทั้งวางท่อ เดินสายไฟ ต่อสายแลน หน้านี้นิยามสิ่งที่ต้องหาให้ชัด คือ minimum spanning tree แล้วหามันด้วย Kruskal ซึ่งเป็น greedy ที่ใช้ union-find จากหน้า 29.1 และพิสูจน์ว่าทำไม greedy นี้ถึงถูก ด้วย exchange argument จากบทที่ 23

spanning tree

ภาพนี้คือหมู่บ้าน 6 แห่ง กับแนวถนน 9 แนว ตัวเลขบนเส้นคือราคาเป็นล้านบาท กราฟที่เส้นเชื่อมมีตัวเลขกำกับแบบนี้เรียกว่า กราฟถ่วงน้ำหนัก (weighted graph) ตัวเลขเรียกว่า น้ำหนัก (weight) แบบเดียวกับกราฟในบทที่ 28

ถ้าเลือกถนนชุดหนึ่งแล้วทุกหมู่บ้านไปถึงกันได้ ในบรรดาชุดที่ถูกที่สุด มีชุดที่ไม่มีวงจรเสมอ เพราะถ้ามีวงจร ตัดเส้นใดก็ได้บนวงจรนั้นทิ้ง หมู่บ้านก็ยังไปถึงกันได้ผ่านส่วนที่เหลือของวงจร และราคาไม่เพิ่ม เพราะราคาถนนไม่ติดลบ ตัดไปเรื่อยๆ จนไม่เหลือวงจร ชุดเส้นที่ต่อทุกโหนดถึงกันและไม่มีวงจร คือต้นไม้ที่ครอบคลุมทุกโหนด เรียกว่า spanning tree (ต้นไม้แผ่ทั่ว) และจากหน้า 29.2 ต้นไม้ที่มี N โหนดมีเส้นเชื่อม N - 1 เส้นพอดี กราฟนี้มีหลาย spanning tree เช่นต้นนี้

spanning tree ที่น้ำหนักรวมน้อยที่สุด เรียกว่า minimum spanning tree หรือ MST ของกราฟนี้คือต้นนี้ ราคา 19

ลองทุก spanning tree ไม่ไหว กราฟที่ทุกคู่โหนดมีเส้นเชื่อมกันมี spanning tree ถึง N^N-2 ต้น (สูตรของ Cayley) N = 10 ก็มีร้อยล้านต้นแล้ว N = 20 มีราว 2.6 × 10²³ ต้น ต้องมีวิธีที่ฉลาดกว่านั้น

Kruskal

Kruskal คิดแบบ greedy ตรงๆ เรียงเส้นเชื่อมจากเบาไปหนัก แล้วไล่หยิบทีละเส้น ถ้าเส้นนั้นไม่ทำให้เกิดวงจรกับเส้นที่หยิบไว้แล้ว ก็หยิบ ถ้าทำให้เกิดวงจรก็ข้าม คำถามว่า "ทำให้เกิดวงจรไหม" คือคำถามของหน้า 29.2 พอดี เส้น a-b ทำให้เกิดวงจรเมื่อ a กับ b อยู่กลุ่มเดียวกันแล้ว ซึ่ง unite ตอบได้พร้อมรวมให้ในตัว

#include <bits/stdc++.h>
using namespace std;

vector<int> parent, group_size;

int find_root(int x)
{
    if (parent[x] == x) {
        return x;
    }
    parent[x] = find_root(parent[x]);
    return parent[x];
}

bool unite(int a, int b)
{
    int root_a = find_root(a);
    int root_b = find_root(b);
    if (root_a == root_b) {
        return false;
    }
    if (group_size[root_a] < group_size[root_b]) {
        swap(root_a, root_b);
    }
    parent[root_b] = root_a;
    group_size[root_a] += group_size[root_b];
    return true;
}

int main()
{
    int n, m;
    cin >> n >> m;
    vector<tuple<int, int, int>> edges(m);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        edges[i] = {w, u, v}; // (1)!
    }
    sort(edges.begin(), edges.end());
    parent.resize(n + 1);
    group_size.assign(n + 1, 1);
    for (int i = 1; i <= n; i++) {
        parent[i] = i;
    }
    long long total = 0; // (2)!
    int used = 0;
    for (auto [w, u, v] : edges) {
        if (unite(u, v)) { // (3)!
            total += w;
            used++;
            cout << "take " << u << "-" << v << " w=" << w << '\n';
        } else {
            cout << "skip " << u << "-" << v << " w=" << w << '\n';
        }
    }
    if (used == n - 1) { // (4)!
        cout << "total = " << total << '\n';
    } else {
        cout << "not connected" << '\n';
    }
    return 0;
}

เก็บน้ำหนักไว้ช่องแรกของ tuple sort จึงเรียงตามน้ำหนักก่อนตามหน้า 16.4 น้ำหนักเท่ากันค่อยเรียงตามโหนด
N เป็นแสนและน้ำหนักถึง 10⁹ ผลรวมถึงราว 10¹⁴ เกิน int
รวมได้ แปลว่าสองปลายอยู่คนละกลุ่ม เส้นนี้ไม่ทำให้เกิดวงจร หยิบได้
หยิบได้ N - 1 เส้นแปลว่าต่อครบทุกหมู่บ้าน ถ้าได้น้อยกว่านั้น กราฟเดิมก็ไม่ได้ต่อถึงกันตั้งแต่แรก ไม่มี spanning tree

take 4-5 w=1
take 2-3 w=2
take 1-3 w=3
skip 1-2 w=4
take 2-4 w=5
skip 3-5 w=6
skip 3-4 w=7
take 4-6 w=8
skip 5-6 w=9
total = 19

4-5 2-3 1-3 เป็นสามเส้นที่ถูกที่สุด หยิบได้ทั้งหมด เส้นถัดไปคือ 1-2 ราคา 4 แต่ 1 กับ 2 ไปถึงกันได้แล้วผ่าน 3 จึงข้าม 2-4 ราคา 5 ต่อกลุ่ม {1, 2, 3} เข้ากับกลุ่ม {4, 5} ได้ จากนั้น 3-5 กับ 3-4 อยู่ในกลุ่มใหญ่เดียวกันแล้วทั้งคู่ ข้าม 4-6 พาหมู่บ้าน 6 เข้ามาเป็นเส้นที่ห้า ครบ N - 1 = 5 เส้น รวม 19 ตรงกับภาพข้างบน

ถ้าอยากให้เร็วขึ้นอีกนิด หยุดลูปได้ทันทีที่หยิบครบ N - 1 เส้น เพราะเส้นที่เหลือต้องถูกข้ามทั้งหมดแน่นอน แต่ไม่ได้เปลี่ยนความซับซ้อน งานที่หนักที่สุดคือการเรียง O(M log M) ส่วนการไล่เส้นทั้งหมดด้วย union-find ใช้ O(M α(N)) Kruskal ทั้งหมดจึงเป็น O(M log M)

ทำไมหยิบเส้นที่ถูกที่สุดก่อนถึงถูก

บทที่ 23 สอนว่า greedy ต้องพิสูจน์เสมอ เพราะหลายโจทย์ที่ greedy ดูน่าจะถูกกลับผิด เครื่องมือที่ใช้คือ exchange argument สมมติว่ามีคำตอบที่ดีที่สุดที่ต่างจากของ greedy แล้วแสดงว่าแลกชิ้นส่วนให้เหมือน greedy ได้ทีละชิ้นโดยไม่แย่ลง ใช้กับ Kruskal ได้แบบนี้

ให้เส้นที่ Kruskal หยิบตามลำดับคือ e₁ e₂ ไปจนถึง e_N-1 ในบรรดา MST ทุกต้น ให้ T เป็นต้นที่มีเส้นตามลำดับนี้ครบติดกันจากเส้นแรกได้ยาวที่สุด คือมี e₁ ถึง e_k ครบทุกเส้น โดย k มากที่สุดเท่าที่ MST ต้นไหนทำได้ ถ้า k = N - 1 ก็จบ เพราะ T มีทุกเส้นที่ Kruskal หยิบ และทั้งสองมี N - 1 เส้นเท่ากัน จึงเป็นต้นเดียวกัน ถ้าไม่ใช่ ให้ e คือ e_k+1 ซึ่งไม่อยู่ใน T สมมติ e ต่อโหนด a กับ b และตอนที่ Kruskal หยิบ e ซึ่งตอนนั้นหยิบไว้แล้วแค่ e₁ ถึง e_k ให้ A คือกลุ่มของ a ซึ่งไม่มี b อยู่

T เป็นต้นไม้ จึงมีทางเดินจาก a ไป b ในต้น T ทางนี้เริ่มใน A แต่จบนอก A จึงต้องมีเส้น f บนทางนี้ที่ข้ามจากในกลุ่ม A ออกไปนอกกลุ่ม
f ไม่ใช่ e₁ ถึง e_k เพราะเส้นที่หยิบแล้วทุกเส้นอยู่ภายในกลุ่มใดกลุ่มหนึ่งเสมอ ไม่มีเส้นไหนข้ามกลุ่ม และ f ก็ไม่ใช่ e เพราะ f อยู่ใน T แต่ e ไม่อยู่
Kruskal ยังไม่เคยพิจารณา f เพราะกลุ่มมีแต่รวมกันใหญ่ขึ้น ถ้าตอนนี้ปลายทั้งสองของ f อยู่คนละกลุ่ม ตอนก่อนหน้าก็ต้องอยู่คนละกลุ่ม ถ้าเคยพิจารณา f ไปแล้ว Kruskal ต้องหยิบมันไว้เป็นหนึ่งใน e₁ ถึง e_k ขัดกับข้อ 2
Kruskal พิจารณาจากเบาไปหนัก f ยังไม่ถูกพิจารณา จึงหนักไม่น้อยกว่า e

แลกกัน เอา f ออกจาก T แล้วใส่ e แทน เรียกต้นใหม่ว่า T' เอา f ออก ต้น T ขาดเป็นสองท่อน โดย a กับ b อยู่คนละท่อน เพราะ f อยู่บนทางเดียวที่เชื่อมสองตัวนี้ ใส่ e กลับเข้าไปก็ต่อสองท่อนนั้นเข้าหากัน T' จึงเป็น spanning tree ที่มีน้ำหนักรวมเท่ากับของ T ลบ f บวก e ซึ่งไม่มากกว่า T T' จึงเป็น MST ด้วย เส้นที่เอาออกคือ f ซึ่งไม่ใช่ e₁ ถึง e_k ตามข้อ 2 T' จึงยังมี e₁ ถึง e_k ครบ และมี e_k+1 เพิ่มมาอีกเส้น ตรงกับลำดับของ Kruskal ยาวกว่า T ขัดกับที่เลือก T มาให้ตรงยาวที่สุดแล้ว กรณีนี้จึงเกิดไม่ได้ ต้นที่ Kruskal ได้คือ MST

ทำไมต้องนับแบบติดกันจากเส้นแรก ไม่นับแค่ว่ามีเส้นของ Kruskal กี่เส้น เพราะ f อาจเป็นเส้นที่ Kruskal หยิบทีหลังก็ได้ ลองกับตัวเลขจริง ให้ T คือต้นราคา 33 ซึ่งใช้ 1-2 2-4 3-4 4-6 5-6 ต้นนี้ไม่ใช่ MST แต่ขั้นแลกทำงานแบบเดียวกัน Kruskal หยิบ 4-5 2-3 1-3 2-4 4-6 ตามลำดับ เส้นแรก 4-5 ไม่อยู่ใน T จึงตรงกัน 0 เส้น ตอนหยิบ 4-5 กลุ่มของ 4 คือ {4} คนเดียว ทางจาก 4 ไป 5 ในต้น T คือ 4-6-5 เส้นที่ข้ามออกจาก {4} คือ f = 4-6 ราคา 8 แลก 4-6 ออก ใส่ 4-5 ราคา 1 ได้ต้นใหม่ราคา 33 - 8 + 1 = 26 สังเกตว่า 4-6 ก็เป็นเส้นที่ Kruskal หยิบ แต่หยิบเป็นเส้นที่ห้า ต้นราคา 33 มีเส้นของ Kruskal 2 เส้นคือ 2-4 กับ 4-6 ต้นราคา 26 ก็มี 2 เส้นคือ 4-5 กับ 2-4 ถ้านับแค่จำนวน การแลกครั้งนี้ไม่ได้ทำให้เหมือนขึ้นเลย แต่ถ้านับแบบติดกันจากเส้นแรก ต้นใหม่ตรงกับลำดับของ Kruskal 1 เส้นแล้ว แลกต่อแบบเดียวกันจนครบ

ต้นก่อนแลก	e	กลุ่ม A ตอนหยิบ e	ทางใน T	f	ต้นหลังแลก	ตรงกับลำดับของ Kruskal
33	4-5 ราคา 1	{4}	4-6-5	4-6 ราคา 8	26	1 เส้นแรก
26	2-3 ราคา 2	{2}	2-4-3	2-4 ราคา 5	23	2 เส้นแรก
23	1-3 ราคา 3	{1}	1-2-3	1-2 ราคา 4	22	3 เส้นแรก
22	2-4 ราคา 5	{1, 2, 3}	2-3-4	3-4 ราคา 7	20	4 เส้นแรก
20	4-6 ราคา 8	{1, 2, 3, 4, 5}	4-5-6	5-6 ราคา 9	19	ครบ 5 เส้น

ทุกรอบ f หนักไม่น้อยกว่า e และต้นใหม่ตรงกับลำดับของ Kruskal ยาวขึ้นหนึ่งเส้นเสมอ จนจบที่ต้นราคา 19 ของ Kruskal ถ้ามีหลายเส้นน้ำหนักเท่ากัน MST อาจมีได้หลายต้น Kruskal ได้ต้นใดต้นหนึ่ง แต่น้ำหนักรวมเท่ากันเสมอ

เร็วขึ้นแค่ไหน

วิธีตรงไปตรงมาของการถามว่า "a กับ b ไปถึงกันแล้วหรือยัง" ก่อนมี union-find คือ BFS บนเส้นที่หยิบไว้แล้ว ซึ่งเป็นป่าที่มีไม่เกิน N - 1 เส้น ทุกเส้นที่พิจารณาต้อง BFS หนึ่งรอบ O(N) รวมเป็น O(MN) วัดบนเครื่องเดียวกับหน้า 29.1 กราฟสุ่มที่ต่อถึงกันหมด น้ำหนักสุ่ม 1 ถึง 10⁹ จับเวลาตั้งแต่เรียงจนได้คำตอบ รันแต่ละแบบ 5 รอบ

ข้อมูล	วิธี	Code::Blocks (`-Wall`)	`-O2`
N = 10⁴ M = 5 × 10⁴	Kruskal ตรวจด้วย BFS	6.7 วินาที	1.4 วินาที
N = 10⁴ M = 5 × 10⁴	Kruskal กับ union-find	0.029 วินาที	0.003 วินาที
N = 10⁵ M = 2 × 10⁵	Kruskal ตรวจด้วย BFS	ไม่ได้วัด	137 วินาที (รันครั้งเดียว)
N = 10⁵ M = 2 × 10⁵	Kruskal กับ union-find	0.121 วินาที	0.013 วินาที

ข้อมูลชุดที่สองมี N กับ M มากขึ้นสิบเท่ากับสี่เท่า งานของการตรวจด้วย BFS มากขึ้นราว 40 เท่า แต่เวลาจริงเพิ่มเกือบร้อยเท่า มากกว่าที่ Big O บอกไว้อีก แบบ Code::Blocks ไม่ได้วัด เพราะที่ N = 10⁴ ก็ช้ากว่า -O2 ราวห้าเท่าแล้ว ส่วน Kruskal กับ union-find เวลาส่วนใหญ่คือการเรียง ซึ่ง sort แบบ Code::Blocks ช้ากว่า -O2 ราวสิบเท่า แต่ยังเร็วมากอยู่ดี

ลองทำให้พัง

แบบที่ 1 เก็บ tuple ผิดลำดับ

ในโปรแกรม kruskal เก็บเส้นเป็น {u, v, w} ตามลำดับที่อ่านเข้ามา และแตกเป็น auto [u, v, w] ให้ตรงกัน คอมไพล์ผ่านโดยไม่มีคำเตือน ป้อนข้อมูลเข้าชุดเดิม

take 1-2 w=4
take 1-3 w=3
skip 2-3 w=2
take 2-4 w=5
skip 3-4 w=7
take 3-5 w=6
skip 4-5 w=1
take 4-6 w=8
skip 5-6 w=9
total = 26

ได้ 26 แทน 19 sort เรียงตามช่องแรกของ tuple ซึ่งตอนนี้คือหมายเลขโหนด เส้นจึงถูกพิจารณาตามเลขหมู่บ้าน ไม่ใช่ตามราคา 4-5 ราคา 1 ถูกข้าม เพราะมาทีหลังจนทั้งสองปลายถึงกันแล้ว ผลที่ได้ยังเป็น spanning tree ที่ถูกต้อง หยิบครบ 5 เส้น ไม่มีวงจร แค่ไม่ใช่ต้นที่ถูกที่สุด ถ้าโปรแกรมพิมพ์คำตอบที่ดูสมเหตุสมผลแบบนี้ ต้องตรวจด้วยมือกับตัวอย่างเล็กๆ ทุกครั้ง

แบบที่ 2 เก็บผลรวมใน int

เปลี่ยน long long total เป็น int total แล้วป้อนหมู่บ้าน 4 แห่งที่มีถนนราคาเส้นละ 10⁹

4 3
1 2 1000000000
2 3 1000000000
3 4 1000000000

take 1-2 w=1000000000
take 2-3 w=1000000000
take 3-4 w=1000000000
total = -1294967296

ราคาแต่ละเส้นอยู่ใน int ได้ แต่ผลรวมสามเส้นคือ 3 × 10⁹ เกิน int ล้นเป็นค่าติดลบตามหน้า 1.3 ราคารวมของ N - 1 เส้นใหญ่ได้ถึง (N - 1) เท่าของเส้นที่แพงที่สุด ให้คำนวณจากขอบเขตก่อนเขียนทุกครั้ง

สรุป

spanning tree คือชุดเส้นที่ต่อทุกโหนดถึงกันโดยไม่มีวงจร มี N - 1 เส้นพอดี MST คือต้นที่น้ำหนักรวมน้อยที่สุด
Kruskal เรียงเส้นจากเบาไปหนัก หยิบเส้นที่สองปลายอยู่คนละกลุ่มของ union-find ข้ามเส้นที่อยู่กลุ่มเดียวกัน ใช้เวลา O(M log M)
พิสูจน์ด้วย exchange argument MST ที่ต่างจาก Kruskal แลกเส้น f บนทางระหว่างสองปลายของ e กับเส้น e ได้โดยไม่แพงขึ้น
หยิบได้ไม่ครบ N - 1 เส้นแปลว่ากราฟไม่ต่อถึงกัน
เก็บน้ำหนักไว้ช่องแรกของ tuple และเก็บผลรวมด้วย long long