拓扑排序c语言

拓扑排序是一种图论算法，用于将有向无环图（DAG）中的节点排序。以下是一个基于C语言的拓扑排序算法的示例代码：

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

#define MAX_VERTICES 100

typedef struct {
    int vertex;
    int weight;
    struct Node* next;
} Node;

Node* createNode(int vertex, int weight, Node* next) {
    Node* newNode = (Node*) malloc(sizeof(Node));
    newNode->vertex = vertex;
    newNode->weight = weight;
    newNode->next = next;
    return newNode;
}

Node* graph[MAX_VERTICES];
int visited[MAX_VERTICES];
int inDegree[MAX_VERTICES];

void addEdge(int source, int destination, int weight) {
    Node* newNode = createNode(destination, weight, graph[source]);
    graph[source] = newNode;
    inDegree[destination]++;
}

void topologicalSort(int vertices) {
    int i, vertex;
    Node* temp;
    int queue[MAX_VERTICES], front = 0, rear = -1;

    for (i = 0; i < vertices; i++) {
        visited[i] = 0;
        if (inDegree[i] == 0) {
            queue[++rear] = i;
        }
    }

    while (front <= rear) {
        vertex = queue[front++];
        printf("%d ", vertex);

        visited[vertex] = 1;
        for (temp = graph[vertex]; temp != NULL; temp = temp->next) {
            if (!visited[temp->vertex]) {
                inDegree[temp->vertex]--;
                if (inDegree[temp->vertex] == 0) {
                    queue[++rear] = temp->vertex;
                }
            }
        }
    }
}

int main() {
    int vertices, edges, i, source, destination, weight;

    printf("Enter the number of vertices: ");
    scanf("%d", &vertices);

    for (i = 0; i < vertices; i++) {
        graph[i] = NULL;
        inDegree[i] = 0;
    }

    printf("Enter the number of edges: ");
    scanf("%d", &edges);

    for (i = 0; i < edges; i++) {
        printf("Enter source, destination and weight of edge %d: ", i);
        scanf("%d%d%d", &source, &destination, &weight);
        addEdge(source, destination, weight);
    }

    printf("\nTopological sort: ");
    topologicalSort(vertices);

    return 0;
}

这个示例代码中，我们首先定义了一个Node结构体，用于表示有向图中的节点。然后，我们创建一个graph数组，用于存储有向图中的节点，以及一个visited数组和一个inDegree数组，分别用于标记节点是否被访问过以及每个节点的入度。接着，我们实现了一个createNode函数，用于创建新的节点。

在主函数中，我们首先读入有向图的顶点数和边数，然后使用addEdge函数添加边。最后，我们调用topologicalSort函数进行拓扑排序，并输出排序结果。

在topologicalSort函数中，我们首先将所有入度为0的节点加入队列中，然后从队列中取出一个节点并输出它。接着，我们遍历该节点的所有邻居节点，并将它们的入度减1。如果某个邻居节点的入度变为0，则将它加入队列中。重复以上步骤直到队列为空。