29.4 Prim และเลือกใช้ให้เหมาะกับกราฟ

Kruskal มองทั้งกราฟพร้อมกัน หยิบเส้นที่ถูกที่สุดจากตรงไหนก็ได้ ต้นไม้จึงงอกออกมาเป็นหลายกลุ่มแล้วค่อยรวมกัน อีกวิธีที่ได้ MST เหมือนกันคือ Prim ซึ่งปลูกต้นไม้ต้นเดียวจากโหนดเริ่มต้น แล้วขยายออกไปทีละโหนด โครงของโปรแกรมเหมือน Dijkstra ในบทที่ 28 แทบทุกบรรทัด หน้านี้เขียน Prim สองแบบ แบบใช้ priority_queue สำหรับกราฟทั่วไป กับแบบ O(N²) ที่ไม่ต้องเก็บเส้นเชื่อมเลย สำหรับกราฟที่ทุกคู่โหนดมีเส้นถึงกัน แล้วสรุปว่าโจทย์แบบไหนควรใช้วิธีไหน

ปลูกต้นไม้จากโหนดเดียว

เริ่มจากต้นไม้ที่มีโหนด 1 โหนดเดียว ทุกรอบดูเส้นเชื่อมทุกเส้นที่ปลายข้างหนึ่งอยู่ในต้นไม้ และอีกข้างอยู่นอกต้นไม้ หยิบเส้นที่ถูกที่สุด แล้วดึงโหนดปลายนอกเข้ามาในต้นไม้ ทำจนครบ N โหนด

เหตุผลที่ถูกเหมือนกับ Kruskal ในหน้า 29.3 ข้อพิสูจน์ตรงนั้นเลือก MST ต้น T ที่ตรงกับลำดับเส้นที่หยิบยาวที่สุดนับจากเส้นแรก แล้วใช้สองข้อ ข้อแรก เส้น f ที่ข้ามออกจากกลุ่ม A บนทางใน T ไม่ใช่เส้นที่หยิบไปแล้ว ข้อสอง f หนักไม่น้อยกว่าเส้น e ที่หยิบต่อ แลก f ออกใส่ e แทนจึงได้ MST ที่ตรงกับลำดับยาวขึ้นหนึ่งเส้น สำหรับ Prim กลุ่ม A ก็คือต้นไม้ที่ปลูกมาถึงตอนนั้น เส้นที่หยิบไปแล้วอยู่ในต้นไม้นี้ทั้งหมด f ที่ข้ามออกไปจึงไม่ใช่หนึ่งในนั้น และ e คือเส้นที่ถูกที่สุดที่ข้ามออกจาก A ตามนิยามของ Prim f ก็ข้ามออกจาก A เหมือนกัน จึงหนักไม่น้อยกว่า e ทันที

Prim ด้วย priority_queue

ถ้าทุกรอบไล่ดูเส้นเชื่อมทั้งหมดเพื่อหาเส้นที่ถูกที่สุดที่ข้ามออกไป ต้องไล่ M เส้น N รอบ เป็น O(NM) ใช้ priority_queue แบบหยิบค่าน้อยก่อนจากหน้า 20.5 ช่วยจำเส้นที่ข้ามออกไปแทน ทุกครั้งที่ดึงโหนด v เข้าต้นไม้ ใส่เส้นทุกเส้นของ v ที่ไปหาโหนดนอกต้นไม้ลงไปเป็นคู่ (น้ำหนัก, โหนดปลาย) แล้วหยิบคู่ที่น้ำหนักน้อยที่สุดออกมา

เส้นที่ใส่ไว้นานแล้วอาจไม่ข้ามออกจากต้นไม้แล้ว เพราะโหนดปลายถูกดึงเข้ามาทางเส้นอื่นไปก่อน แทนที่จะตามไปลบออกจากคิว ให้ตรวจตอนหยิบออกมา ถ้าโหนดปลายอยู่ในต้นไม้แล้วก็ทิ้งไป แบบเดียวกับการข้ามระยะเก่าใน Dijkstra

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

