DFS and BFS

Danh sách kề và DFS

Vài chữ dùng suốt chương. Cạnh vô hướng đi được cả hai chiều, cạnh có hướng chỉ đi theo chiều mũi tên. Bậc của một đỉnh là số cạnh nối với nó. Đường đi là dãy đỉnh mà hai đỉnh liền nhau có cạnh nối; chu trình là đường đi quay về đỉnh đầu. Hai đỉnh liên thông khi có đường đi giữa chúng.

Đồ thị $n$ đỉnh, $m$ cạnh lưu bằng danh sách kề: g[u] là các đỉnh nối với $u$, mỗi cạnh vô hướng thêm vào cả hai đầu. Bộ nhớ $O(n + m)$, duyệt hàng xóm của $u$ tốn đúng bậc của $u$. Ma trận kề $n \times n$ chỉ hợp khi $n$ cỡ vài nghìn.

DFS từ $u$: đánh dấu $u$ đã thăm, rồi gọi DFS cho từng hàng xóm chưa thăm. Mỗi đỉnh được gọi một lần, mỗi cạnh được xét hai lần, nên tổng $O(n + m)$.

Gọi DFS từ mọi đỉnh chưa thăm, mỗi lần gọi từ ngoài là một thành phần liên thông mới. Đệ quy sâu tới $n$ tầng; với $n$ cỡ $10^6$ trên lưới, nên đổi sang BFS hoặc tự giữ ngăn xếp.

void dfs(ll u) {
    vis[u] = 1;
    for (ll v : g[u])
        if (!vis[v]) dfs(v);
}

Ví dụSố Cụm Trong Mạng

Đề. Đồ thị vô hướng $n \le 100$ đỉnh, đếm số thành phần liên thông.

Lời giải. Duyệt $u = 1..n$, gặp đỉnh chưa thăm thì tăng đếm và DFS từ đó. DFS đánh dấu đúng thành phần chứa $u$, nên đỉnh chưa thăm tiếp theo chắc chắn thuộc một thành phần mới: nếu nó thuộc thành phần đã gặp thì DFS trước đó đã đánh dấu nó. Mỗi thành phần được đếm đúng một lần.

Bước 1: danh sách kề. Cạnh vô hướng thêm vào cả hai đầu.

for (ll i = 1; i <= m; i++) {
    ll u, v;
    cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
}

Bước 2: DFS. Đánh dấu $u$ rồi gọi tiếp mọi hàng xóm chưa thăm. Khi hàm trả về, mọi đỉnh tới được từ $u$ đã được đánh dấu.

void dfs(ll u) {
    vis[u] = 1;
    for (ll v : g[u])
        if (!vis[v]) dfs(v);
}

Bước 3: đếm số lần phải bắt đầu.

for (ll u = 1; u <= n; u++)
    if (!vis[u]) {
        ans++;
        dfs(u);
    }

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

const ll N = 105;
ll n, m, vis[N];
vector<ll> g[N];

