温州网站,东营做网站seo的,上海房产网安居客,流控插件wordpress这段代码通过拓扑排序对有向无环图进行排序。它创建了一个图结构#xff0c;其中包含节点、邻接表和入度数组。然后#xff0c;通过输入添加了一些边#xff0c;创建了图的结构。接着#xff0c;使用拓扑排序算法对图进行排序#xff0c;并将排序后的结果打印输出。
首先…
这段代码通过拓扑排序对有向无环图进行排序。它创建了一个图结构其中包含节点、邻接表和入度数组。然后通过输入添加了一些边创建了图的结构。接着使用拓扑排序算法对图进行排序并将排序后的结果打印输出。
首先它定义了Node结构来表示图中的节点包含了节点值和指向下一个节点的指针。然后Graph结构表示整个图包含了邻接表、入度数组以及节点数量。
在createNode函数中它创建了一个新的节点并为其分配内存。createGraph函数用于创建一个图结构并初始化邻接表和入度数组。
addEdge函数用于在图中添加边。对于有向图中的每条边它在adjList中的源节点位置创建一个新节点并将其添加到邻接表的头部并且同时更新了目标节点的入度。
enqueue和dequeue函数是用于实现队列的基本操作用于在拓扑排序算法中管理节点的顺序。
topologicalSort函数实现了拓扑排序算法。首先它找到入度为0的节点并将其加入队列。接着它开始迭代处理队列中的节点将其邻接节点的入度减1并将入度减为0的邻接节点加入队列。这个过程一直持续到队列为空。如果最后排序的节点数和图的节点数不一致说明图中存在环路这种情况下会返回NULL。
在main函数中它接收用户的输入并创建图然后进行拓扑排序。最后根据排序结果输出结果。
这段代码执行过程中对节点编号进行了处理使得输出结果中的节点编号从1开始并按照拓扑排序的顺序输出。
#include stdio.h
#include stdlib.h#define MAX_NODES 200000struct 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开始存储因为节点是123...这样算的,
//而我想从012....
//输出的时候要加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;
}
