Thuật toán duyệt đồ thị ưu tiên chiều rộng

Thuật toán duyệt đồ thị ưu tiên chiều rộng (Breadth-first search - BFS) là một trong những thuật toán tìm kiếm cơ bản và thiết yếu trên đồ thị. Mà trong đó, những đỉnh nào gần đỉnh xuất phát hơn sẽ được duyệt trước.

Ứng dụng của $BFS$ có thể giúp ta giải quyết tốt một số bài toán trong thời gian và không gian tối thiểu. Đặc biệt là bài toán tìm kiếm đường đi ngắn nhất từ một đỉnh gốc tới tất cả các đỉnh khác. Trong đồ thị không có trọng số hoặc tất cả trọng số bằng nhau, thuật toán sẽ luôn trả ra đường đi ngắn nhất có thể. Ngoài ra, thuật toán này còn được dùng để tìm các thành phần liên thông của đồ thị, hoặc kiểm tra đồ thị hai phía, …

Ý tưởng

Với đồ thị không trọng số và đỉnh nguồn $s$. Đồ thị này có thể là đồ thị có hướng hoặc vô hướng, điều đó không quan trọng đối với thuật toán.

Có thể hiểu thuật toán như một ngọn lửa lan rộng trên đồ thị:

• Ở bước thứ $0$, chỉ có đỉnh nguồn $s$ đang cháy.
• Ở mỗi bước tiếp theo, ngọn lửa đang cháy ở mỗi đỉnh lại lan sang tất cả các đỉnh kề với nó.

Trong mỗi lần lặp của thuật toán, "vòng lửa" lại lan rộng ra theo chiều rộng. Những đỉnh nào gần $s$ hơn sẽ bùng cháy trước.

Chính xác hơn, thuật toán có thể được mô tả như sau:

• Đầu tiên ta thăm đỉnh nguồn $s$.
• Việc thăm đỉnh $s$ sẽ phát sinh thứ tự thăm các đỉnh $(u_1, u_2, … u_p)$ kề với $s$ (những đỉnh gần $s$ nhất). Tiếp theo, ta thăm đỉnh $u_1$, khi thăm đỉnh $u_1$ sẽ lại phát sinh yêu cầu thăm những đỉnh $(v_1, v_2, …, v_q)$ kề với $u_1$. Nhưng rõ ràng những đỉnh $v$ này “xa” $s$ hơn những đỉnh $u$ nên chúng chỉ được thăm khi tất cả những đỉnh $u$ đều đã được thăm. Tức là thứ tự thăm các đỉnh sẽ là: $s, u_1, u_2, …, u_p, v_1, v_2, …, v_q, …$

Thuật toán tìm kiếm theo chiều rộng sử dụng một danh sách để chứa những đỉnh đang “chờ” thăm. Tại mỗi bước, ta thăm một đỉnh đầu danh sách, loại nó ra khỏi danh sách và cho những đỉnh kề với nó chưa được thăm xếp hàng vào cuối danh sách. Thuật toán sẽ kết thúc khi danh sách rỗng.

Thuật toán

Thuật toán sử dụng một cấu trúc dữ liệu hàng đợi (queue) để chứa các đỉnh sẽ được duyệt theo thứ tự ưu tiên chiều rộng.

Bước 1: Khởi tạo

• Các đỉnh đều ở trạng thái chưa được đánh dấu. Ngoại trừ đỉnh nguồn $s$ đã được đánh dấu.
• Một hàng đợi ban đầu chỉ chứa $1$ phần tử là $s$.

Bước 2: Lặp lại các bước sau cho đến khi hàng đợi rỗng:

• Lấy đỉnh $u$ ra khỏi hàng đợi.
• Xét tất cả những đỉnh $v$ kề với $u$ mà chưa được đánh dấu, với mỗi đỉnh $v$ đó:
  • Đánh dấu $v$ đã thăm.
  • Lưu lại vết đường đi từ $u$ đến $v$.
  • Đẩy $v$ vào trong hàng đợi (đỉnh $v$ sẽ chờ được duyệt tại những bước sau).

Bước 3: Truy vết tìm đường đi.

Mô tả

• Xét đồ thị sau đây, với đỉnh nguồn $s=1$ :

• Quá trình:

Cài đặt

Cấu trúc dữ liệu:

• Biến

  if (!visit[u]) cout << "No path!"; else {

  vector  path;  
  for (int v = u; v != -1; v = par[v])  
      path.push_back(v);  
  reverse(path.begin(), path.end());  
  cout << "Path: ";  
  for (auto v : path) cout << v << ' ';  
  

  }
  0 - Kích thước mảng.
