Tìm kiếm theo chiều rộng (BFS) cho Đồ thị

Duyệt Tìm kiếm theo chiều rộng (BFS) là thuật toán dùng để thăm tất cả nút của đồ thị cho trước. Trong thuật toán duyệt này, một nút được chọn rồi tất cả nút kề được thăm lần lượt. Sau khi hoàn tất các đỉnh kề, nó chuyển sang đỉnh khác và kiểm tra đỉnh kề của nó lại.

Để cài đặt, cần dùng cấu trúc dữ liệu Hàng đợi (Queue). Tất cả đỉnh kề được thêm vào hàng đợi, khi xong các đỉnh kề, một mục bị lấy ra khỏi hàng đợi và bắt đầu duyệt qua đỉnh đó lại.

Trong đồ thị đôi khi có chu trình, nên dùng mảng đánh dấu nút đã thăm hay chưa.

Đầu vào - Ma trận kề của đồ thị.

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 - Duyệt BFS: B A D E C F

Thuật toán

bfs(vertices, start)

Đầu vào − Danh sách đỉnh, và đỉ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
    ban đầu đánh dấu tất cả nút trạng thái chưa thăm
    thêm đỉnh bắt đầu vào que
    while que không rỗng, do
        lấy mục từ que gán cho u
        hiển thị đỉnh u
        for all vertices i kề với u, do
            if vertices[i] chưa thăm, then
                đánh dấu vertices[i] là đang thăm tạm thời
                thêm v vào hàng đợi
            done
        đánh dấu u là đã thăm hoàn toàn
    done
End

Ví dụ (C++)

#include 
#include 
#define NODE 6
using namespace std;
typedef struct node{
    int val;
    int state; //trạng thái
}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;
    int i, j;
    queue que;
    for(i = 0; i
Đầu ra
BFS Traversal: B A D E C F