C语言实现深度优先算法 |21xrx.com

C语言实现深度优先算法

2023-11-06 22:25:59 深夜i -- --

C语言深度优先算法实现

深度优先算法是一种经典的图遍历算法，常被用于解决连通图的相关问题。在图论中，图由节点和边组成，而深度优先算法则是通过递归的方式按照某一条路径尽可能深入图中的节点，直到无法继续深入为止。

在C语言中，可以使用邻接表或邻接矩阵来表示图的结构。假设我们有一个图如下所示：

A / \ B C / \ \ D E F

我们可以用邻接表来表示这个图：


#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 6
typedef struct node {
  int vertex;
  struct node* next;
} Node;
Node* adj_list[MAX_VERTICES];
// 向图中添加边
void add_edge(int start, int end) {
  Node* new_node = (Node*) malloc(sizeof(Node));
  new_node->vertex = end;
  new_node->next = adj_list[start];
  adj_list[start] = new_node;
}
// 深度优先遍历
void dfs(int vertex, int visited[]) {
  Node* adj_vertex = adj_list[vertex];
  visited[vertex] = 1;
  printf("%c ", vertex + 65);  // 以字母表示节点
  while (adj_vertex != NULL) {
    int vertex_index = adj_vertex->vertex;
    if (!visited[vertex_index]) {
      dfs(vertex_index, visited);
    }
    adj_vertex = adj_vertex->next;
  }
}
int main() {
  for (int i = 0; i < MAX_VERTICES; i++) {
    adj_list[i] = NULL;
  }
  add_edge(0, 1);  // A -> B
  add_edge(0, 2);  // A -> C
  add_edge(1, 3);  // B -> D
  add_edge(1, 4);  // B -> E
  add_edge(2, 5);  // C -> F
  int visited[MAX_VERTICES] = {0};
  dfs(0, visited); // 从节点A开始深度优先遍历
  return 0;
}

上述代码中，我们首先定义了一个节点结构 `Node`，每个节点保存着它的编号 `vertex` 和指向下一个节点的指针 `next`。然后我们创建了一个大小为 `MAX_VERTICES` 的邻接表 `adj_list`。在 `add_edge` 函数中，我们将边加入到图中。最后，在 `dfs` 函数中，我们递归地深度优先遍历图，并使用一个数组 `visited` 来记录已访问过的节点。

当我们执行这段代码时，输出将会是 `A B D E C F`，即按照深度优先的顺序遍历了图中的节点。

深度优先算法在图遍历和搜索问题中有着广泛的应用。无论是在网络路径规划、迷宫求解还是拓扑排序等领域，深度优先算法都是一个强大且有效的工具。

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

下一篇: OpenCV实现不规则图形质心识别

评论区

()

相似文章