• Mảng

  if (!visit[u]) cout << "No path!"; else {

  vector  path;  
  for (int v = u; v != -1; v = par[v])  
      path.push_back(v);  
  reverse(path.begin(), path.end());  
  cout << "Path: ";  
  for (auto v : path) cout << v << ' ';  
  

  }
  1 - Mảng lưu lại khoảng cách từ đỉnh nguồn đến mọi đỉnh.
• Mảng

  if (!visit[u]) cout << "No path!"; else {

  vector  path;  
  for (int v = u; v != -1; v = par[v])  
      path.push_back(v);  
  reverse(path.begin(), path.end());  
  cout << "Path: ";  
  for (auto v : path) cout << v << ' ';  
  

  }
  2 - Mảng lưu lại vết đường đi.
• Mảng

  if (!visit[u]) cout << "No path!"; else {

  vector  path;  
  for (int v = u; v != -1; v = par[v])  
      path.push_back(v);  
  reverse(path.begin(), path.end());  
  cout << "Path: ";  
  for (auto v : path) cout << v << ' ';  
  

  }
  3 - Mảng đánh dấu các đỉnh đã thăm.
• Vector

  if (!visit[u]) cout << "No path!"; else {

  vector  path;  
  for (int v = u; v != -1; v = par[v])  
      path.push_back(v);  
  reverse(path.begin(), path.end());  
  cout << "Path: ";  
  for (auto v : path) cout << v << ' ';  
  

  }
  4 - Danh sách cạnh kề của mỗi đỉnh.
• Hàng đợi

  if (!visit[u]) cout << "No path!"; else {

  vector  path;  
  for (int v = u; v != -1; v = par[v])  
      path.push_back(v);  
  reverse(path.begin(), path.end());  
  cout << "Path: ";  
  for (auto v : path) cout << v << ' ';  
  

  }
  5 - Chứa các đỉnh sẽ được duyệt theo thứ tự ưu tiên chiều rộng.

int n; // Số lượng đỉnh của đồ thị
int d[maxN], par[maxN];
bool visit[maxN];
vector  g[maxN];
void bfs(int s) { // Với s là đỉnh xuất phát (đỉnh nguồn)
    fill_n(d, n + 1, 0);
    fill_n(par, n + 1, -1);
    fill_n(visit, n + 1, false);
    queue  q;
    q.push(s);
    visit[s] = true;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (auto v : g[u]) {
            if (!visit[v]) {
                d[v]     = d[u] + 1;
                par[v]   = u;
                visit[v] = true;
                q.push(v);
            }
        }
    }
}

Truy vết

• Cài đặt truy vết đường đi từ đỉnh nguồn $s$ đến đỉnh $u$ :

if (!visit[u]) cout << "No path!";
else {
    vector  path;
    for (int v = u; v != -1; v = par[v])
        path.push_back(v);
    reverse(path.begin(), path.end());
    cout << "Path: ";
    for (auto v : path) cout << v << ' ';
}

Các đặc tính của thuật toán

Nếu sử dụng một ngăn xếp (stack) thay vì hàng đợi (queue) thì ta sẽ thu được thứ tự duyệt đỉnh của thuật toán tìm kiếm theo chiều sâu (Depth First Search – DFS). Đây chính là phương pháp khử đệ quy của $DFS$ để cài đặt thuật toán trên các ngôn ngữ không cho phép đệ quy.

Định lí: Thuật toán $BFS$ cho ta độ dài đường đi ngắn nhất từ đỉnh nguồn tới mọi đỉnh (với khoảng cách tới đỉnh $u$ bằng $d[u]$). Trong thuật toán $BFS$, nếu đỉnh $u$ xa đỉnh nguồn hơn đỉnh $v$, thì $u$ sẽ được thăm trước.

• Chứng minh: Trong $BFS$, từ một đỉnh hiện tại, ta luôn đi thăm tất cả các đỉnh kề với nó trước, sau đó thăm tất cả các đỉnh cách nó một đỉnh, rồi các đỉnh cách nó hai đỉnh, v.v… Như vậy, nếu từ một đỉnh $u$ khi ta chạy $BFS$, quãng đường đến đỉnh $v$ luôn là quãng đường đi qua ít cạnh nhất.

Định lý Bắt tay (Handshaking lemma)

Định lý: Trong một đồ thị bất kỳ, tổng số bậc của tất cả các đỉnh bằng gấp đôi số cạnh của đồ thị.

• Mô tả: Cho đồ thị $G=(V,E)$ gồm $|V|$ đỉnh và $|E|$ cạnh. Khi đó, tổng tất cả các bậc của đỉnh trong $G$ bằng $2 \times |E|$ . Với $deg(v)$ là số bậc của đỉnh $v$, ta có: $\displaystyle\sum_{v \in V}deg(v) = 2 \times |E|$
  • Ví dụ: Cho đồ thị sau với $|V| = 8$ và $|E| = 7$
    • $\displaystyle\sum_{v \in V}deg(v) = 2 \times |E| = 2 \times 7 = 14$
