C语言实现DFS算法 |21xrx.com

C语言实现DFS算法

2023-09-20 04:22:50 深夜i 17 0

C语言实现 DFS算法

DFS（深度优先搜索）算法是一种常用的图搜索算法，它可以用于解决许多实际问题。在C语言中，我们可以通过递归来实现DFS算法。

首先，我们需要定义图的结构，可以使用邻接矩阵或邻接表来表示图。在这里，我们使用邻接表。

#include <stdio.h>
#include <stdlib.h>
// 图的邻接表结点
typedef struct Node {
  int vertex;
  struct Node* next;
} Node;
// 图的结构
typedef struct Graph {
  int numVertices;
  Node** adjacencyList;
} Graph;
// 创建图
Graph* createGraph(int numVertices) {
  Graph* graph = (Graph*)malloc(sizeof(Graph));
  graph->numVertices = numVertices;
  graph->adjacencyList = (Node**)malloc(numVertices * sizeof(Node*));
  for (int i = 0; i < numVertices; i++) {
    graph->adjacencyList[i] = NULL;
  }
  return graph;
}
// 添加边
void addEdge(Graph* graph, int src, int dest) {
  // 添加src到dest的边
  Node* newNode = (Node*)malloc(sizeof(Node));
  newNode->vertex = dest;
  newNode->next = graph->adjacencyList[src];
  graph->adjacencyList[src] = newNode;
  // 添加dest到src的边
  newNode = (Node*)malloc(sizeof(Node));
  newNode->vertex = src;
  newNode->next = graph->adjacencyList[dest];
  graph->adjacencyList[dest] = newNode;
}
// 深度优先搜索
void DFS(Graph* graph, int vertex, int* visited) {
  visited[vertex] = 1;
  printf("%d ", vertex);
  Node* temp = graph->adjacencyList[vertex];
  while (temp != NULL) {
    int connectedVertex = temp->vertex;
    if (visited[connectedVertex] == 0) {
      DFS(graph, connectedVertex, visited);
    }
    temp = temp->next;
  }
}
int main() {
  Graph* graph = createGraph(5);
  addEdge(graph, 0, 1);
  addEdge(graph, 0, 2);
  addEdge(graph, 1, 3);
  addEdge(graph, 1, 4);
  int visited[5] = {0};
  printf("DFS: ");
  DFS(graph, 0, visited);
  return 0;
}

在上述代码中，我们首先定义了图的邻接表结构，用于表示图的结点和边。然后，我们实现了创建图和添加边的函数，这样我们就可以构建我们需要的图。

接下来，我们实现了DFS函数。该函数使用递归方式来进行深度优先搜索。首先，我们将当前结点标记为已访问，并打印该结点。然后，我们遍历当前结点的邻居结点，如果邻居结点未被访问，则调用DFS函数继续遍历。

最后，在main函数中，我们创建了一个图，并添加了一些边。我们还定义了一个visited数组来记录结点的访问情况。最后，我们调用DFS函数来遍历整个图，并打印结果。

通过上述的C语言代码，我们可以很方便地实现DFS算法并进行图的遍历。这个算法可以应用于诸如迷宫求解、拓扑排序、连通分量等问题的解决中。

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

下一篇: OpenCV实现特定物体识别技术

评论区

相似文章