Thuật toán dfs dùng stack

     

Giải thuật tìm kiếm theo chiều sâu là gì ?

Giải thuật tìm kiếm theo chiều sâu (Depth First Search – viết tắt là DFS), còn được gọi là giải thuật tìm kiếm ưu tiên chiều sâu, là giải thuật duyệt hoặc tìm kiếm trên một cây hoặc một đồ thị và sử dụng stack (ngăn xếp) để ghi nhớ đỉnh liền kề để bắt đầu việc tìm kiếm khi không gặp được đỉnh liền kề trong bất kỳ vòng lặp nào. Giải thuật tiếp tục cho tới khi gặp được đỉnh cần tìm hoặc tới một nút không có con. Khi đó giải thuật quay lui về đỉnh vừa mới tìm kiếm ở bước trước.

Bạn đang xem: Thuật toán dfs dùng stack

*

Trong hình minh họa trên, giải thuật tìm kiếm theo chiều sâu đầu tiên duyệt từ các đỉnh A tới B tới C tới D sau đó tới E, sau đó tới F và cuối cùng tới G. Giải thuật này tuân theo qui tắc sau:

Qui tắc 1: Duyệt tiếp tới đỉnh liền kề mà chưa được duyệt. Đánh dấu đỉnh mà đã được duyệt. Hiển thị đỉnh đó và đẩy vào trong một ngăn xếp (stack).Qui tắc 2: Nếu không tìm thấy đỉnh liền kề, thì lấy một đỉnh từ trong ngăn xếp (thao tác pop up). (Giải thuật sẽ lấy tất cả các đỉnh từ trong ngăn xếp mà không có các đỉnh liền kề nào)Qui tắc 3: Lặp lại các qui tắc 1 và qui tắc 2 cho tới khi ngăn xếp là trống.

Bảng dưới đây minh họa các qui tắc với hình ví dụ trên:

BướcDuyệtMiêu tả
1.
*
Khởi tạo ngăn xếp (stack)
2.
*
Đánh dấu đỉnh Sđã duyệt và đặt đỉnh này vào trong ngăn xếp. Tìm kiếm bất kỳ đỉnh liền kề nào mà chưa được duyệt từ đỉnh S. Chúng ta có 3 đỉnh và chúng ta có thể lấy bất kỳ đỉnh nào trong số chúng. Ví dụ, chúng ta lấy đỉnh A theo thứ tự chữ cái.
3.
*
Đánh dấu đỉnh A là đã duyệt và đặt vào trong ngăn xếp. Tìm kiếm bất kỳ đỉnh liền kề nào với đỉnh A. Cả SD đều là hai đỉnh liền kề A nhưng chúng ta chỉ quan tâm về đỉnh chưa được duyệt.
4.

Xem thêm: Mẹo Học 450 Câu Hỏi Luật Giao Thông Đường Bộ 450 Câu Hỏi, 450 Câu Hỏi Lý Thuyết, Đáp Án Thi Lái Xe Ôtô

*
Duyệt đỉnh D, đánh dấu đỉnh này là đã duyệt và đặt vào trong ngăn xếp. Ở đây, chúng ta có BC là hai đỉnh kề với D và cả hai đều là chưa được duyệt. Chúng ta sẽ chọn theo thứ tự chữ cái một lần nữa.
5.
*
Chọn B, đánh dấu là đã duyệt và đặt vào trong ngăn xếp. Ở đây B không có bất kỳ đỉnh liền kề nào mà chưa được duyệt. Vì thế chúng ta lấy B ra khỏi ngăn xếp.
6.
*
Kiểm tra phần tử trên cùng của ngăn xếp để trở về nút đã duyệt trước đó và kiểm tra xem đỉnh này có đỉnh nào liền kề mà chưa được duyệt hay không. Ở đây, chúng ta tìm thấy đỉnh D nằm ở trên cùng của ngăn xếp.
7.
*
Chỉ có một đỉnh liền kề với D mà chưa được duyệt, đó là đỉnh C. Chúng ta duyệt C, đánh dấu là đã duyệt và đặt vào trong ngăn xếp.

Xem thêm: Những Cách An Ủi Bạn Trai Khi Buồn, Mệt Mỏi Hiệu Quả Nhất, Những Cách An Ủi Bạn Trai Khi Buồn

C không có bất kỳ đỉnh nào liền kề mà chưa được duyệt, chúng ta tiếp tục lấy các đỉnh từ trong ngăn xếp để tìm xem có còn bất kỳ đỉnh nào liền kề mà chưa được duyệt hay không. Trong ví dụ này là không có, và chúng ta vẫn tiếp tục cho tới khi ngăn xếp là trống.

Tìm kiếm theo chiều sâu trong C

#include #include #include #define MAX 5struct Vertex { char label; bool visited;};//khai bao cac bien cho ngan xep (stack)int stack; int top = -1; //khai bao cac bien lien quan toi do thi (graph)//khai bao danh sach cac dinh (Vertex)struct Vertex* lstVertices;//Khai bao mot ma tran ke (adjacency matrix)int adjMatrix;//khai bao mot bien de dem so dinhint vertexCount = 0;//cac ham thao tac voi ngan xepvoid push(int item) { stack<++top> = item; } int pop() { return stack; } int peek() { return stack;}bool isStackEmpty() { return top == -1;}//cac ham thao tac tren do thi//them dinh vao danh sach cac dinhvoid addVertex(char label) { struct Vertex* vertex = (struct Vertex*) malloc(sizeof(struct Vertex)); vertex->label = label; vertex->visited = false; lstVertices = vertex;}//them canh vao mang cac canhvoid addEdge(int start,int end) { adjMatrix = 1; adjMatrix = 1;}//hien thi dinhvoid displayVertex(int vertexIndex) { printf("%c ",lstVertices->label);} //lay dinh chua duyet tu ma tran keint getAdjUnvisitedVertex(int vertexIndex) { int i; for(i = 0; ivisited == false) { return i; } } return -1;}void depthFirstSearch() { int i; //danh dau nut dau tien (first node) la da duyet (visited) lstVertices<0>->visited = true; //hien thi dinh displayVertex(0); //chen chi muc cua dinh vao trong ngan xep push(0); while(!isStackEmpty()) { //Rut dinh chua duoc duyet tu ngan xep int unvisitedVertex = getAdjUnvisitedVertex(peek()); //khong tim thay dinh lien ke if(unvisitedVertex == -1) { pop(); }else { lstVertices->visited = true; displayVertex(unvisitedVertex); push(unvisitedVertex); } } //ngan xep la trong, hoan thanh tim kiem, reset gia tri cua visited for(i = 0;i visited = false; } }int main() { int i, j; for(i = 0; iKết quả