int main()
{
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, int>>> adj(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back(make_pair(v, w));
        adj[v].push_back(make_pair(u, w));
    }
    vector<bool> in_tree(n + 1, false);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; // (1)!
    pq.push(make_pair(0, 1)); // (2)!
    long long total = 0;
    int added = 0;
    while (!pq.empty()) {
        auto [w, v] = pq.top();
        pq.pop();
        if (in_tree[v]) { // (3)!
            cout << "skip " << v << " w=" << w << '\n';
            continue;
        }
        in_tree[v] = true;
        total += w;
        added++;
        cout << "add " << v << " w=" << w << '\n';
        for (auto [to, cost] : adj[v]) {
            if (!in_tree[to]) { // (4)!
                pq.push(make_pair(cost, to));
            }
        }
    }
    if (added == n) {
        cout << "total = " << total << '\n';
    } else {
        cout << "not connected" << '\n';
    }
    return 0;
}

1. เก็บคู่ (น้ำหนัก, โหนด) ให้ greater เรียงตามน้ำหนักก่อน และหยิบตัวน้อยที่สุดออกมาก่อน
2. โหนดเริ่มต้นเข้าต้นไม้ด้วยน้ำหนัก 0 ไม่มีเส้นไหนพามันเข้ามา จะเริ่มที่โหนดไหนก็ได้ MST มีน้ำหนักเท่ากัน
3. คู่เก่าที่โหนดปลายเข้าต้นไม้ไปแล้ว ทิ้งไป ไม่นับน้ำหนัก
4. ไม่ต้องใส่เส้นที่ไปหาโหนดในต้นไม้ เพราะไม่ได้ข้ามออกไปไหน

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

add 1 w=0
add 3 w=3
add 2 w=2
skip 2 w=4
add 4 w=5
add 5 w=1
skip 5 w=6
skip 4 w=7
add 6 w=8
skip 6 w=9
total = 19

ใช้กราฟเดียวกับหน้า 29.3 ได้ 19 เท่ากัน แต่ลำดับที่หยิบต่างจาก Kruskal Prim ดึง 3 เข้ามาก่อนด้วยเส้น 1-3 ราคา 3 แม้เส้น 4-5 ราคา 1 จะถูกกว่า เพราะตอนนั้น 4 กับ 5 ยังไม่ได้ติดกับต้นไม้ที่ปลูกจาก 1 ส่วนบรรทัด skip 2 w=4 คือคู่ของเส้น 1-2 ที่ใส่ไว้ตอนดึง 1 เข้ามา แต่ 2 เข้าต้นไม้ไปก่อนแล้วผ่าน 3 ด้วยราคา 2

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

กราฟที่ทุกคู่มีเส้นถึงกัน

โรงเรียนมีอาคาร N หลัง อยากเดินสายแลนให้ทุกอาคารต่อถึงกัน สายเดินตามทางเดินที่เป็นตารางตั้งฉาก สายระหว่างอาคารที่พิกัด (x₁, y₁) กับ (x₂, y₂) ยาว |x₁ - x₂| + |y₁ - y₂| เมตร ทุกคู่อาคารเดินสายถึงกันได้ กราฟจึงมีเส้นเชื่อม N(N - 1)/2 เส้น N = 5000 ก็มีถึง 12.5 ล้านเส้น Kruskal ต้องสร้างและเรียงทุกเส้น Prim ด้วย priority_queue ก็ต้องใส่เส้นลงคิวเป็นล้านๆ ครั้ง

กราฟแบบนี้เรียกว่า กราฟหนาแน่น (dense graph) M ใกล้ N² ใช้ Prim อีกแบบที่ไม่เก็บเส้นเชื่อมเลย ให้ best[v] คือราคาของเส้นที่ถูกที่สุดที่ต่อโหนด v นอกต้นไม้เข้ากับต้นไม้ ทุกรอบไล่หาโหนดนอกต้นไม้ที่ best น้อยที่สุด O(N) ดึงเข้ามา แล้วคำนวณระยะจากโหนดใหม่ไปหาโหนดนอกต้นไม้ทุกตัว ปรับ best ให้น้อยลงถ้าทำได้ อีก O(N) ทำ N รอบ รวมเป็น O(N²) ซึ่งเท่ากับจำนวนเส้นเชื่อม จึงเร็วที่สุดเท่าที่เป็นไปได้สำหรับกราฟที่ต้องดูทุกเส้น

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

