使用 C 语言演示 DFS 算法 |21xrx.com

使用 C 语言演示 DFS 算法

2023-09-12 02:02:27 深夜i 15 0

C语言 DFS算法演示

DFS（Depth First Search）是一种常用的搜索算法，用于在图或树中遍历和搜索节点。在本文中，我们将使用 C 语言来演示 DFS 算法的实现过程。

首先，让我们定义一个表示图的数据结构。我们可以使用邻接表来表示图，其中每个节点的邻居节点被存储在一个链表中。我们还可以使用一个布尔数组来追踪已访问的节点。

接下来，让我们实现 DFS 算法的核心函数。我们将从指定的起始节点开始进行深度优先搜索。首先，我们将该节点标记为已访问，并打印该节点的值。然后，我们递归地调用 DFS 函数来访问该节点的邻居节点，直到所有可访问的节点都被访问完为止。

#include <stdio.h>
#include <stdbool.h>
#define MAX_NODES 10
struct Node {
  int value;
  struct Node* nextNode;
};
// 图的邻接表表示
struct Graph {
  int numNodes;
  struct Node* adjList[MAX_NODES];
};
// 创建新的节点
struct Node* createNode(int value) {
  struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
  newNode->value = value;
  newNode->nextNode = NULL;
  return newNode;
}
// 在图中添加边
void addEdge(struct Graph* graph, int src, int dest) {
  struct Node* newNode = createNode(dest);
  newNode->nextNode = graph->adjList[src];
  graph->adjList[src] = newNode;
}
// 深度优先搜索
void dfs(struct Graph* graph, int startNode, bool visited[]) {
  visited[startNode] = true;
  printf("%d ", startNode);
  struct Node* currNode = graph->adjList[startNode];
  while (currNode != NULL) {
    int adjNode = currNode->value;
    if (!visited[adjNode]) {
      dfs(graph, adjNode, visited);
    }
    currNode = currNode->nextNode;
  }
}
int main() {
  struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
  graph->numNodes = MAX_NODES;
  for (int i = 0; i < MAX_NODES; i++) {
    graph->adjList[i] = NULL;
  }
  addEdge(graph, 0, 1);
  addEdge(graph, 0, 2);
  addEdge(graph, 1, 3);
  addEdge(graph, 1, 4);
  addEdge(graph, 2, 5);
  addEdge(graph, 2, 6);
  bool visited[MAX_NODES];
  for (int i = 0; i < MAX_NODES; i++) {
    visited[i] = false;
  }
  printf("DFS traversal: ");
  dfs(graph, 0, visited);
  return 0;
}

在上述代码中，我们创建了一个包含 7 个节点的图。然后，我们使用 `addEdge` 函数添加图中的边。最后，我们使用 `dfs` 函数从节点 0 开始进行深度优先搜索，并打印遍历的结果。

编译并运行上述代码，将会输出这个图的 DFS 遍历结果。在本例中，输出的结果是 `0 2 6 5 1 4 3`。这表明 DFS 算法按照深度优先的顺序遍历了图的所有节点。

总而言之，DFS 算法是一种非常有用的搜索算法，可以用于图、树等数据结构的遍历和搜索。通过使用 C 语言实现 DFS 算法，我们可以更好地理解和应用该算法。

上一篇: idea打包java可执行jar包

下一篇: OpenCV图像拼接系统的应用及优势

评论区

相似文章