27.3 BFS และระยะทางที่สั้นที่สุด

DFS ในหน้า 27.2 บอกได้ว่าไปถึงไหนบ้าง แต่ไม่บอกว่าไปด้วยถนนน้อยที่สุดกี่เส้น DFS จากบ้าน 1 ไปถึงบ้าน 4 ผ่าน 1 2 3 6 5 4 ห้าเส้น ทั้งที่มีถนน 1-4 ตรงๆ เส้นเดียว โจทย์ "น้อยที่สุดกี่ก้าว" บนกราฟที่ทุกเส้นยาวเท่ากันต้องใช้ BFS (breadth-first search) หรือการค้นแบบกว้างก่อน ซึ่งเดินออกจากจุดเริ่มทีละชั้นด้วย queue จากบทที่ 17 แบบเดียวกับ level order ในหน้า 26.2 หน้านี้ต่อยอดเป็นการพิมพ์เส้นทาง BFS จากหลายจุดพร้อมกัน และการแบ่งกราฟเป็นสองฝั่ง

ไล่ทีละชั้น

ให้ dist[v] คือจำนวนเส้นที่น้อยที่สุดจากจุดเริ่มถึง v จุดเริ่มมีระยะ 0 เพื่อนบ้านของมันมีระยะ 1 เพื่อนบ้านของพวกนั้นที่ยังไม่มีระยะ มีระยะ 2 ไปเรื่อยๆ BFS ทำแบบนี้ด้วย queue

1. ตั้ง dist ทุกช่องเป็น -1 แปลว่ายังไปไม่ถึง ตั้งจุดเริ่มเป็น 0 แล้วใส่ queue
2. หยิบจุดหน้า queue ออกมาเป็น v ทุกเพื่อนบ้านที่ dist ยังเป็น -1 ได้ระยะ dist[v] + 1 แล้วต่อท้าย queue
3. ทำข้อ 2 จน queue ว่าง

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

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, start;
    cin >> n >> m >> start;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    fill(dist, dist + n + 1, -1); // (1)!
    queue<int> waiting;
    dist[start] = 0;
    waiting.push(start);
    while (!waiting.empty()) {
        int v = waiting.front();
        waiting.pop();
        cout << "take " << v << " dist " << dist[v] << '\n';
        for (int next : adj[v]) {
            if (dist[next] == -1) {
                dist[next] = dist[v] + 1; // (2)!
                waiting.push(next);
            }
        }
    }
    for (int v = 1; v <= n; v++) {
        cout << dist[v] << (v == n ? '\n' : ' ');
    }
    return 0;
}

1. fill(first, last, value) จาก algorithm ใส่ค่า value ลงทุกช่องตั้งแต่ first ถึงช่องก่อน last ตรงนี้คือช่อง 0 ถึง n ของอาเรย์ธรรมดา ใช้กับ vector ได้ด้วย เช่น fill(v.begin(), v.end(), -1) ค่า -1 ใช้แทน visited ได้ในตัว ระยะจริงไม่มีทางติดลบ และจุดที่ไปไม่ถึงจะเหลือ -1 จนจบ พิมพ์ออกไปตรงๆ ได้
2. ให้ระยะตั้งแต่ตอนใส่ queue ไม่ใช่ตอนหยิบออก แต่ละจุดจึงเข้า queue ครั้งเดียว ถ้าเลื่อนไปจดตอนหยิบออกแทน จุดเดียวกันอาจถูกใส่ซ้ำจากหลายเพื่อนบ้าน หน้า 27.4 จะวัดให้เห็นว่าเสียหายแค่ไหน

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

take 1 dist 0
take 2 dist 1
take 4 dist 1
take 3 dist 2
take 5 dist 2
take 6 dist 3
0 1 2 1 2 3 -1 -1 -1

ข้อมูลเข้าเหมือนกราฟของหมู่บ้าน แต่บรรทัดแรกมีจุดเริ่มต่อท้ายด้วย จุดออกจาก queue เรียงตามระยะ 0 1 1 2 2 3 ไม่มีทางสลับกัน ได้ระยะของบ้าน 4 เป็น 1 ถูกต้อง และบ้าน 7 8 9 เป็น -1 เพราะไปไม่ถึง

