Duyệt theo chiều rộng (BFS) cho Đồ thị

Giới thiệu

Breadth-First Search (BFS) duyệt đồ thị: từ một đỉnh, thăm tất cả đỉnh kề trước, rồi mới đi sâu hơn.

Cần hàng đợi (Queue). Đánh dấu đỉnh đã thăm để tránh lặp do chu trình.

Đầu vào và Đầu ra

Đầu vào: Ma trận kề:
  A B C D E F
A 0 1 1 1 0 0
B 1 0 0 1 1 0
C 1 0 0 1 0 1
D 1 1 1 0 1 1
E 0 1 0 1 0 1
F 0 0 1 1 1 0
Đầu ra: BFS Traversal: B A D E C F

Thuật toán

bfs(vertices, start)

Đầu vào: Danh sách đỉnh, đỉnh bắt đầu.

Đầu ra: Duyệt tất cả nút nếu đồ thị liên thông.

Begin
  định nghĩa hàng đợi que rỗng
  đánh dấu tất cả nút chưa thăm
  thêm start vào que
  trong khi que không rỗng làm:
    lấy phần tử từ que thành u
    hiển thị u
    với mọi đỉnh i kề u làm:
      nếu vertices[i] chưa thăm thì
        đánh dấu vertices[i] tạm thời đã thăm
        thêm i vào que
      done
    đánh dấu u hoàn toàn đã thăm
  done
End

Ví dụ (C++)

#include <iostream>
#include <queue>
#define NODE 6
using namespace std;

typedef struct node { int val; int state; } node;

int graph[NODE][NODE] = {
  {0, 1, 1, 1, 0, 0},
  {1, 0, 0, 1, 1, 0},
  {1, 0, 0, 1, 0, 1},
  {1, 1, 1, 0, 1, 1},
  {0, 1, 0, 1, 0, 1},
  {0, 0, 1, 1, 1, 0}
};

void bfs(node *vert, node s) {
  node u;
  queue<node> que;
  for(int i = 0; i < NODE; i++) vert[i].state = 0;
  vert[s.val].state = 1;
  que.push(s);
  while(!que.empty()) {
    u = que.front(); que.pop();
    cout << char(u.val + 'A') << " ";
    for(int i = 0; i < NODE; i++) {
      if(graph[i][u.val]) {
        if(vert[i].state == 0) {
          vert[i].state = 1;
          que.push(vert[i]);
        }
      }
    }
    u.state = 2;
  }
}

int main() {
  node vertices[NODE], start;
  char s = 'B';
  for(int i = 0; i < NODE; i++) vertices[i].val = i;
  start.val = s - 'A';
  cout << "BFS Traversal: ";
  bfs(vertices, start);
  cout << endl;
}

Kết quả đầu ra

BFS Traversal: B A D E C F