C语言数据结构图的深度优先遍历

在C语言中，数据结构图（通常指的是图的表示，如邻接矩阵、邻接表等）的深度优先搜索（DFS）是一种用于遍历或查找图中所有节点的算法。DFS的基本思想是从某个起始节点开始，尽可能深地探索分支，直到到达一个叶子节点，然后回溯到上一个未访问的节点继续探索。

下面是使用递归实现深度优先遍历的一个简单示例：

#include <stdio.h>
#include <stdbool.h>

// 图的邻接列表表示，这里假设每个节点是一个整数
typedef struct Node {
    int value;
    struct Node* next;
} Node;

void dfs(Node* node, bool visited[]) {
    if (node == NULL) return;
    
    // 标记当前节点为已访问
    visited[node->value] = true;
    printf("%d ", node->value);

    // 对邻居进行深度优先遍历
    Node* neighbor = node->next;
    while (neighbor != NULL) {
        if (!visited[neighbor->value]) {
            dfs(neighbor, visited);
        }
        neighbor = neighbor->next;
    }
}

int main() {
    Node nodes[] = {1, 2, 3, 4, 5};
    int num_nodes = sizeof(nodes) / sizeof(nodes[0]);
    bool visited[num_nodes];

    // 初始化visited数组为false
    for (int i = 0; i < num_nodes; i++) {
        visited[i] = false;
    }

    // 从节点1开始进行深度优先遍历
    dfs(&nodes[0], visited);

    return 0;
}

在这个例子中，`dfs`函数接受一个节点指针和一个布尔型数组`visited`，用以跟踪已经访问过的节点。当遍历完一个节点的所有邻居后，会回溯到上一个未访问的节点，直到遍历完整张图。