深度优先搜索 (DFS) 是一种算法,它遍历图并访问所有节点,然后再返回它可以确定。此外,它还确定两个节点之间是否存在路径。
它以深度方式搜索图或树。
下面给出的是实现深度优先搜索(DFS)的算法 -
步骤 1 - 最初堆栈是空的。
第 2 步- 如果要访问的节点不存在于堆栈中,则我们将其压入堆栈并将其标记为已访问。
步骤 3 - 然后,检查当前节点是否符合我们的搜索条件。
步骤 3.1 - 如果它在那里,那么我们就完成了。
步骤 4 - 否则,我们需要从当前节点转到所有相邻节点。
步骤 4.1 - 然后以任何随机顺序访问所有类型的节点,并继续搜索。
步骤 5 - 如果所有相邻节点都已被访问,那么它就变成了死胡同。
第 6 步- 我们转到先前访问过的节点并从堆栈中弹出最近的节点。
步骤 7 - 如果所有节点都被搜索过,或者我们得到了答案,算法将终止。
以下是用于实现深度优先搜索(DFS)的 C 程序-
#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; }; //堆栈变量 int stack[MAX]; int top = -1; //图变量 //顶点数组 struct Vertex* lstVertices[MAX]; //邻接矩阵 int adjMatrix[MAX][MAX]; //顶点数 int vertexCount = 0; //堆栈函数 void push(int item) { stack[++top] = item; } int pop() { return stack[top--]; } int peek() { return stack[top]; } bool isStackEmpty() { return top == -1; } //图函数 //将顶点添加到顶点列表 void addVertex(char label) { struct Vertex* vertex = (struct Vertex*) malloc(sizeof(struct Vertex)); vertex->label = label; vertex->visited = false; lstVertices[vertexCount++] = vertex; } //将边添加到边数组 void addEdge(int start,int end) { adjMatrix[start][end] = 1; adjMatrix[end][start] = 1; } //显示顶点 void displayVertex(int vertexIndex) { printf("%c ",lstVertices[vertexIndex]->label); } //获取相邻的未访问顶点 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; //将第一个节点标记为已访问 lstVertices[0]->visited = true; //显示顶点 displayVertex(0); //将顶点索引推入堆栈 push(0); while(!isStackEmpty()) { //获取位于堆栈顶部的顶点的未访问顶点 int unvisitedVertex = getAdjUnvisitedVertex(peek()); //没有找到相邻的顶点 if(unvisitedVertex == -1) { pop(); } else { lstVertices[unvisitedVertex]->visited = true; displayVertex(unvisitedVertex); push(unvisitedVertex); } } //堆栈为空,搜索完成,重置访问标志 for(i = 0;i < vertexCount;i++) { lstVertices[i]->visited = false; } } int main() { int i, j; for(i = 0; i < MAX; i++) // 设置邻接{ for(j = 0; j < MAX; j++) // 矩阵为 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); // 广告 addEdge(2, 4); // 乙 - 丁 addEdge(3, 4); // C-D printf("深度优先搜索: "); depthFirstSearch(); return 0; }输出结果
执行上述程序时,会产生以下结果 -
深度优先搜索: S A D B C