27.1 กราฟและการเก็บในโปรแกรม

โจทย์ที่พูดถึงหมู่บ้านกับถนน เพื่อนกับเพื่อน สถานีรถไฟฟ้า ทางเดินในเขาวงกต หรือการเทน้ำจากขวดหนึ่งไปอีกขวด ดูต่างกันมาก แต่ถ้าตัดเรื่องราวทิ้ง ทุกข้อเหลือแค่ของหลายชิ้นกับคู่ของที่เชื่อมกัน สิ่งนี้เรียกว่า กราฟ (graph) เรียนวิธีคิดกับกราฟครั้งเดียว ใช้ได้กับโจทย์ทุกแบบที่ว่ามา หน้านี้ทำความรู้จักกราฟ แล้วเก็บกราฟลงในโปรแกรมสองแบบ คือ adjacency matrix กับ adjacency list พร้อมวัดว่าเลือกผิดแบบแล้วเสียอะไร

กราฟคืออะไร

กราฟประกอบด้วยสองอย่าง จุดยอด (vertex) คือของแต่ละชิ้น เช่น บ้านหนึ่งหลัง และ เส้นเชื่อม (edge) คือคู่ของจุดยอดที่เชื่อมกันโดยตรง เช่น ถนนหนึ่งเส้นระหว่างบ้านสองหลัง โจทย์มักเรียกจุดยอดว่า node และใช้ตัวอักษร V แทนจำนวนจุดยอด E แทนจำนวนเส้นเชื่อม หรือใช้ N กับ M ตามข้อมูลเข้า

ภาพนี้คือหมู่บ้านเล็กๆ ที่มีบ้าน 9 หลัง หมายเลข 1 ถึง 9 และถนน 9 เส้น ตัวอย่างในหน้า 27.1 ถึง 27.3 ใช้กราฟนี้ ยกเว้นตัวอย่างกราฟมีทิศและกราฟมีน้ำหนักซึ่งมีภาพของตัวเอง

ตำแหน่งที่วาดไม่มีความหมาย ย้ายบ้าน 9 ไปไว้มุมซ้ายก็ยังเป็นกราฟเดิม สิ่งเดียวที่สำคัญคือใครเชื่อมกับใคร คำที่โจทย์ใช้บ่อยมีดังนี้

ต้นไม้ในบทที่ 26 ก็คือกราฟแบบหนึ่ง เป็นกราฟที่ทุกจุดเดินถึงกันหมด และไม่มีวงจรเลย ต้นไม้ N จุดจึงมีเส้นเชื่อม N - 1 เส้นพอดี กลุ่มบ้าน 7 8 9 ในภาพเป็นต้นไม้ ส่วนกลุ่มบ้าน 1 ถึง 6 ไม่ใช่ เพราะมีวงจร ความต่างข้อนี้คือเหตุผลที่บทนี้ต้องมีของใหม่ที่ต้นไม้ไม่ต้องใช้ คือการจำว่าจุดไหนเคยไปแล้ว เพราะในกราฟทั่วไป เดินไปเรื่อยๆ อาจวนกลับมาที่เดิม

กราฟสามแบบที่เจอบ่อย

กราฟไม่มีทิศ (undirected graph) คือแบบในภาพข้างบน ถนนจาก 1 ไป 2 ใช้ขับจาก 2 กลับมา 1 ได้ด้วย ความเป็นเพื่อนก็เป็นแบบนี้

กราฟมีทิศ (directed graph) เส้นเชื่อมมีลูกศร ไปได้ทางเดียว เช่น ถนนเดินรถทางเดียว การติดตามในโซเชียลที่ A ติดตาม B โดย B ไม่ต้องติดตาม A ภาพนี้ไปจาก 1 ถึง 4 ได้ แต่จาก 4 ไปไหนไม่ได้เลย

