Tìm kiếm đầu tiên theo chiều sâu (DFS) là một thuật toán duyệt qua một biểu đồ và truy cập vào tất cả các nút trước khi quay lại nó có thể xác định. Ngoài ra, nó xác định xem có tồn tại một đường dẫn giữa hai nút hay không.
Nó tìm kiếm một biểu đồ hoặc cây theo cách thức chuyên sâu.
Thuật toán
Dưới đây là một thuật toán để triển khai Tìm kiếm đầu tiên theo độ sâu (DFS) -
Bước 1 - Ban đầu ngăn xếp trống.
Bước 2 - Nếu một nút được truy cập không có trong ngăn xếp, thì chúng tôi đẩy nó lên ngăn xếp và đánh dấu nó là đã thăm.
Bước 3 - Sau đó, kiểm tra xem nút hiện tại có phù hợp với tiêu chí tìm kiếm của chúng tôi hay không.
Bước 3.1 - Nếu nó ở đó, thì chúng ta đã hoàn tất.
Bước 4 - Nếu không, chúng ta cần đi đến tất cả các nút liền kề từ nút hiện tại.
Bước 4.1 - Sau đó truy cập tất cả các loại nút đó, theo bất kỳ thứ tự ngẫu nhiên nào và tiếp tục tìm kiếm.
Bước 5 - Nếu tất cả các nút liền kề đã được truy cập thì nó sẽ trở thành một ngõ cụt.
Bước 6 - Chúng tôi đi đến nút đã truy cập trước đó và bật nút gần đây khỏi ngăn xếp.
Bước 7 - Thuật toán sẽ kết thúc nếu tất cả các nút đã được tìm kiếm hoặc nếu chúng tôi nhận được câu trả lời.
Chương trình
Sau đây là chương trình C để triển khai Tìm kiếm đầu tiên theo độ sâu (DFS) -
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX 5
void addVertex(char);
void addEdge(int,int );
void displayVertex(int);
void depthFirstSearch();
int getAdjUnvisitedVertex(int);
struct Vertex {
char label;
bool visited;
};
//stack variables
int stack[MAX];
int top = -1;
//graph variables
//array of vertices
struct Vertex* lstVertices[MAX];
//adjacency matrix
int adjMatrix[MAX][MAX];
//vertex count
int vertexCount = 0;
//stack functions
void push(int item) {
stack[++top] = item;
}
int pop() {
return stack[top--];
}
int peek() {
return stack[top];
}
bool isStackEmpty() {
return top == -1;
}
//graph functions
//add vertex to the vertex list
void addVertex(char label) {
struct Vertex* vertex = (struct Vertex*) malloc(sizeof(struct Vertex));
vertex->label = label;
vertex->visited = false;
lstVertices[vertexCount++] = vertex;
}
//add edge to edge array
void addEdge(int start,int end) {
adjMatrix[start][end] = 1;
adjMatrix[end][start] = 1;
}
//display the vertex
void displayVertex(int vertexIndex) {
printf("%c ",lstVertices[vertexIndex]->label);
}
//get the adjacent unvisited vertex
int getAdjUnvisitedVertex(int vertexIndex) {
int i;
for(i = 0; i < vertexCount; i++) {
if(adjMatrix[vertexIndex][i] == 1 && lstVertices[i]->visited == false) {
return i;
}
}
return -1;
}
void depthFirstSearch() {
int i;
//mark first node as visited
lstVertices[0]->visited = true;
//display the vertex
displayVertex(0);
//push vertex index in stack
push(0);
while(!isStackEmpty()) {
//get the unvisited vertex of vertex which is at top of the stack
int unvisitedVertex = getAdjUnvisitedVertex(peek());
//no adjacent vertex found
if(unvisitedVertex == -1) {
pop();
} else {
lstVertices[unvisitedVertex]->visited = true;
displayVertex(unvisitedVertex);
push(unvisitedVertex);
}
}
//stack is empty, search is complete, reset the visited flag
for(i = 0;i < vertexCount;i++) {
lstVertices[i]->visited = false;
}
}
int main() {
int i, j;
for(i = 0; i < MAX; i++) // set adjacency {
for(j = 0; j < MAX; j++) // matrix to 0
adjMatrix[i][j] = 0;
addVertex('S'); // 0
addVertex('A'); // 1
addVertex('B'); // 2
addVertex('C'); // 3
addVertex('D'); // 4
addEdge(0, 1); // S - A
addEdge(0, 2); // S - B
addEdge(0, 3); // S - C
addEdge(1, 4); // A - D
addEdge(2, 4); // B - D
addEdge(3, 4); // C - D
printf("Depth First Search: ");
depthFirstSearch();
return 0;
} Đầu ra
Khi chương trình trên được thực thi, nó tạo ra kết quả sau -
Depth First Search: S A D B C