用c语言写一个完整的用邻接表存储的拓扑排序并作出详细步骤说明

在C语言中，我们可以使用邻接表（Adjacency List）来表示图，并通过深度优先搜索（Depth-First Search，DFS）算法实现拓扑排序。以下是编写一个简单的拓扑排序过程：

首先，我们需要定义结构体来表示节点（顶点）和边（边表），以及邻接表的数据结构。

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

// 定义节点结构体
typedef struct Node {
    int val;       // 节点值
    struct Node* next; // 邻接表指针
} Node;

// 定义邻接表结构体
typedef struct AdjList {
    Node* nodes; // 存储所有节点的链表头
    int size;    // 图中节点数
} AdjList;

接下来，创建邻接表并插入节点：

void add_edge(AdjList* graph, int src, int dest) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->val = dest;
    newNode->next = graph->nodes;
    graph->nodes = newNode;
    graph->size++;
}

// 初始化邻接表
void init_graph(AdjList* graph, int num_nodes) {
    graph->nodes = NULL;
    graph->size = 0;
    for (int i = 0; i < num_nodes; ++i) {
        Node* newNode = (Node*)malloc(sizeof(Node));
        newNode->val = i;
        newNode->next = NULL;
        graph->nodes = newNode;
    }
}

然后实现拓扑排序的核心部分 - 深度优先搜索：

bool visit(Node* node, bool* visited, AdjList* graph) {
    if (node == NULL)
        return true;

    *visited[node->val] = true;
    Node* nextNode = node->next;
    while (nextNode != NULL) {
        if (!(*visited)[nextNode->val]) {
            if (!visit(nextNode, visited, graph))
                return false;
        }
        nextNode = nextNode->next;
    }
    return true;
}

// 拓扑排序函数
void topological_sort(AdjList* graph) {
    int num_nodes = graph->size;
    bool* visited = (bool*)malloc(sizeof(bool) * num_nodes);
    for (int i = 0; i < num_nodes; i++)
        visited[i] = false;

    for (int i = 0; i < num_nodes && !visit(graph->nodes, visited, graph); i++) {
        printf("%d ", i);
    }

    free(visited);
}

最后，在主程序中测试以上函数：

int main() {
    AdjList graph;
    init_graph(&graph, 5); // 假设有5个节点
    // 添加边...（例如，add_edge(&graph, 0, 1); add_edge(&graph, 1, 2);等）

    topological_sort(&graph);

    return 0;
}