• Chứng minh: Vì mỗi một cạnh nối với đúng hai đỉnh của đồ thị, nên một cạnh sẽ đóng góp $2$ đơn vị vào tổng số bậc của tất cả các đỉnh.

Hệ quả: Trong đồ thị, số lượng đỉnh bậc lẻ luôn là một số chẵn.

• Chứng minh: Gọi $L$ và $C$ lần lượt là tập các đỉnh bậc lẻ và bậc chẵn của đồ thị $G=(V, E)$. Ta có: $2 \times |E| = \displaystyle\sum_{v \in V}deg(v) = \displaystyle\sum_{v \in L}deg(v) + \displaystyle\sum_{v \in C}deg(v)$
  • $2 \times |E|$ chẵn
  • $\displaystyle\sum_{v \in C}deg(v)$ chẵn $\Rightarrow$ $\displaystyle\sum_{v \in L}deg(v)$ chẵn

Nhận xét:

• Trong quá trình duyệt đồ thị được biểu diễn bằng danh sách kề, mỗi cạnh sẽ được duyệt chính xác hai lần đối với đồ thị vô hướng (vì mỗi cạnh sẽ được lưu trong $2$ danh sách kề của $2$ đỉnh). Còn đối với đồ thị có hướng, mọi cạnh của đồ thị chỉ được duyệt chính xác một lần.

Tham khảo: Handshaking_lemma

Độ phức tạp thuật toán

Độ phức tạp thời gian

Gọi $|V|$ là số lượng đỉnh và $|E|$ là số lượng cạnh của đồ thị.

Trong quá trình $BFS$, cách biểu diễn đồ thị có ảnh hưởng lớn tới chi phí về thời gian thực hiện giải thuật :