void dfs(ll u) {
    vis[u] = 1;
    for (ll v : g[u])
        if (!vis[v]) dfs(v);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for (ll i = 1; i <= m; i++) {
        ll u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    ll ans = 0;
    for (ll u = 1; u <= n; u++)
        if (!vis[u]) {
            ans++;
            dfs(u);
        }
    cout << ans << '\n';
}

ChạyInput7 4
1 2
2 3
4 5
6 7

Output3

Độ phức tạp: mỗi đỉnh và mỗi cạnh được xét một lần: $O(n + m)$.

BFS

BFS dùng một hàng đợi. Đỉnh xuất phát có khoảng cách 0; lấy đỉnh $u$ ở đầu hàng, mỗi hàng xóm $v$ chưa thăm nhận d[v] = d[u] + 1 và vào cuối hàng. Hàng đợi luôn chứa các đỉnh khoảng cách $k$ rồi tới $k + 1$, không bao giờ lẫn lớp xa hơn, nên mọi đỉnh lớp $k$ được lấy ra trước mọi đỉnh lớp $k + 1$ và d[v] là số cạnh ít nhất từ nguồn tới $v$. Đánh dấu thăm lúc đẩy vào hàng, không phải lúc lấy ra, để mỗi đỉnh vào hàng một lần.

Muốn in đường đi, lưu par[v] = u khi $v$ được thăm từ $u$; từ đích lần par về nguồn rồi đảo ngược. BFS chỉ đúng khi mọi cạnh cùng độ dài; cạnh có trọng số cần Dijkstra (bài 3.5).

Ví dụTuyến Truyền Tin Ngắn Nhất

Đề. $n \le 10^5$ máy, $m \le 2 \cdot 10^5$ kết nối hai chiều. In một tuyến từ máy 1 tới máy $n$ qua ít máy nhất, hoặc IMPOSSIBLE.

Lời giải. BFS từ máy 1 cho khoảng cách ngắn nhất (theo số cạnh) tới mọi máy. Để in được tuyến, ghi lại par[v]: đỉnh đã đưa $v$ vào hàng đợi. Mỗi đỉnh chỉ có một par, và đi theo par từ $n$ lùi về 1 là một đường ngắn nhất, vì mỗi bước lùi giảm khoảng cách đúng 1.

Bước 1: BFS có ghi cha. d[v] = -1 là chưa thăm. Đánh dấu ngay lúc đẩy vào hàng đợi, nên mỗi đỉnh vào hàng một lần.

for (ll i = 1; i <= n; i++) d[i] = -1;
queue<ll> q;
q.push(1);
d[1] = 0;
while (!q.empty()) {
    ll u = q.front();
    q.pop();
    for (ll v : g[u])
        if (d[v] == -1) {
            d[v] = d[u] + 1;
            par[v] = u;
            q.push(v);
        }
}

Bước 2: truy vết. Máy $n$ không được thăm thì in IMPOSSIBLE. Ngược lại lần par từ $n$ về 1; đường lần ngược đi từ $n$ về 1 nên reverse trước khi in. Số máy trên đường là d[n] + 1, chính là path.size().

vector<ll> path;
for (ll v = n; v != 1; v = par[v]) path.push_back(v);
path.push_back(1);
reverse(path.begin(), path.end());

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

const ll N = 1e5 + 5;
ll n, m, d[N], par[N];
vector<ll> g[N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for (ll i = 1; i <= m; i++) {
        ll u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for (ll i = 1; i <= n; i++) d[i] = -1;
    queue<ll> q;
    q.push(1);
    d[1] = 0;
    while (!q.empty()) {
        ll u = q.front();
        q.pop();
        for (ll v : g[u])
            if (d[v] == -1) {
                d[v] = d[u] + 1;
                par[v] = u;
                q.push(v);
            }
    }
    if (d[n] == -1) {
        cout << "IMPOSSIBLE\n";
        return 0;
    }
    vector<ll> path;
    for (ll v = n; v != 1; v = par[v]) path.push_back(v);
    path.push_back(1);
    reverse(path.begin(), path.end());
    cout << path.size() << '\n';
    for (ll v : path) cout << v << ' ';
    cout << '\n';
}

ChạyInput7 7
1 2
2 3
3 7
1 4
4 5
5 6
6 7

Output4
1 2 3 7

Độ phức tạp: $O(n + m)$.

Khi đồ thị cỡ triệu đỉnh, cách lưu cũng đáng chú ý. vector cho mỗi đỉnh là nhiều khối nhớ nhỏ rải rác; nếu đếm bậc trước rồi xếp mọi cạnh vào một mảng liên tiếp thì BFS đọc bộ nhớ gọn hơn:

Mảng liên tiếp nhanh hơn khoảng 2,5 lần. Với đồ thị cỡ $2 \cdot 10^5$ thì vector vẫn thừa nhanh; chỉ nghĩ tới cách này khi đồ thị cỡ triệu cạnh và hết thời gian.

Lưới

Lưới $n \times m$ là đồ thị mà mỗi ô là một đỉnh, nối với các ô chung cạnh không bị chặn. Không cần dựng danh sách kề: giữ hai mảng dx, dy cho bốn hướng (hoặc tám hướng), và một hàm kiểm ô nằm trong lưới. Lưới $1000 \times 1000$ có $10^6$ đỉnh, nên DFS đệ quy dễ tràn ngăn xếp; dùng BFS với hàng đợi các cặp tọa độ. Truy vết trên lưới chỉ cần nhớ hướng đã đi vào mỗi ô.

Ví dụLối Ra Ngắn Nhất

Đề. Lưới $n, m \le 1000$ có tường, một ô A và một ô B. In YES, độ dài và chuỗi bước LRUD của một đường ngắn nhất từ A tới B, hoặc NO.

Lời giải. BFS trên lưới từ A. Thay vì lưu ô cha, lưu hướng đã đi để vào mỗi ô: from[x][y] = k. Từ B lùi ngược theo hướng đã ghi là về được A, và các hướng gom được chính là chuỗi bước, theo thứ tự ngược.

Bước 1: tìm A, B và khởi tạo. from[x][y] = -1 là chưa thăm; ô xuất phát đặt 4 để khác $-1$ mà không trùng hướng nào. Hướng $k$ ứng với chữ "UDLR"[k], khớp với dx, dy.

for (ll i = 0; i < n; i++) {
    cin >> s[i];
    for (ll j = 0; j < m; j++) {
        from[i][j] = -1;
        if (s[i][j] == 'A') ax = i, ay = j;
        if (s[i][j] == 'B') bx = i, by = j;
    }
}

Bước 2: BFS ghi hướng. dx, dy là bốn hướng lên, xuống, trái, phải. Ba điều kiện continue loại ô ra ngoài lưới, ô tường và ô đã thăm. Hàng đợi chứa thẳng cặp tọa độ, và mỗi ô mới được ghi hướng from[nx][ny] = k lúc thăm.

queue<pair<ll, ll>> q;
q.push({ax, ay});
from[ax][ay] = 4;
while (!q.empty()) {
    ll x = q.front().first, y = q.front().second;
    q.pop();
    for (ll k = 0; k < 4; k++) {
        ll nx = x + dx[k], ny = y + dy[k];
        if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
        if (s[nx][ny] == '#' || from[nx][ny] != -1) continue;
        from[nx][ny] = k;
        q.push({nx, ny});
    }
}

Bước 3: truy vết. Đứng ở B, lấy hướng k đã vào ô này, ghi chữ dir[k], rồi lùi một bước ngược hướng đó. Chữ cái gom được theo thứ tự từ B về A, nên đảo lại trước khi in.

string path;
for (ll x = bx, y = by; x != ax || y != ay;) {
    ll k = from[x][y];
    path += dir[k];
    x -= dx[k];
    y -= dy[k];
}
reverse(path.begin(), path.end());

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

const ll N = 1005;
ll n, m, from[N][N];
ll dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
string s[N], dir = "UDLR";

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    ll ax = 0, ay = 0, bx = 0, by = 0;
    for (ll i = 0; i < n; i++) {
        cin >> s[i];
        for (ll j = 0; j < m; j++) {
            from[i][j] = -1;
            if (s[i][j] == 'A') ax = i, ay = j;
            if (s[i][j] == 'B') bx = i, by = j;
        }
    }
    queue<pair<ll, ll>> q;
    q.push({ax, ay});
    from[ax][ay] = 4;
    while (!q.empty()) {
        ll x = q.front().first, y = q.front().second;
        q.pop();
        for (ll k = 0; k < 4; k++) {
            ll nx = x + dx[k], ny = y + dy[k];
            if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
            if (s[nx][ny] == '#' || from[nx][ny] != -1) continue;
            from[nx][ny] = k;
            q.push({nx, ny});
        }
    }
    if (from[bx][by] == -1) {
        cout << "NO\n";
        return 0;
    }
    string path;
    for (ll x = bx, y = by; x != ax || y != ay;) {
        ll k = from[x][y];
        path += dir[k];
        x -= dx[k];
        y -= dy[k];
    }
    reverse(path.begin(), path.end());
    cout << "YES\n" << path.size() << '\n' << path << '\n';
}

ChạyInput5 6
######
#A...#
###.##
#...B#
######

OutputYES
5
RRDDR

Độ phức tạp: $O(nm)$.

Hai màu và chu trình

Đồ thị hai phía. Một đồ thị chia được đỉnh thành hai phía, mọi cạnh nối hai phía khác nhau, khi và chỉ khi nó không có chu trình độ dài lẻ. Kiểm bằng cách duyệt từng thành phần và tô màu: đỉnh đầu màu 1, hàng xóm của đỉnh màu $c$ nhận màu $3 - c$. Gặp một cạnh hai đầu cùng màu là vô nghiệm; không gặp thì cách tô đó là một cách chia.

Chu trình trong đồ thị vô hướng. Các cạnh mà DFS đi xuống tạo thành một cây gọi là cây DFS: đỉnh gọi DFS cho $v$ là cha của $v$, các đỉnh trên đường từ đỉnh xuất phát xuống $u$ là tổ tiên của $u$. Trong DFS, cạnh tới một đỉnh đã thăm mà không phải cha là một cạnh ngược: nó nối đỉnh hiện tại với một tổ tiên, và cùng đường đi trên cây DFS tạo thành chu trình. Lần par từ đỉnh hiện tại về tổ tiên đó là in được chu trình. Đồ thị có hướng cần ba trạng thái (chưa thăm, đang trên ngăn xếp, đã xong), sẽ gặp ở bài 3.3.

Ví dụChia Hai Nhóm Tương Khắc

Đề. $n \le 10^5$ người, $m \le 2 \cdot 10^5$ cặp không được cùng nhóm. In nhóm (1 hoặc 2) của từng người, hoặc IMPOSSIBLE.

Lời giải. Bài hỏi đồ thị có hai phía không. Tô hai màu bằng BFS: mỗi thành phần bắt đầu ở một đỉnh chưa tô với màu 1, hàng xóm nhận màu ngược lại. Thành phần khác nhau không ràng buộc nhau. Gặp một cạnh hai đầu cùng màu nghĩa là có chu trình lẻ, không chia được.

Bước 1: tô một thành phần. col[v] = 0 là chưa tô; màu là 1 hoặc 2, nên 3 - c đổi màu. Mọi cạnh được kiểm khi lấy đầu mút ra khỏi hàng đợi.

queue<ll> q;
q.push(s);
col[s] = 1;
while (!q.empty()) {
    ll u = q.front();
    q.pop();
    for (ll v : g[u]) {
        if (!col[v]) {
            col[v] = 3 - col[u];
            q.push(v);
        } else if (col[v] == col[u]) {
            cout << "IMPOSSIBLE\n";
            return 0;
        }
    }
}

Bước 2: mọi thành phần. Vòng ngoài chạy $s = 1..n$, bỏ qua đỉnh đã tô.

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

const ll N = 1e5 + 5;
ll n, m, col[N];
vector<ll> g[N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for (ll i = 1; i <= m; i++) {
        ll u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for (ll s = 1; s <= n; s++) {
        if (col[s]) continue;
        queue<ll> q;
        q.push(s);
        col[s] = 1;
        while (!q.empty()) {
            ll u = q.front();
            q.pop();
            for (ll v : g[u]) {
                if (!col[v]) {
                    col[v] = 3 - col[u];
                    q.push(v);
                } else if (col[v] == col[u]) {
                    cout << "IMPOSSIBLE\n";
                    return 0;
                }
            }
        }
    }
    for (ll i = 1; i <= n; i++) cout << col[i] << ' ';
    cout << '\n';
}

ChạyInput6 4
1 2
2 3
4 5
5 6

Output1 2 1 1 2 1

Độ phức tạp: $O(n + m)$.

Nhiều nguồn

Muốn biết với mọi đỉnh, khoảng cách tới đỉnh gần nhất thuộc một tập $S$: đừng BFS từ từng đỉnh, mà đẩy cả tập $S$ vào hàng đợi với khoảng cách 0 rồi BFS một lần. Như thể có một đỉnh nguồn ảo nối tới mọi đỉnh của $S$. Khi cạnh có hướng mà câu hỏi lại là “từ $u$ tới gần nhất tập $S$”, BFS trên đồ thị ngược (đảo chiều mọi cạnh) từ $S$: đường từ $u$ tới $S$ trong đồ thị gốc là đường từ $S$ tới $u$ trong đồ thị ngược.

Ví dụBước Nhảy Đổi Tính Chẵn Lẻ

Đề. Mảng $n \le 2 \cdot 10^5$ số, từ $i$ nhảy được tới $i - a_i$ hoặc $i + a_i$ nếu còn trong mảng. Với mỗi $i$, in số bước ít nhất để tới một vị trí có $a_j$ khác tính chẵn lẻ với $a_i$, hoặc $-1$.

Lời giải. Bước nhảy là cạnh có hướng $i \to i \pm a_i$. Với vị trí $a_i$ lẻ, đáp án là khoảng cách từ $i$ tới tập các vị trí chẵn. BFS từ từng $i$ thì quá chậm; đảo chiều mọi cạnh, khoảng cách từ $i$ tới tập nguồn trên đồ thị gốc bằng khoảng cách từ tập nguồn tới $i$ trên đồ thị ngược, và BFS nhiều nguồn tính được nó cho mọi $i$ một lần. Làm hai lần: nguồn là các vị trí chẵn, rồi nguồn là các vị trí lẻ.

Bước 1: đồ thị ngược. rg[t] chứa mọi $i$ nhảy được tới $t$.

for (ll i = 1; i <= n; i++) {
    if (i - a[i] >= 1) rg[i - a[i]].push_back(i);
    if (i + a[i] <= n) rg[i + a[i]].push_back(i);
}

Bước 2: BFS nhiều nguồn. Nguồn là mọi vị trí có $a_i$ chia 2 dư $p$, khoảng cách 0, cùng vào hàng đợi trước khi BFS. Chỉ ghi ans[i] cho các vị trí có tính chẵn lẻ khác $p$, đúng những vị trí cần tới tập nguồn này.

void bfs(ll p) {
    queue<ll> q;
    for (ll i = 1; i <= n; i++) {
        d[i] = -1;
        if (a[i] % 2 == p) {
            d[i] = 0;
            q.push(i);
        }
    }
    while (!q.empty()) {
        ll u = q.front();
        q.pop();
        for (ll v : rg[u])
            if (d[v] == -1) {
                d[v] = d[u] + 1;
                q.push(v);
            }
    }
    for (ll i = 1; i <= n; i++)
        if (a[i] % 2 != p) ans[i] = d[i];
}

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

const ll N = 2e5 + 5;
ll n, a[N], d[N], ans[N];
vector<ll> rg[N];

void bfs(ll p) {
    queue<ll> q;
    for (ll i = 1; i <= n; i++) {
        d[i] = -1;
        if (a[i] % 2 == p) {
            d[i] = 0;
            q.push(i);
        }
    }
    while (!q.empty()) {
        ll u = q.front();
        q.pop();
        for (ll v : rg[u])
            if (d[v] == -1) {
                d[v] = d[u] + 1;
                q.push(v);
            }
    }
    for (ll i = 1; i <= n; i++)
        if (a[i] % 2 != p) ans[i] = d[i];
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (ll i = 1; i <= n; i++) cin >> a[i];
    for (ll i = 1; i <= n; i++) {
        if (i - a[i] >= 1) rg[i - a[i]].push_back(i);
        if (i + a[i] <= n) rg[i + a[i]].push_back(i);
    }
    bfs(0);
    bfs(1);
    for (ll i = 1; i <= n; i++) cout << ans[i] << ' ';
    cout << '\n';
}

ChạyInput5
1 2 1 2 1

Output1 -1 1 -1 1

Độ phức tạp: hai lần BFS, mỗi lần $O(n)$ vì mỗi đỉnh có tối đa hai cạnh.

Đỉnh phụ

Khi chi phí không nằm trên cạnh mà ở việc đổi một thứ gì đó (đổi tuyến, đổi màu, đổi phương tiện), thêm đỉnh mới cho thứ đó. Mỗi tuyến xe thành một đỉnh, nối với mọi ga trên tuyến: đi từ ga lên tuyến rồi xuống ga khác là hai cạnh, nên số tuyến đã dùng bằng nửa khoảng cách BFS. Số cạnh mới bằng số cặp (ga, tuyến), vẫn $O(m)$, trong khi nối thẳng mọi cặp ga cùng tuyến có thể tới $O(n^2)$ cạnh.