กราฟมีน้ำหนัก (weighted graph) เส้นเชื่อมมีตัวเลขกำกับ เช่น ความยาวถนนเป็นกิโลเมตร หรือค่าผ่านทาง ในภาพนี้ทางที่ผ่านถนนน้อยเส้นที่สุดจาก 1 ไป 4 มีสองทาง ยาวเท่ากันคือสองเส้น แต่ทาง 1 2 4 ยาว 9 กิโลเมตร สั้นกว่าทาง 1 3 4 ที่ยาว 12 กิโลเมตร

บทนี้ทำงานกับกราฟที่ ไม่มีน้ำหนัก ทุกเส้นนับเป็นหนึ่งก้าวเท่ากัน ยกเว้นหัวข้อเสริม 0-1 BFS ในหน้า 27.5 ที่น้ำหนักเป็นได้แค่ 0 กับ 1 การหาทางที่สั้นที่สุดเมื่อน้ำหนักเป็นตัวเลขอะไรก็ได้ ต้องใช้วิธีของบทที่ 28

ข้อมูลเข้าของโจทย์กราฟ

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

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

รายการเส้นเชื่อมแบบนี้เรียกว่า edge list เก็บง่าย แต่ถามว่า "บ้าน 5 มีเพื่อนบ้านเป็นใครบ้าง" แล้วต้องไล่ดูทุกเส้น งานแทบทุกอย่างในบทนี้ถามคำถามนี้ซ้ำเป็นแสนครั้ง จึงต้องแปลงให้อยู่ในรูปที่ตอบได้เร็วก่อน

adjacency matrix

วิธีแรกคือตาราง N × N ช่องแถว u คอลัมน์ v เป็น true ถ้า u กับ v เชื่อมกัน เรียกว่า adjacency matrix (เมทริกซ์ประชิด) ใช้อาเรย์สองมิติจากบทที่ 7 ได้ตรงๆ

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

bool road[101][101]; // (1)!

int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        road[u][v] = true;
        road[v][u] = true; // (2)!
    }
    for (int u = 1; u <= n; u++) {
        for (int v = 1; v <= n; v++) {
            cout << road[u][v];
        }
        cout << '\n';
    }
    return 0;
}

1. ประกาศนอก main ทุกช่องเริ่มเป็น false ให้เอง และไม่ติดขีดจำกัดราว 2 MB ของตัวแปรใน main ตามหน้า 5.5 จองไว้ 101 แถวเพราะใช้ช่อง 1 ถึง 100 ไม่ใช้ช่อง 0
2. ถนนวิ่งได้สองทาง จึงต้องเขียนทั้งช่อง [u][v] และ [v][u] ถ้าเป็นกราฟมีทิศ เขียนแค่ช่องแรก

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

010100000
101010000
010001000
100010000
010101000
001010000
000000010
000000101
000000010

แถวที่ 2 คือ 101010000 มี 1 ที่คอลัมน์ 1 3 5 ตรงกับเพื่อนบ้านของบ้าน 2 ตารางสมมาตรกันตามเส้นทแยง เพราะถนนวิ่งได้สองทาง ข้อดีคือถามว่า "u กับ v เชื่อมกันไหม" ได้ใน O(1) แค่ดู road[u][v] ข้อเสียคือต้องจองที่ N² ช่องเสมอ แม้ถนนจะมีไม่กี่เส้น และการหาเพื่อนบ้านทั้งหมดของ u ต้องไล่ทั้งแถว N ช่อง

adjacency list

วิธีที่สองเก็บเฉพาะเพื่อนบ้านที่มีจริง แต่ละจุดยอดมี vector ของตัวเองหนึ่งตัว ใส่หมายเลขเพื่อนบ้านลงไป เรียกว่า adjacency list (รายการประชิด) เป็นรูปแบบเดียวกับรายชื่อสมาชิกชุมนุมในหน้า 16.2 ที่แต่ละแถวยาวไม่เท่ากัน

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

const int MAXN = 100001;
vector<int> adj[MAXN]; // (1)!

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v); // (2)!
        adj[v].push_back(u);
    }
    for (int u = 1; u <= n; u++) {
        cout << u << " (degree " << adj[u].size() << "):"; // (3)!
        for (int v : adj[u]) {
            cout << ' ' << v;
        }
        cout << '\n';
    }
    return 0;
}