• Nếu đồ thị biểu diễn bằng danh sách kề (vector

  if (!visit[u]) cout << "No path!"; else {

  vector  path;  
  for (int v = u; v != -1; v = par[v])  
      path.push_back(v);  
  reverse(path.begin(), path.end());  
  cout << "Path: ";  
  for (auto v : path) cout << v << ' ';  
  

  }

• :
  • Ta có thể thực hiện thuật toán này một cách tối ưu nhất về mặt thời gian nhờ khả năng duyệt qua các đỉnh kề của mỗi đỉnh một cách hiệu quả.
  • Vì ta sử dụng mảng

    if (!visit[u]) cout << "No path!"; else {

       vector  path;  
       for (int v = u; v != -1; v = par[v])  
           path.push_back(v);  
       reverse(path.begin(), path.end());  
       cout << "Path: ";  
       for (auto v : path) cout << v << ' ';  
    

    }
    3 để ngăn việc đẩy một đỉnh vào hàng đợi nhiều lần nên mỗi đỉnh sẽ được thăm chính xác một lần duy nhất. Do đó, ta mất độ phức tạp thời gian $O(|V|)$ dành cho việc thăm các đỉnh.
  • Bất cứ khi nào một đỉnh được thăm, mọi cạnh kề với đỉnh đó đều được duyệt, với thời gian dành cho mỗi cạnh là $O(1)$. Từ phần nhận xét của định lý Bắt tay (Handshaking lemma), ta sẽ mất độ phức tạp thời gian $O(|E|)$ dành cho việc duyệt các cạnh.
  • Nhìn chung, độ phức tạp thời gian của thuật toán này là $O(|V|+|E|)$. Đây là cách cài đặt tốt nhất.
• Nếu đồ thị được biểu diễn bằng ma trận kề :
  • Ta cũng sẽ mất độ phức tạp thời gian $O(|V|)$ dành cho việc thăm các đỉnh (giải thích tương tự như trên).
  • Với mỗi đỉnh được thăm, ta sẽ phải duyệt qua toàn bộ các đỉnh của đồ thị để kiểm tra đỉnh kề với nó. Do đó, thuật toán sẽ mất độ phức tạp $O(|V|^2)$.

Độ phức tạp không gian

Tại mọi thời điểm, trong hàng đợi (queue

if (!visit[u]) cout << "No path!";
else {
    vector  path;
    for (int v = u; v != -1; v = par[v])
        path.push_back(v);
    reverse(path.begin(), path.end());
    cout << "Path: ";
    for (auto v : path) cout << v << ' ';
}

5. có không quá $|V|$ phần tử. Do đó, độ phức tạp bộ nhớ là $O(|V|)$.

Ứng dụng BFS để xác định thành phần liên thông

Bài toán 1

BDFS - Đếm số thành phần liên thông

Đề bài

Cho đơn đồ thị vô hướng gồm $n$ đỉnh và $m$ cạnh $(1 \le n, m \le 10^5)$, các đỉnh được đánh số từ $1$ tới $n$. Tìm số thành phần liên thông của đồ thị.

Ý tưởng

Một đồ thị có thể liên thông hoặc không liên thông. Nếu đồ thị liên thông thì số thành phần liên thông của nó là $1$. Điều này tương đương với phép duyệt theo thủ tục $BFS$ được gọi đến đúng một lần. Nếu đồ thị không liên thông (số thành phần liên thông lớn hơn $1$) ta có thể tách chúng thành những đồ thị con liên thông. Điều này cũng có nghĩa là trong phép duyệt đồ thị, số thành phần liên thông của nó bằng số lần gọi tới thủ tục $BFS$.

Thuật toán

Thuật toán ứng dụng $BFS$ để xác định thành phần liên thông:

• Bước 0: Khởi tạo số lượng thành phần liên thông bằng $0$.
• Bước 1: Xuất phát từ một đỉnh chưa được đánh dấu của đồ thị. Ta đánh dấu đỉnh xuất phát, tăng số thành phần liên thông thêm $1$.
• Bước 2: Từ một đỉnh $i$ đã đánh dấu, ta đánh dấu tất cả các đỉnh $j$ kề với $i$ mà $j$ chưa được đánh dấu.
• Bước 3: Thực hiện bước $2$ cho đến khi không còn thực hiện được nữa.
• Bước 4: Nếu số số đỉnh đánh dấu bằng $n$ (mọi đỉnh đều được đánh dấu) kết thúc thuật toán và trả về số thành phần liên thông, ngược lại quay về bước $1$.

Mô tả

Cài đặt

Cấu trúc dữ liệu:

• Hằng số

  if (!visit[u]) cout << "No path!"; else {

  vector  path;  
  for (int v = u; v != -1; v = par[v])  
      path.push_back(v);  
  reverse(path.begin(), path.end());  
  cout << "Path: ";  
  for (auto v : path) cout << v << ' ';  
  

  }
  9.
• Biến `

include

using namespace std; const int maxN = 1e5 + 7; int n, m, components = 0; bool visit[maxN]; vector g[maxN]; void bfs(int s) {

++components;  
queue  q;  
q.push(s);  
visit[s] = true;  
while (!q.empty()) {  
    int u = q.front();  
    q.pop();  
    for (auto v : g[u]) {  
        if (!visit[v]) {  
            visit[v] = true;  
            q.push(v);  
        }  
    }  
}  

} int main() {

cin >> n >> m;  
while (m--) {  
    int u, v;  
    cin >> u >> v;  
    g[u].push_back(v);  
    g[v].push_back(u);  
}  
fill_n(visit, n + 1, false);  
for (int i = 1; i <= n; ++i)  
    if (!visit[i]) bfs(i);  
cout << components;  

}

0 - Số lượng thành phần liên thông.
Mảng  
  
if (!visit[u]) cout << "No path!";  
else {  
    vector  path;  
    for (int v = u; v != -1; v = par[v])  
        path.push_back(v);  
    reverse(path.begin(), path.end());  
    cout << "Path: ";  
    for (auto v : path) cout << v << ' ';  
}  
  
3 - Mảng đánh dấu các đỉnh đã thăm.
Vector  
  
if (!visit[u]) cout << "No path!";  
else {  
    vector  path;  
    for (int v = u; v != -1; v = par[v])  
        path.push_back(v);  
    reverse(path.begin(), path.end());  
    cout << "Path: ";  
    for (auto v : path) cout << v << ' ';  
}  
  
4 - Danh sách cạnh kề của mỗi đỉnh.
Hàng đợi  
  
if (!visit[u]) cout << "No path!";  
else {  
    vector  path;  
    for (int v = u; v != -1; v = par[v])  
        path.push_back(v);  
    reverse(path.begin(), path.end());  
    cout << "Path: ";  
    for (auto v : path) cout << v << ' ';  
}  
  
5 - Chứa các đỉnh sẽ được duyệt theo thứ tự ưu tiên chiều rộng.

include

using namespace std; const int maxN = 1e5 + 7; int n, m, components = 0; bool visit[maxN]; vector g[maxN]; void bfs(int s) {

++components;
queue  q;
q.push(s);
visit[s] = true;
while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (auto v : g[u]) {
        if (!visit[v]) {
            visit[v] = true;
            q.push(v);
        }
    }
}

} int main() {

cin >> n >> m;
while (m--) {
    int u, v;
    cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
}
fill_n(visit, n + 1, false);
for (int i = 1; i <= n; ++i)
    if (!visit[i]) bfs(i);
cout << components;

} `

Đánh giá

Ta cũng có thể sử dụng thuật toán tìm kiếm theo chiều sâu (Depth First Search – DFS) để kiểm tra đồ thị hai phía.