拓扑排序笔记

发布时间:2023年12月28日

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

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

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

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

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

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;
}

文章来源:https://blog.csdn.net/weixin_62281810/article/details/135278098
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。