int main()
{
    int n;
    cin >> n;
    vector<int> x(n), y(n);
    for (int i = 0; i < n; i++) {
        cin >> x[i] >> y[i];
    }
    vector<long long> best(n, LLONG_MAX); // (1)!
    vector<int> link(n, -1); // (2)!
    vector<char> in_tree(n, false);
    best[0] = 0;
    long long total = 0;
    for (int step = 0; step < n; step++) {
        int v = -1;
        for (int i = 0; i < n; i++) { // (3)!
            if (!in_tree[i] && (v == -1 || best[i] < best[v])) {
                v = i;
            }
        }
        in_tree[v] = true;
        total += best[v];
        if (link[v] != -1) {
            cout << "cable " << link[v] << "-" << v << " length " << best[v] << '\n';
        }
        for (int i = 0; i < n; i++) {
            long long d = abs(x[v] - x[i]) + abs(y[v] - y[i]);
            if (!in_tree[i] && d < best[i]) { // (4)!
                best[i] = d;
                link[i] = v;
            }
        }
    }
    cout << "total = " << total << '\n';
    return 0;
}

1. ยังไม่มีเส้นไหนต่อถึงต้นไม้ ให้เป็นค่าที่มากที่สุดของ long long ซึ่งไม่มีระยะจริงไหนเกิน
2. จำว่าค่า best[v] ได้มาจากเส้นที่ต่อกับโหนดไหน เพื่อพิมพ์ว่าเดินสายจากไหนไปไหน ถ้าโจทย์ถามแค่ผลรวม ไม่ต้องมีอาเรย์นี้
3. หาโหนดนอกต้นไม้ที่ต่อเข้าต้นไม้ได้ถูกที่สุด ลูปนี้แทน priority_queue
4. เส้นจาก v ไปหา i ถูกกว่าเส้นที่ดีที่สุดเดิมของ i ก็จำเส้นใหม่

5
0 0
2 2
3 0
5 4
1 5

cable 0-2 length 3
cable 2-1 length 3
cable 1-4 length 4
cable 1-3 length 5
total = 15

อาคารใช้หมายเลข 0 ถึง N - 1 ตามลำดับที่อ่าน อาคาร 0 ที่ (0, 0) เข้าต้นไม้ก่อน อาคาร 2 ที่ (3, 0) ห่าง 3 เมตรเป็นตัวแรกที่ดึงเข้ามา จากนั้นอาคาร 1 ที่ (2, 2) ห่างจากอาคาร 2 ไป 1 + 2 = 3 เมตร ส่วนอาคาร 4 กับ 3 ต่อจากอาคาร 1 ทั้งคู่ เพราะใกล้อาคาร 1 กว่าอาคารอื่นที่อยู่ในต้นไม้แล้ว สายรวม 15 เมตร โปรแกรมเก็บแค่อาเรย์ไม่กี่ตัวขนาด N ไม่ได้เก็บเส้นเชื่อมสักเส้น

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

วัดบนเครื่องเดียวกับหน้า 29.1 รันแต่ละแบบ 5 รอบ จับเวลาตั้งแต่อ่านข้อมูลเสร็จจนได้คำตอบ ตารางแรกเป็นกราฟสุ่มชุดเดียวกับหน้า 29.3 ซึ่ง M ประมาณ 2 ถึง 5 เท่าของ N เรียกว่า กราฟเบาบาง (sparse graph) วิธีตรงไปตรงมาคือ Prim ที่ทุกรอบไล่ดูเส้นทั้ง M เส้นหาเส้นที่ถูกที่สุดที่ข้ามออกจากต้นไม้

ตารางที่สองเป็นอาคาร N หลังพิกัดสุ่ม 0 ถึง 10⁶ ระยะแบบเดินตามตาราง ทุกคู่มีเส้นถึงกัน Kruskal กับ Prim แบบ priority_queue ต้องสร้างเส้นจากพิกัดทั้ง N(N - 1)/2 เส้นก่อน คอลัมน์สุดท้ายคือหน่วยความจำสูงสุดที่ Windows รายงานตอน N = 5000 แบบ -O2