1. อาเรย์ของ vector แต่ละช่องเป็น vector ว่างหนึ่งตัว adj[u] คือรายชื่อเพื่อนบ้านของ u ตัว vector ว่างกินที่ช่องละ 24 byte ข้อมูลจริงอยู่นอก stack จึงประกาศแสนช่องได้ไม่มีปัญหา
2. ถนนหนึ่งเส้นเพิ่มเพื่อนบ้านให้ทั้งสองฝั่ง เส้นเชื่อม M เส้นจึงเก็บรวม 2M ตัว ถ้าเป็นกราฟมีทิศ เขียนแค่บรรทัดแรก
3. ดีกรีคือขนาดของรายการ ได้ทันทีด้วย size()

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

1 (degree 2): 2 4
2 (degree 3): 1 3 5
3 (degree 2): 2 6
4 (degree 2): 1 5
5 (degree 3): 2 4 6
6 (degree 2): 5 3
7 (degree 1): 8
8 (degree 2): 7 9
9 (degree 1): 8

ลำดับในรายการคือลำดับที่อ่านเข้ามา บ้าน 6 จึงเป็น 5 3 ไม่ใช่ 3 5 เพราะถนน 5-6 มาก่อนถนน 3-6 ปกติลำดับไม่มีผลกับคำตอบ ถ้าโจทย์บังคับให้ไปเพื่อนบ้านหมายเลขน้อยก่อน ให้ sort ทุกรายการหลังอ่านครบ ถ้าไม่อยากจองเผื่อด้วย MAXN ก็ใช้ vector<vector<int>> adj(n + 1); หลังอ่าน n ได้ ใช้งานเหมือนกันทุกอย่าง

กราฟมีทิศ

เก็บเฉพาะทิศที่ไปได้ ตัวอย่างนี้ใช้กราฟถนนทางเดียวในภาพก่อนหน้า และนับด้วยว่ามีลูกศรกี่อันชี้เข้าแต่ละจุด เรียกว่า in-degree

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

const int MAXN = 100001;
vector<int> adj[MAXN];
int in_degree[MAXN];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int from, to;
        cin >> from >> to;
        adj[from].push_back(to);
        in_degree[to]++;
    }
    for (int u = 1; u <= n; u++) {
        cout << u << " in " << in_degree[u] << " out:";
        for (int v : adj[u]) {
            cout << ' ' << v;
        }
        cout << '\n';
    }
    return 0;
}

5 5
1 2
2 3
3 1
3 4
5 4

1 in 1 out: 2
2 in 1 out: 3
3 in 1 out: 1 4
4 in 2 out:
5 in 0 out: 4

adj[4] ว่าง เพราะไม่มีถนนออกจาก 4 แต่มีลูกศรชี้เข้า 4 สองอัน ถ้าโจทย์ถามว่า "ใครขับมาถึงจุด 4 ได้บ้าง" รายการนี้ตอบไม่ได้ตรงๆ ต้องสร้างรายการอีกชุดที่กลับทิศทุกเส้น ซึ่งจะได้ลองในแบบฝึกหัด

กราฟมีน้ำหนัก

แต่ละช่องในรายการเก็บเป็น pair ของเพื่อนบ้านกับน้ำหนัก แล้วแตกออกด้วย structured binding ตามหน้า 16.4

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

const int MAXN = 100001;
vector<pair<int, int>> adj[MAXN];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v, km;
        cin >> u >> v >> km;
        adj[u].push_back({v, km});
        adj[v].push_back({u, km});
    }
    for (int u = 1; u <= n; u++) {
        cout << u << ':';
        for (auto [v, km] : adj[u]) {
            cout << ' ' << v << '(' << km << " km)";
        }
        cout << '\n';
    }
    return 0;
}

4 4
1 2 7
1 3 3
2 4 2
3 4 9

1: 2(7 km) 3(3 km)
2: 1(7 km) 4(2 km)
3: 1(3 km) 4(9 km)
4: 2(2 km) 3(9 km)

