用C语言实现DFS

  • Z时代
  • 2024-01-10
  • 分类：综合

深度优先搜索 (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

以上是 用C语言实现DFS 的全部内容， 来源链接： utcz.com/z/341333.html

回到顶部