Tìm kiếm
Latest topics
THUẬT TOÁN TÌM KIẾM THEO CHIỀU RỘNG (Breadth First Search)
bkiz :: Giáo Trình :: Toán Rời Rạc
Trang 1 trong tổng số 1 trang
THUẬT TOÁN TÌM KIẾM THEO CHIỀU RỘNG (Breadth First Search)
void BFS(int u){
queue = φ;
u <= queue; /*nạp u vào hàng đợi*/
chuaxet[u] = false;/* đổi trạng thái của u*/
while (queue ≠ φ ) { /* duyệt tới khi nào hàng đợi rỗng*/
queue<=p; /*lấy p ra từ khỏi hàng đợi*/
Thăm_Đỉnh(p); /* duyệt xong đỉnh p*/
for (v ∈ ke(p) ) {/* đưa các đỉnh v kề với p nhưng chưa được xét vào hàng đợi*/
if (chuaxet[v] ) {
v<= queue; /*đưa v vào hàng đợi*/
chuaxet[v] = false;/* đổi trạng thái của v*/
}
}
} /* end while*/
}/* end BFS*/
Thủ tục BFS sẽ thăm tất cả các đỉnh dùng thành phần liên thông với u. Để thăm tất cả các
đỉnh của đồ thị, chúng ta chỉ cần thực hiện đoạn chương trình dưới đây:
{
for (u=1; u≤n; u++)
chuaxet[u] = TRUE;
for (u∈V )
if (chuaxet[u] )
BFS(u);
}
queue = φ;
u <= queue; /*nạp u vào hàng đợi*/
chuaxet[u] = false;/* đổi trạng thái của u*/
while (queue ≠ φ ) { /* duyệt tới khi nào hàng đợi rỗng*/
queue<=p; /*lấy p ra từ khỏi hàng đợi*/
Thăm_Đỉnh(p); /* duyệt xong đỉnh p*/
for (v ∈ ke(p) ) {/* đưa các đỉnh v kề với p nhưng chưa được xét vào hàng đợi*/
if (chuaxet[v] ) {
v<= queue; /*đưa v vào hàng đợi*/
chuaxet[v] = false;/* đổi trạng thái của v*/
}
}
} /* end while*/
}/* end BFS*/
Thủ tục BFS sẽ thăm tất cả các đỉnh dùng thành phần liên thông với u. Để thăm tất cả các
đỉnh của đồ thị, chúng ta chỉ cần thực hiện đoạn chương trình dưới đây:
{
for (u=1; u≤n; u++)
chuaxet[u] = TRUE;
for (u∈V )
if (chuaxet[u] )
BFS(u);
}
Similar topics
» THUẬT TOÁN TÌM KIẾM THEO CHIỀU SÂU (DFS)
» Thuật toán Dijkstra
» Thuật toán Floy
» THUẬT TOÁN KRUSKAL
» Thuật toán DDA (Digital Differential Analizer)
» Thuật toán Dijkstra
» Thuật toán Floy
» THUẬT TOÁN KRUSKAL
» Thuật toán DDA (Digital Differential Analizer)
bkiz :: Giáo Trình :: Toán Rời Rạc
Trang 1 trong tổng số 1 trang
Permissions in this forum:
Bạn không có quyền trả lời bài viết
|
|
Mon Jun 24, 2013 11:27 pm by hangme
» host facebook
Mon Apr 02, 2012 2:26 pm by Admin
» Cyberlink PowerDirector 9 key full
Thu Mar 29, 2012 5:00 pm by Admin
» PowerDirector 10 Ultra
Fri Mar 23, 2012 6:15 pm by Admin
» Mảng - Nhập mảng số nguyên, tính tổng phần tử dương, tìm số hoàn hảo, tìm max, min, sắp xếp từ lớn đến nhỏ, từ nhỏ đến lớn
Sun Mar 18, 2012 9:17 pm by Admin
» HTML+CSS Form đăng nhập
Tue Sep 13, 2011 10:38 pm by Admin
» HTML+javascript : Lịch Dương
Thu Sep 08, 2011 5:15 pm by Admin
» HTML+javascript : Đòng hồ điện tử
Thu Sep 08, 2011 5:06 pm by Admin
» HTML: Form Đăng nhập
Thu Sep 08, 2011 4:42 pm by Admin