21xrx.com
2025-06-19 20:32:34 Thursday
登录
文章检索 我的文章 写文章
C语言实现DFS算法
2023-09-16 06:53:05 深夜i     28     0
C语言 实现 DFS算法

DFS（深度优先搜索）是一种用于遍历或搜索图形或树的算法。它可以用来解决许多实际问题，例如迷宫问题、图形连通性问题和寻找最短路径等。在本文中，将介绍如何使用C语言实现DFS算法。

DFS算法基于堆栈的工作原理。它首先访问一个节点，并将其标记为已访问。然后，遍历该节点的未访问邻居节点，并对每个邻居节点进行递归的DFS调用。这样，可以一直往下遍历直到图形或树的底端。然后回溯至堆栈中的上一个未访问节点，并继续遍历其未访问邻居节点。直到所有节点都被访问为止。

接下来，我们将展示一个简单的示例来说明DFS算法的实现。假设我们有一个包含5个节点的图形，节点用字母A、B、C、D和E表示，如下所示：

A----B
  |   |
  |   |
  D----C

我们使用邻接列表来表示图形。为了实现DFS算法，我们首先需要定义一个用于表示节点的结构体，其中包含一个指向邻居节点的指针数组。然后，我们需要定义一个堆栈数据结构来存储待访问的节点。

下面是一个使用C语言实现DFS算法的示例代码：

#include <stdio.h>
#include <stdlib.h>
typedef struct node {
  char data;
  struct node** neighbors;
  int visited;
} Node;
typedef struct stack {
  Node** data;
  int top;
} Stack;
Node* createNode(char data) {
  Node* newNode = (Node*)malloc(sizeof(Node));
  newNode->data = data;
  newNode->neighbors = (Node**)malloc(sizeof(Node*) * 5);
  newNode->visited = 0;
  return newNode;
}
Stack* createStack() {
  Stack* newStack = (Stack*)malloc(sizeof(Stack));
  newStack->data = (Node**)malloc(sizeof(Node*) * 5);
  newStack->top = -1;
  return newStack;
}
void push(Stack* stack, Node* node) {
  stack->data[++stack->top] = node;
}
Node* pop(Stack* stack) {
  return stack->data[stack->top--];
}
void DFS(Node* startNode) {
  Stack* stack = createStack();
  push(stack, startNode);
  while (stack->top != -1) {
    Node* currentNode = pop(stack);
    if (!currentNode->visited) {
      printf("%c ", currentNode->data);
      currentNode->visited = 1;
    }
    for (int i = 0; i < 5; i++) {
      if (currentNode->neighbors[i] != NULL && !currentNode->neighbors[i]->visited) {
        push(stack, currentNode->neighbors[i]);
      }
    }
  }
  free(stack);
}
int main() {
  // 创建图形节点
  Node* A = createNode('A');
  Node* B = createNode('B');
  Node* C = createNode('C');
  Node* D = createNode('D');
  Node* E = createNode('E');
  // 设置节点间的邻居关系
  A->neighbors[0] = B;
  A->neighbors[1] = D;
  B->neighbors[0] = A;
  B->neighbors[1] = C;
  C->neighbors[0] = D;
  C->neighbors[1] = B;
  D->neighbors[0] = A;
  D->neighbors[1] = C;
  printf("DFS遍历结果：");
  DFS(A); // 以节点A为起点进行DFS遍历
  // 释放内存
  free(A->neighbors);
  free(B->neighbors);
  free(C->neighbors);
  free(D->neighbors);
  free(A);
  free(B);
  free(C);
  free(D);
  free(E);
  return 0;
}

在此示例中，我们创建了一个包含5个节点的图形，并设置其邻居关系。然后，我们从节点A开始进行DFS遍历。最后，我们释放了动态分配的内存。

通过运行上述代码，我们可以得到以下输出：

DFS遍历结果：A B C D

这表明DFS算法按照预期的顺序遍历了所有的节点。

总结起来，DFS算法是一种强大且广泛使用的图形搜索算法。使用C语言可以轻松实现DFS算法，通过对节点的遍历和递归调用，可以找到所需的解决方案。尽管示例中的图形较小，但我们可以使用相同的原理和代码，处理规模更大的图形或树。

  
  

评论区