c语言实现图的深度优先遍历

在C语言中，我们可以使用邻接表数据结构来实现图的深度优先遍历(Depth First Search, DFS)，因为它对于稀疏图来说存储效率更高。下面是一个简单的示例，展示了如何创建一个图、添加节点和边，然后进行DFS：

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

// 图节点结构体
typedef struct Node {
    int id;
    struct Node* next;  // 邻接节点指针
    bool visited;
} Node;

// 创建新节点
Node* createNode(int id) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->id = id;
    newNode->next = NULL;
    newNode->visited = false;
    return newNode;
}

// 添加边
void addEdge(Node** nodes, int from, int to) {
    Node* fromNode = findNode(nodes, from);
    Node* toNode = findNode(nodes, to);
    
    if(fromNode && toNode) {
        toNode->next = fromNode->next;
        fromNode->next = toNode;
    }
}

// 找到节点
Node* findNode(Node** nodes, int id) {
    for(Node* node = *nodes; node != NULL; node = node->next) {
        if(node->id == id)
            return node;
    }
    return NULL;
}

// 深度优先遍历
void dfs(Node** nodes, int start, void (*visit)(int)) {
    Node* current = findNode(nodes, start);
    if(current) {
        current->visited = true;
        visit(start);
        
        Node* temp = current->next;
        while(temp != NULL) {
            if(!temp->visited) {
                dfs(nodes, temp->id, visit);
            }
            temp = temp->next;
        }
    }
}

// 示例遍历函数，打印节点ID
void printVisit(int id) {
    printf("%d ", id);
}

int main() {
    int numNodes, numEdges; // 节点数和边数
    Node* nodes = NULL;

    // 初始化节点列表
    for(int i = 0; i < numNodes; ++i) {
        nodes = createNode(i);
        if(i > 0)
            nodes->next = nodes;
    }

    // 添加边（假设为无向图）
    for(int i = 0; i < numEdges; ++i) {
        int edgeFrom, edgeTo;
        // 从输入获取边的两端
        addEdge(&nodes, edgeFrom, edgeTo);
    }

    // 开始深度优先遍历
    dfs(&nodes, 0, printVisit);  // 从节点0开始

    return 0;
}

在这个例子中，我们首先创建了一个空的图，然后添加边并将所有节点连接成环形。`dfs`函数接收节点数组、起始节点和访问函数作为参数。在遍历时，我们会标记已访问过的节点，同时递归地探索未访问的相邻节点。