ทำไมได้ระยะที่สั้นที่สุด

ในทุกจังหวะ queue มีแต่จุดระยะ d ต่อด้วยจุดระยะ d + 1 เท่านั้น เพราะจุดที่ถูกต่อท้ายมีระยะมากกว่าจุดที่กำลังหยิบอยู่หนึ่งเสมอ จุดจึงออกจาก queue เรียงตามระยะ ไม่มีทางย้อน ทางที่สั้นที่สุดไปจุด x ต้องผ่านเพื่อนบ้านตัวใดตัวหนึ่งของ x เป็นจุดรองสุดท้าย ระยะที่สั้นที่สุดของ x จึงเท่ากับระยะน้อยที่สุดในบรรดาเพื่อนบ้านบวกหนึ่ง เพื่อนบ้านที่ระยะน้อยที่สุดคือตัวที่ออกจาก queue ก่อนเพื่อนบ้านตัวอื่น และเป็นตัวที่ให้ระยะ x ก่อนใคร ครั้งแรกที่ x ได้ระยะจึงเป็นระยะที่สั้นที่สุดพอดี ไล่เหตุผลนี้ทีละชั้นตั้งแต่จุดเริ่ม ก็ได้ว่าถูกทุกจุด

เหตุผลนี้ใช้ได้เพราะทุกเส้นยาวเท่ากัน ถ้าแต่ละเส้นยาวไม่เท่ากัน ทางที่ผ่านเส้นน้อยกว่าอาจยาวกว่าทางที่ผ่านหลายเส้น ในภาพกราฟมีน้ำหนักของหน้า 27.1 ทาง 1 2 4 กับ 1 3 4 ผ่านสองเส้นเท่ากัน BFS มองว่าไกลเท่ากัน ทั้งที่ยาว 9 กับ 12 กิโลเมตร กรณีนั้นใช้ BFS ไม่ได้ ต้องรอบทที่ 28

เวลาที่ใช้

แต่ละจุดเข้าและออกจาก queue ไม่เกินครั้งเดียว และตอนออกไล่รายการเพื่อนบ้านของตัวเองครั้งเดียว รวมเป็น O(V + E) เท่ากับ DFS และไม่มีปัญหาเรื่องความลึก เพราะไม่ได้เรียกตัวเองเลย queue ยาวได้ไม่เกิน V ช่อง

เก็บพ่อเพื่อพิมพ์เส้นทาง

ถ้าโจทย์ให้พิมพ์เส้นทางด้วย ตอนที่จุด next ได้ระยะจาก v ให้จดไว้ว่า parent[next] = v คือมาถึง next จาก v พอ BFS จบ เดินย้อนจากปลายทางตาม parent ไปเรื่อยๆ จะถึงจุดเริ่ม ได้เส้นทางแบบกลับหัว แล้วกลับลำดับอีกที ข้อมูลเข้าบรรทัดแรกมีจุดเริ่มกับปลายทางต่อท้าย

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

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, start, goal;
    cin >> n >> m >> start >> goal;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    fill(dist, dist + n + 1, -1);
    queue<int> waiting;
    dist[start] = 0;
    parent[start] = 0;
    waiting.push(start);
    while (!waiting.empty()) {
        int v = waiting.front();
        waiting.pop();
        for (int next : adj[v]) {
            if (dist[next] == -1) {
                dist[next] = dist[v] + 1;
                parent[next] = v; // (1)!
                waiting.push(next);
            }
        }
    }
    if (dist[goal] == -1) {
        cout << "no route\n";
        return 0;
    }
    vector<int> route;
    for (int v = goal; v != 0; v = parent[v]) { // (2)!
        route.push_back(v);
    }
    reverse(route.begin(), route.end()); // (3)!
    cout << "roads " << dist[goal] << '\n';
    for (int i = 0; i < (int)route.size(); i++) {
        cout << route[i] << (i + 1 == (int)route.size() ? '\n' : ' ');
    }
    return 0;
}

