深度优先搜索c语言代码邻接表

深度优先搜索（Depth-First Search，DFS）是一种常用的图遍历算法，它从起点开始，尽可能深地探索分支，直到遇到某个节点无法继续，然后回溯到上一个节点，再尝试其他分支。在C语言中，我们可以使用邻接表（Adjacency List）数据结构来表示图，因为邻接表更适合存储稀疏图，即边的数量远小于顶点数的平方。

下面是一个简单的C语言代码示例，使用邻接表实现深度优先搜索：

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

// 图节点结构
typedef struct Node {
    int value;
    struct Node* next; // 邻接列表
} Node;

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

// 添加邻居
void addEdge(Node** head, int src, int dest) {
    Node* node = *head;
    while (node != NULL) {
        if (node->value == dest) break;
        node = node->next;
    }
    if (node == NULL) {
        node = createNode(dest);
        *head = node;
    } else {
        node->next = createNode(dest);
    }
}

// 深度优先搜索
void dfs(Node* start, int visited[], int n) {
    visited[start->value] = 1;
    printf("%d ", start->value);

    Node* temp = start->next;
    while (temp != NULL) {
        if (!visited[temp->value]) {
            dfs(temp, visited, n);
        }
        temp = temp->next;
    }
}

int main() {
    int V = 5; // 顶点数
    Node* adj[V]; // 初始化邻接表

    // 假设图的邻接矩阵如下：
    // 0 1 1 0 0
    // 1 0 0 1 1
    // 1 0 0 1 0
    // 0 1 1 0 1
    // 0 1 0 1 0

    // 根据实际的邻接矩阵添加边
    for (int i = 0; i < V; i++) {
        adj[i] = NULL;
    }

    // ... (添加具体的边)

    int startNode = 0; // 搜索起始节点
    int visited[V] = {0}; // 记录已访问过的节点

    printf("DFS starting from %d -> ", startNode);
    dfs(adj + startNode, visited, V);
    printf("\n");

    return 0;
}