DFS

Để cài đặt thuật toán này mà không sử dụng đến phép đệ quy chúng ta cần có một cấu trúc stack để lưu trữ các đỉnh liền kề của một đỉnh khi được đưa vào xét. Một đỉnh sẽ đựoc đẩy vào stack khi nó là đỉnh đang xét hoặc là đỉnh liền kề của đỉnh đang xét, và đỉnh đó được lấy ra khi nó đã là đỉnh không có đỉnh nào liền kề mà chưa được thăm nữa.

Trong khi cài đặt xuất hiện một giá trị k và nó được gắn = -2 khi không có đỉnh liền kề với đỉnh đang xét nữa, lúc này cũng là thời điểm để một đỉnh được lấy ra khỏi stack

Trong việc cái đặt thuật toán này chúng ta sử dụng hai mảng sau: was_visited[20] là mảng một chiều gồm có 20 phần tử và kiểu dữ liệu của mảng là bool để đánh dấu một đỉnh là được thăm rồi khi đỉnh đó được mang vào xét. Và giá trị mà nó nhận là “true” Một mảng nữa là mảng daTham[20] để chứa những đỉnh đã thăm ngay khi chúng là đỉnh liền kề của đỉnh đang xét. Chính mảng này sẽ được đưa ra như kết quả của bài toán. Đỉnh được đưa vào duyệt đầu tiên chúng ta gọi nó là đỉnh: “start”, số đỉnh của đồ thị sẽ được đọc vào từ file dữ liệu và được gán vào biến: “soDinh”.

Và thuật toán đựơc cài đặt như sau:

if(start<soDinh){

—daTham[0]=start;          //ghi nhận đỉnh đầu tiên được thăm

theStack.push(start);     //đưa đỉnh đó vào stack

was_visited[start]=true;  //đánh dấu đỉnh đã được thăm

int t = 0;    //để đảm bảo các đỉnh liền kề đã duyết thì không bị lặp lại

while(!theStack.is_empty()){

dinhStack =
theStack.giaTriDauStack();   //tìm đến đỉnh đầu stack

int k =
dinhLienKe(dinhStack,t);

if(k==-2){             //nếu không có đỉnh liền kề         

theStack.pop(dinhStack);//lấy ra phần tử đầu stack

t = 0;

}

else{

was_visited[k] = true;// đánh dấu đỉnh liền kề của đỉnh v đã thăm

if(k<soDinh-1)

t =
k+1;          //sẽ duyệt từ đỉnh thứ k+1

else t = k;         //nếu k = sốđỉnh thì không duyệt nữa

theStack.push(k);   //đưa đỉnh liền kề vào stack

daTham[++stt] = k;// đưa đỉnh liền kề vào mảng đã thăm theo thứ tự

}

}

}

2 thoughts on “DFS

  1. Bác Gió ơi !
    Cháu có bài toán tìm tâp phủ đỉnh của một đồ thị vô hướng. Cháu đã có thuật toán như sau
    – khởi tạo tập đỉnh C rỗng
    – Khởi tạo tập cạnh E’= tập cạnh E của đồ thị vô hướng G
    while (E’ khác rỗng)
    do {
    -chọn 2 đỉnh bất kỳ tạo thành cạnh trong E’.
    -nạp 2 dỉnh này vào C
    -xóa tất cả các cạnh trong E’ chứa 1 trong 2 đỉnh đó.
    }
    -Kêt thúc thuật toán cho ra tập C là tập phủ đỉnh (vertex cover) của đồ thịv ô huwongs C
    Hiện tại cháu đã Code nhưng chạy ko ra kết quả. Cháu có teher gửi code của cháu để bác xem và góp ý giúp đc ko ạ. Chờ email của bác vào hòm Gmail của Cháu ở trên ! Thanx bác Gió !

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s