รูปแบบนี้จะใช้อีกครั้งกับ 0-1 BFS ในหน้า 27.5 และใช้ทั้งบทที่ 28

เลือกแบบไหน

งานในบทนี้ทั้ง DFS และ BFS ไล่เพื่อนบ้านของทุกจุดครบหนึ่งรอบ จึงเป็นแถวสุดท้ายของตาราง ใช้ adjacency list ได้ O(V + E) ส่วน adjacency matrix ได้ O(V²) เสมอไม่ว่าจะมีถนนกี่เส้น

เรื่องหน่วยความจำตัดสินได้เร็วกว่า โจทย์ค่าย 2 และ TOI ให้ N ถึงแสนหรือสองแสนเป็นปกติ adjacency matrix แบบ bool ของ N = 100000 คือ 10¹⁰ byte หรือ 10 GB ขณะที่โจทย์ส่วนใหญ่จำกัดหน่วยความจำไว้ราว 256 MB ส่วนโปรแกรมที่ใช้ adjacency list ในหัวข้อถัดไป กับ N = 100000 และ M = 200000 ใช้หน่วยความจำสูงสุดทั้งโปรแกรมแค่ 13.8 MB หลักเลือกจึงง่าย

• N ไม่เกินสองสามพัน และอยากถามว่า u กับ v เชื่อมกันไหมบ่อยๆ ใช้ adjacency matrix ได้
• นอกนั้นใช้ adjacency list เสมอ

เร็วต่างกันแค่ไหน

สถานีรถเมล์ N สถานีเชื่อมกันด้วยถนน M เส้น สถานีที่ i มีคนรอ w_i คน หาสถานีที่สถานีข้างเคียงทั้งหมดรวมกันมีคนรอมากที่สุด ถ้าเท่ากันเลือกหมายเลขน้อย งานนี้คือไล่เพื่อนบ้านของทุกสถานีครบหนึ่งรอบพอดี

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

const int MAXN = 200001;
vector<int> adj[MAXN];
int waiting[MAXN];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for (int u = 1; u <= n; u++) {
        cin >> waiting[u];
    }
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    int best = 1;
    long long best_sum = -1;
    for (int u = 1; u <= n; u++) {
        long long sum = 0;
        for (int v : adj[u]) {
            sum += waiting[v];
        }
        if (sum > best_sum) {
            best_sum = sum;
            best = u;
        }
    }
    cout << best << ' ' << best_sum << '\n';
    return 0;
}

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

2 20

สถานี 2 มีเพื่อนบ้านคือ 1 3 5 คนรอรวม 5 + 8 + 7 = 20 ฉบับ adjacency matrix เปลี่ยนสามจุด ประกาศ bool road[MAXN][MAXN]; แทน adj โดยตั้ง MAXN เป็น N + 1 ของข้อมูลแต่ละชุด (ถ้าใช้ 200001 แบบฉบับ list จะต้องจอง 40 GB) ตอนอ่านถนนเขียน road[u][v] กับ road[v][u] เป็น true แทน push_back และลูปข้างในต้องไล่ทุกสถานี

for (int v = 1; v <= n; v++) {
    if (road[u][v]) {
        sum += waiting[v];
    }
}

วัดบนเครื่องเดียวกับหน้า 19.1 กราฟสุ่ม รันแต่ละแบบ 5 รอบโดยไม่นับรอบแรกหลังคอมไพล์ ตารางเป็นค่ากลาง เวลารวมการอ่านข้อมูลด้วย หน่วยความจำสูงสุดวัดจาก PeakWorkingSet ของทั้งโปรแกรมแบบ -O2 ฉบับ matrix ตั้ง MAXN เป็น 10001 และ 20001 ตามข้อมูล ฉบับ list ประกาศ MAXN ไว้สองแสนช่องทุกครั้ง จึงใช้อย่างน้อยราว 10 MB แม้กราฟจะเล็ก