1. จดพร้อมกับตอนให้ระยะ จุดหนึ่งได้ระยะครั้งเดียว พ่อจึงถูกจดครั้งเดียวด้วย
2. จุดเริ่มมีพ่อเป็น 0 ซึ่งไม่ใช่หมายเลขบ้าน ลูปจึงหยุดหลังใส่จุดเริ่มลงไป
3. ที่เก็บมาเรียงจากปลายทางไปจุดเริ่ม reverse จาก algorithm ในหน้า 16.5 กลับให้เป็นจากจุดเริ่มไปปลายทาง

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

roads 3
4 1 2 3

จากบ้าน 4 ไปบ้าน 3 มีเส้นทางที่สั้นที่สุดสามเส้น คือ 4 1 2 3 4 5 2 3 และ 4 5 6 3 โปรแกรมได้เส้นแรก เพราะ 1 อยู่ก่อน 5 ในรายการของบ้าน 4 จึงเข้า queue ก่อน และเป็นคนแรกที่ไปถึง 2 ถ้าสลับลำดับถนนในข้อมูลเข้า อาจได้เส้นอื่นที่ยาวเท่ากัน ถ้าโจทย์ระบุว่าต้องพิมพ์เส้นไหน เช่น เส้นที่น้อยที่สุดตามพจนานุกรม ต้องคิดเพิ่ม ซึ่งจะได้ลองในแบบฝึกหัด ถ้าไปไม่ถึง dist[goal] เป็น -1 ต้องเช็กก่อนเดินย้อน ป้อนจากบ้าน 1 ไปบ้าน 9

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

no route

BFS หลายจุดเริ่ม

อำเภอมีโรงพยาบาลอยู่ในหมู่บ้าน K แห่ง อยากรู้ว่าแต่ละหมู่บ้านอยู่ห่างจากโรงพยาบาลที่ใกล้ที่สุดกี่ถนน วิธีตรงไปตรงมาคือ BFS จากโรงพยาบาลทีละแห่ง แล้วเก็บค่าน้อยสุดของแต่ละหมู่บ้าน ใช้เวลา O(K(V + E))

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

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

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, k;
    cin >> n >> m >> k;
    fill(dist, dist + n + 1, -1);
    queue<int> waiting;
    for (int i = 0; i < k; i++) {
        int hospital;
        cin >> hospital;
        dist[hospital] = 0;
        waiting.push(hospital); // (1)!
    }
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    while (!waiting.empty()) {
        int v = waiting.front();
        waiting.pop();
        for (int next : adj[v]) {
            if (dist[next] == -1) {
                dist[next] = dist[v] + 1;
                waiting.push(next);
            }
        }
    }
    for (int v = 1; v <= n; v++) {
        cout << dist[v] << (v == n ? '\n' : ' ');
    }
    return 0;
}

1. ทุกจุดเริ่มเข้า queue ก่อนเริ่มวน ส่วนที่เหลือของโปรแกรมเหมือน BFS จากจุดเดียวทุกบรรทัด

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

1 2 3 0 1 2 2 1 0

โรงพยาบาลอยู่ที่บ้าน 4 กับบ้าน 9 บ้าน 3 ได้ 3 เพราะใกล้บ้าน 4 ที่สุด และไกลจากบ้าน 9 เกินจะไปถึง บ้าน 7 ได้ 2 จากบ้าน 9 งานนี้ยังเป็น O(V + E) ไม่ว่าจะมีโรงพยาบาลกี่แห่ง

วัดบนเครื่องเดียวกับหน้า 19.1 กราฟสุ่ม N = 100000 M = 150000 เปลี่ยนจำนวนโรงพยาบาล K รันแต่ละแบบ 5 รอบ ยกเว้นแถวที่ K = 10000 ของวิธีทีละแห่งรัน 3 รอบ ตารางเป็นค่ากลาง