กราฟเบาบาง Kruskal กับ Prim แบบ priority_queue เร็วพอๆ กัน ต่างกันไม่ถึงสิบเท่าและเร็วกว่าหนึ่งวินาทีมาก เลือกแบบที่เขียนแล้วไม่พลาดได้เลย แต่กราฟหนาแน่น Kruskal กับ Prim แบบ priority_queue ทั้งช้าและกินหน่วยความจำเป็นร้อยเมกะไบต์ ซึ่งเกินขีดจำกัดของหลายโจทย์ ส่วนแบบ O(N²) ที่ -O2 เร็วกว่าสองวิธีนั้นราว 30 ถึง 120 เท่า และแทบไม่ใช้หน่วยความจำ สังเกตว่าแบบ Code::Blocks ของแบบ O(N²) ที่ N = 5000 ช้ากว่า -O2 ราวสิบเท่า โปรแกรมคำนวณระยะก่อนเช็ก in_tree ทุกรอบจึงคำนวณระยะ N ครั้ง N รอบเป็น N × N = 25 ล้านครั้ง รวมกับลูปหาโหนดที่ best น้อยสุดอีก 25 ล้านรอบ ทุกรอบอ่าน vector หลายตัว งานแบบนี้ -O2 ปรับให้เร็วขึ้นได้มากเหมือนโปรแกรมที่ใช้ STL ทั่วไป ถ้าเก็บ in_tree เป็น vector<bool> แบบ Code::Blocks ที่ N = 5000 ช้าลงเป็น 1.28 วินาที เพราะต้องแกะบิตทุกครั้งที่อ่านตามหน้า 23.4 ส่วนแบบ -O2 เป็น 0.044 วินาที grader ใช้ -O2 จึงไม่ต้องกังวล

เลือกใช้อะไร

ลองทำให้พัง

แบบที่ 1 ลืม greater

ในโปรแกรม prim ประกาศคิวเป็น priority_queue<pair<int, int>> pq; ซึ่งสั้นกว่า แล้วป้อนข้อมูลเข้าชุดเดิม

add 1 w=0
add 2 w=4
add 4 w=5
add 6 w=8
add 5 w=9
add 3 w=7
skip 3 w=6
skip 3 w=3
skip 3 w=2
skip 5 w=1
total = 33

คอมไพล์ผ่าน ไม่มีคำเตือน ได้ 33 ซึ่งเป็นต้นไม้ที่ใช้ 1-2 2-4 4-6 5-6 และ 3-4 ต้นเดียวกับต้นราคา 33 ในหน้า 29.3 ไม่ใช่เรื่องบังเอิญ priority_queue ปกติหยิบค่ามากสุดก่อนตามหน้า 20.5 Prim จึงหยิบเส้นที่แพงที่สุดที่ข้ามออกไปทุกรอบ ได้ spanning tree ที่น้ำหนักรวม มากที่สุด ของกราฟนี้ ถ้าโจทย์ต้องการแบบนั้นจริง ก็ใช้ได้ ซึ่งจะเจอในหน้า 29.5

แบบที่ 2 ไม่ทิ้งคู่เก่า

ในโปรแกรม prim ลบสี่บรรทัดที่ตรวจ if (in_tree[v]) ตอนหยิบออกมา

add 1 w=0
add 3 w=3
add 2 w=2
add 2 w=4
add 4 w=5
add 5 w=1
add 4 w=5
add 5 w=6
add 4 w=7
add 6 w=8
add 6 w=8
add 6 w=8
add 6 w=9
add 6 w=9
not connected

โหนด 6 ถูกดึงเข้าต้นไม้ห้าครั้ง added นับได้ 14 ไม่เท่ากับ N โปรแกรมจึงบอกว่า not connected ทั้งที่กราฟต่อถึงกันหมด ถ้าพิมพ์ total แทน จะได้ผลรวมที่นับเส้นซ้ำไปหลายเส้น คู่เก่าในคิวยังอยู่เสมอ เพราะเราไม่ได้ลบมันตอนโหนดปลายเข้าต้นไม้ การตรวจตอนหยิบออกมาจึงขาดไม่ได้

สรุป

• Prim ปลูกต้นไม้จากโหนดเดียว หยิบเส้นที่ถูกที่สุดที่ข้ามออกจากต้นไม้ทุกรอบ ถูกต้องด้วยเหตุผลเดียวกับ Kruskal
• Prim ด้วย priority_queue แบบ greater ใส่คู่ (น้ำหนัก, โหนด) ตอนหยิบให้ทิ้งคู่ที่โหนดอยู่ในต้นไม้แล้ว ใช้เวลา O(M log M)
• กราฟที่ทุกคู่มีเส้นถึงกัน ใช้ Prim แบบ O(N²) กับอาเรย์ best ไม่ต้องเก็บเส้นเชื่อม
• กราฟเบาบางใช้ Kruskal หรือ Prim ก็ได้ กราฟหนาแน่นใช้ Prim แบบ O(N²) โจทย์ที่ต้องดูลำดับการรวมกลุ่มใช้ Kruskal
• ลืม greater ได้ maximum spanning tree และลืมทิ้งคู่เก่าได้โหนดซ้ำ