Duyệt thành phần liên thông có thể dùng BFS hoặc DFS

Nếu đồ thị có số thành phần liên thông > 1 =>  đồ thị không liên thông.

Ta sử dụng biến solt để ghi nhận các đỉnh cùng 1 thành phần liên thông trong mảng chuaxet[]

-          Nếu đỉnh i chưa được duyệt, chuaxet[i] == 0;

-          Nếu đỉnh i được duyệt thuộc thành phần liên thông thứ j = solt; ta ghi nhận chuaxet[i] = solt;

-          Các đỉnh cùng thành phần liên thông nếu có cùng giá trị trong mảng chuaxet[].

void BFS(int u) {

queue = rỗng;

u ← queue; /*nạp u vào hàng đợi*/

solt = solt + 1;

chuaxet[u] = solt; /*solt là biến toàn cục thiết lập giá trị 0*/

while (queue ≠ rỗng )    { 

      queue ← p; /*lấy p ra từ stack*/

for (v 'thuộc' ke(p) ) { 

            if (chuaxet[v]  ) {

                        v ← queue; /*nạp v vào hàng đợi*/

                        chuaxet[v] = solt; /*v có cùng thành phần liên thông với p*/

                        }

            }

}

}

Để duyệt hết các thành phần liên thông của đồ thị, ta chỉ cần

void Lien_Thong (void) {

      for (i=1; i<=n; i++)

      chuaxet[i] = 0; // khởi tạo mảng chuaxet[]

      for (i=1; i<=n; i++)

                  if (chuaxet[i] == 0) {

solt = solt + 1;

                                    BFS(i);

                        }

}

Để ghi nhận từng đỉnh thuộc thành phần liên thông nào, ta chỉ cần:

void Result( int solt) {

            if (solt == 1) {

            <Đồ thị là liên thông>;

            }

            for (i=1; i<=solt; i++) {

/*Đưa ra thành phần liên thông thứ i*/

            for (j=1; j<=n; j++) {

            if (chuaxet[j] == i)

            <Đưa ra đỉnh j> ;

}

}

}