用C语言实现DFS
深度优先搜索(DFS)是一种算法，它遍历图并访问所有节点，然后再返回它可以确定。此外，它还确定两个节点之间是否存在路径。
它以深度方式搜索图或树。
算法
下面给出的是实现深度优先搜索(DFS)的算法-
步骤1-最初堆栈是空的。
第2步-如果要访问的节点不存在于堆栈中，则我们将其压入堆栈并将其标记为已访问。
步骤3-然后，检查当前节点是否符合我们的搜索条件。
步骤3.1-如果它在那里，那么我们就完成了。
步骤4-否则，我们需要从当前节点转到所有相邻节点。
步骤4.1-然后以任何随机顺序访问所有类型的节点，并继续搜索。
步骤5-如果所有相邻节点都已被访问，那么它就变成了死胡同。
第6步-我们转到先前访问过的节点并从堆栈中弹出最近的节点。
步骤7-如果所有节点都被搜索过，或者我们得到了答案，算法将终止。
程序
以下是用于实现深度优先搜索(DFS)的C程序-
#include输出结果#include #include #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