拓扑排序笔记

这段代码通过拓扑排序对有向无环图进行排序。它创建了一个图结构，其中包含节点、邻接表和入度数组。然后，通过输入添加了一些边，创建了图的结构。接着，使用拓扑排序算法对图进行排序，并将排序后的结果打印输出。

首先，它定义了Node结构来表示图中的节点，包含了节点值和指向下一个节点的指针。然后，Graph结构表示整个图，包含了邻接表、入度数组以及节点数量。

在createNode函数中，它创建了一个新的节点，并为其分配内存。createGraph函数用于创建一个图结构，并初始化邻接表和入度数组。

addEdge函数用于在图中添加边。对于有向图中的每条边，它在adjList中的源节点位置创建一个新节点，并将其添加到邻接表的头部，并且同时更新了目标节点的入度。

enqueue和dequeue函数是用于实现队列的基本操作，用于在拓扑排序算法中管理节点的顺序。

topologicalSort函数实现了拓扑排序算法。首先，它找到入度为0的节点，并将其加入队列。接着，它开始迭代处理队列中的节点，将其邻接节点的入度减1，并将入度减为0的邻接节点加入队列。这个过程一直持续到队列为空。如果最后排序的节点数和图的节点数不一致，说明图中存在环路，这种情况下会返回NULL。

在main函数中，它接收用户的输入并创建图，然后进行拓扑排序。最后，根据排序结果输出结果。

这段代码执行过程中，对节点编号进行了处理，使得输出结果中的节点编号从1开始，并按照拓扑排序的顺序输出。

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

#define MAX_NODES 200000

struct Node {
    int value;
    struct Node* next;
};

struct Graph {
    struct Node* adjList[MAX_NODES];
    int inDegree[MAX_NODES];
    int numNodes;
};

struct Node* createNode(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->value = value;
    newNode->next = NULL;
    return newNode;
}

struct Graph* createGraph(int numNodes) {
    struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
    graph->numNodes = numNodes;

    for (int i = 0; i < numNodes; ++i) {
        graph->adjList[i] = NULL;
        graph->inDegree[i] = 0;
    }

    return graph;
}

void addEdge(struct Graph* graph, int src, int dest) {
    struct Node* newNode = createNode(dest);
//让目标那条边直接成为graph->adjList[src]。这样一来每个graph->adjList[src]就会是指向的边
//当时候入度为0的节点跳出时，就可以 int adjNode = temp->value; graph->inDegree[adjNode]--;
//直接让graph->adjList[src]指向的入度减一并遍历，就很简单了
    newNode->next = graph->adjList[src];
    graph->adjList[src] = newNode;
//这里要注意，dest是被指向的边，所以它的入度要加一
    graph->inDegree[dest]++;
}

void enqueue(int queue[], int* rear, int node) {
    queue[(*rear)++] = node;
}

int dequeue(int queue[], int* front) {
    return queue[(*front)++];
}

int* topologicalSort(struct Graph* graph) {
    int* result = (int*)malloc(graph->numNodes * sizeof(int));
    int front = 0, rear = 0;
    int queue[MAX_NODES];
    int idx = 0;

    for (int i = 0; i < graph->numNodes; ++i) {
        if (graph->inDegree[i] == 0) {
            enqueue(queue, &rear, i);
        }
    }

    while (front != rear) {
        int currentNode = dequeue(queue, &front);
        result[idx++] = currentNode;

        struct Node* temp = graph->adjList[currentNode];
        while (temp != NULL) {
            int adjNode = temp->value;
            graph->inDegree[adjNode]--;
            if (graph->inDegree[adjNode] == 0) {
                enqueue(queue, &rear, adjNode);
            }
            temp = temp->next;
        }
    }

    if (idx != graph->numNodes) {
        free(result);
        return NULL; // Graph contains cycle
    }

    return result;
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);

    struct Graph* graph = createGraph(n);

    for (int i = 0; i < m; ++i) {
        int u, v;
        scanf("%d %d", &u, &v);
//这里u - 1, v - 1其实是为了满足数组从索引0开始存储，因为节点是1，2，3...这样算的,
//而我想从0，1，2....
//输出的时候要加1回来
        addEdge(graph, u - 1, v - 1);
    }

    int* result = topologicalSort(graph);
    if (result == NULL) {
        printf("-1\n");
    } else {
        for (int i = 0; i < n; ++i) {
            if (i == n - 1) {
                printf("%d", result[i] + 1);//加1回来
            } else {
                printf("%d ", result[i] + 1);
            }
        }
        free(result);
    }

    return 0;
}