N เพิ่มสองเท่า matrix ช้าลงราวสามถึงสี่เท่า และกินหน่วยความจำราวสี่เท่า ตรงกับ N² ที่โตสี่เท่า ส่วน list โตตามขนาดข้อมูลที่อ่าน ที่ N = 20000 matrix ยังทันเวลา เพราะการไล่ bool ที่เรียงติดกันเป็นงานที่ CPU ทำได้เร็วมาก แต่ใช้หน่วยความจำเกือบ 400 MB เกินขีดจำกัดของโจทย์ส่วนใหญ่ไปแล้ว ปัญหาจริงของ matrix จึงเป็นหน่วยความจำก่อนเวลา

ลองทำให้พัง

แบบที่ 1 ลืมใส่เส้นกลับ

ในโปรแกรม adj-list ลบบรรทัด adj[v].push_back(u); ออก เพราะคิดว่าใส่ถนนไปแล้วหนึ่งครั้ง

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

const int MAXN = 100001;
vector<int> adj[MAXN];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
    }
    for (int u = 1; u <= n; u++) {
        cout << u << " (degree " << adj[u].size() << "):";
        for (int v : adj[u]) {
            cout << ' ' << v;
        }
        cout << '\n';
    }
    return 0;
}

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

1 (degree 2): 2 4
2 (degree 2): 3 5
3 (degree 1): 6
4 (degree 1): 5
5 (degree 1): 6
6 (degree 0):
7 (degree 1): 8
8 (degree 1): 9
9 (degree 0):

คอมไพล์ผ่าน ไม่มีคำเตือน แต่กราฟกลายเป็นกราฟมีทิศโดยไม่ตั้งใจ บ้าน 6 มีดีกรี 0 ทั้งที่มีถนนสองเส้น บ้าน 2 หายเพื่อนบ้านไปหนึ่งหลัง ถ้าเอากราฟนี้ไปหาว่าบ้าน 6 ไปบ้าน 1 ได้ไหม จะได้คำตอบว่าไม่ได้ ทุกครั้งที่สร้างกราฟ ให้พิมพ์รายการของกราฟเล็กๆ ออกมาเทียบกับภาพก่อน แล้วค่อยเขียนส่วนที่เหลือ

แบบที่ 2 ประกาศ matrix ใน main

โจทย์ให้ N ไม่เกิน 2000 จึงประกาศ matrix ขนาดพอดีไว้ใน main พร้อมตั้งค่าเริ่มต้นเป็น 0 ด้วย = {}

int main()
{
    bool road[2001][2001] = {};
    int n, m;
    cin >> n >> m;

คอมไพล์ด้วย -Wall ไม่มีคำเตือน แต่พอรันกับกราฟของหมู่บ้าน โปรแกรมปิดตัวทันทีโดยไม่พิมพ์อะไร

Process returned -1073741571 (0xC00000FD)

bool 2001 × 2001 ช่องคือราว 4 MB เกินที่ราว 2 MB ที่ตัวแปรใน main ใช้ได้ จึง stack overflow แบบเดียวกับหน้า 5.5 และ 7.1 ตั้งแต่ยังไม่ทันอ่านข้อมูล ย้ายไปประกาศนอก main ก็หาย

สรุป

• กราฟคือจุดยอดกับเส้นเชื่อม มีแบบไม่มีทิศ มีทิศ และมีน้ำหนัก ต้นไม้คือกราฟที่ถึงกันหมดและไม่มีวงจร
• adjacency matrix ตอบว่า u กับ v เชื่อมกันไหมใน O(1) แต่ใช้ที่ V² ใช้ได้เมื่อ N ไม่เกินสองสามพัน
• adjacency list vector<int> adj[MAXN] ใช้ที่ V + 2E และไล่เพื่อนบ้านของทุกจุดได้ใน O(V + E) เป็นแบบที่ใช้เกือบทุกข้อ
• กราฟไม่มีทิศต้องใส่ทั้ง adj[u].push_back(v) และ adj[v].push_back(u) กราฟมีน้ำหนักเก็บเป็น pair
• ประกาศกราฟนอก main เสมอ