วิธีทีละแห่งโตตามจำนวนโรงพยาบาล K เพิ่มสิบเท่าก็ช้าลงแปดถึงสิบห้าเท่า ส่วน BFS หลายจุดเริ่มแทบไม่เปลี่ยน เพราะทุกหมู่บ้านยังเข้า queue ครั้งเดียวเหมือนเดิม วิธีนี้ใช้ได้ทุกครั้งที่โจทย์ถามว่า "ใกล้อะไรสักอย่างที่ใกล้ที่สุดแค่ไหน" เช่น ไฟที่ลามจากหลายจุดพร้อมกัน หรือช่องในตารางที่ใกล้ทางออกบานใดก็ได้

กราฟสองฝั่ง

ครูจะแบ่งนักเรียนเป็นสองทีม โดยคู่ที่ทะเลาะกันต้องอยู่คนละทีม ถ้าแต่ละคนเป็นจุดและคู่ที่ทะเลาะกันเป็นเส้นเชื่อม คำถามคือระบายสีจุดด้วยสองสีให้ทุกเส้นเชื่อมจุดต่างสีกันได้ไหม กราฟที่ทำได้เรียกว่า กราฟสองฝั่ง (bipartite graph)

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

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

const int MAXN = 100001;
vector<int> adj[MAXN];
int color[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);
        adj[v].push_back(u);
    }
    fill(color, color + n + 1, -1);
    for (int start = 1; start <= n; start++) {
        if (color[start] != -1) {
            continue;
        }
        queue<int> waiting;
        color[start] = 0;
        waiting.push(start);
        while (!waiting.empty()) {
            int v = waiting.front();
            waiting.pop();
            for (int next : adj[v]) {
                if (color[next] == -1) {
                    color[next] = 1 - color[v]; // (1)!
                    waiting.push(next);
                } else if (color[next] == color[v]) { // (2)!
                    cout << "conflict " << v << ' ' << next << '\n';
                    return 0;
                }
            }
        }
    }
    for (int v = 1; v <= n; v++) {
        cout << color[v] << (v == n ? '\n' : ' ');
    }
    return 0;
}

1. สีตรงข้ามกับ v คือ 1 - color[v] ได้ 1 จาก 0 และได้ 0 จาก 1
2. เพื่อนบ้านมีสีแล้ว และเป็นสีเดียวกับ v พิมพ์คู่นั้นแล้วจบเลย

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

0 1 0 1 0 1 0 1 0

หมู่บ้านนี้แบ่งสองฝั่งได้ สีของแต่ละจุดคือระยะจากจุดเริ่มของกลุ่มเป็นเลขคู่หรือคี่ เทียบกับภาพในหัวข้อแรก บ้านระยะ 0 และ 2 เป็นสี 0 บ้านระยะ 1 และ 3 เป็นสี 1 ลองเพิ่มถนน 1-5 อีกเส้น บรรทัดแรกจึงเป็น 9 10

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

conflict 2 5

ถนน 1-5 ทำให้เกิดวงจร 1 2 5 1 ซึ่งยาว 3 เส้น เดินวงจรความยาวคี่ สีต้องสลับเป็นจำนวนคี่ครั้งแล้วกลับมาที่จุดเดิม ซึ่งเป็นไปไม่ได้ กราฟจึงเป็นสองฝั่งได้ก็ต่อเมื่อไม่มีวงจรความยาวคี่เลย วงจร 1 2 5 4 1 ในกราฟเดิมยาว 4 เส้นจึงไม่เป็นปัญหา ต้นไม้ไม่มีวงจร จึงเป็นกราฟสองฝั่งเสมอ

ลองทำให้พัง

แบบที่ 1 ใช้ stack แทน queue

ในโปรแกรม bfs-dist เปลี่ยน queue<int> เป็น stack<int> และ front() เป็น top() เพราะคิดว่ายังไงก็ไปครบทุกจุดเหมือนกัน

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

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, start;
    cin >> n >> m >> start;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    fill(dist, dist + n + 1, -1);
    stack<int> waiting;
    dist[start] = 0;
    waiting.push(start);
    while (!waiting.empty()) {
        int v = waiting.top();
        waiting.pop();
        cout << "take " << v << " dist " << dist[v] << '\n';
        for (int next : adj[v]) {
            if (dist[next] == -1) {
                dist[next] = dist[v] + 1;
                waiting.push(next);
            }
        }
    }
    for (int v = 1; v <= n; v++) {
        cout << dist[v] << (v == n ? '\n' : ' ');
    }
    return 0;
}

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

take 1 dist 0
take 4 dist 1
take 5 dist 2
take 6 dist 3
take 3 dist 4
take 2 dist 1
0 1 4 1 2 3 -1 -1 -1

ไปครบทุกจุดจริง แต่บ้าน 3 ได้ระยะ 4 ทั้งที่ 1 2 3 ยาวแค่ 2 stack หยิบบ้าน 4 ที่ใส่ทีหลังออกก่อน แล้วลงลึกไป 5 ไป 6 จนไปเจอบ้าน 3 ผ่านทางยาวก่อนที่บ้าน 2 จะได้ออกจาก stack พอบ้าน 3 ได้ระยะแล้วก็ไม่ถูกแก้อีก เหตุผลเรื่องชั้นในหัวข้อแรกใช้ได้กับ queue เท่านั้น การไปครบทุกจุดใช้ stack หรือ queue ก็ได้ แต่ระยะที่สั้นที่สุดต้องใช้ queue

แบบที่ 2 ใช้ 0 แทนยังไม่เคยไป

ไม่อยากเรียก fill จึงปล่อยให้ dist ที่ประกาศนอก main เป็น 0 ทั้งหมด แล้วเช็ก dist[next] == 0 แทน

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

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, start;
    cin >> n >> m >> start;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    queue<int> waiting;
    dist[start] = 0;
    waiting.push(start);
    while (!waiting.empty()) {
        int v = waiting.front();
        waiting.pop();
        cout << "take " << v << " dist " << dist[v] << '\n';
        for (int next : adj[v]) {
            if (dist[next] == 0) {
                dist[next] = dist[v] + 1;
                waiting.push(next);
            }
        }
    }
    for (int v = 1; v <= n; v++) {
        cout << dist[v] << (v == n ? '\n' : ' ');
    }
    return 0;
}

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

take 1 dist 0
take 2 dist 1
take 4 dist 1
take 1 dist 2
take 3 dist 2
take 5 dist 2
take 6 dist 3
2 1 2 1 2 3 0 0 0

ผิดสองจุด บ้าน 1 ถูกหยิบออกมาสองครั้ง และระยะกลายเป็น 2 เพราะระยะที่ถูกต้องของจุดเริ่มคือ 0 ซึ่งดูเหมือนยังไม่เคยไป บ้าน 2 จึงให้ระยะบ้าน 1 ใหม่ ส่วนบ้าน 7 8 9 ที่ไปไม่ถึงได้ 0 ซึ่งอ่านแล้วเหมือนเป็นจุดเริ่ม ค่าที่ใช้แทน "ยังไม่เคยไป" ต้องเป็นค่าที่ระยะจริงเป็นไม่ได้ เช่น -1 หรือแยกเป็นอาเรย์ visited ต่างหาก

สรุป

• BFS ใช้ queue ให้ระยะตอนใส่ queue ได้ระยะที่สั้นที่สุดจากจุดเริ่มถึงทุกจุดในกราฟที่ทุกเส้นยาวเท่ากัน ใช้เวลา O(V + E) และไม่มีปัญหาเรื่องความลึก
• จด parent ตอนให้ระยะ แล้วเดินย้อนจากปลายทางและกลับลำดับ ได้เส้นทางที่สั้นที่สุดหนึ่งเส้น
• ใส่จุดเริ่มทั้งหมดลง queue ด้วยระยะ 0 ได้ระยะถึงจุดเริ่มที่ใกล้ที่สุดใน BFS ครั้งเดียว
• ระบายสองสีด้วย BFS ถ้าเจอเส้นที่ปลายสีเดียวกันแปลว่าไม่ใช่กราฟสองฝั่ง ซึ่งเกิดเมื่อมีวงจรความยาวคี่
• ใช้ stack แทน queue ได้ระยะผิด และอย่าใช้ 0 แทนยังไม่เคยไป