c语言,采用队列完成拓扑排序算法的设计。
时间: 2024-03-10 13:48:39 浏览: 14
下面是 C 语言实现采用队列完成拓扑排序算法的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_NODE 100
int in_degree[MAX_NODE]; // 记录每个节点的入度
int queue[MAX_NODE]; // 队列
int front = -1, rear = -1; // 队列的头尾指针
// 图的邻接表表示
struct Node {
int data;
struct Node* next;
};
struct Graph {
int num_nodes; // 节点数
struct Node** adj_list; // 邻接表
};
// 创建节点
struct Node* create_node(int data) {
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
new_node->data = data;
new_node->next = NULL;
return new_node;
}
// 添加边
void add_edge(struct Graph* graph, int src, int dest) {
struct Node* new_node = create_node(dest);
new_node->next = graph->adj_list[src];
graph->adj_list[src] = new_node;
}
// 初始化入度为 0
void init_in_degree(int* in_degree, int num_nodes) {
for (int i = 0; i < num_nodes; i++) {
in_degree[i] = 0;
}
}
// 统计每个节点的入度
void count_in_degree(struct Graph* graph, int* in_degree) {
for (int i = 0; i < graph->num_nodes; i++) {
struct Node* temp = graph->adj_list[i];
while (temp != NULL) {
in_degree[temp->data]++;
temp = temp->next;
}
}
}
// 将节点加入队列
void enqueue(int* queue, int* rear, int node) {
queue[++(*rear)] = node;
}
// 从队列中取出节点
int dequeue(int* queue, int* front) {
return queue[++(*front)];
}
// 实现拓扑排序
void topological_sort(struct Graph* graph) {
int num_nodes = graph->num_nodes;
init_in_degree(in_degree, num_nodes); // 初始化入度为 0
count_in_degree(graph, in_degree); // 统计每个节点的入度
// 将所有入度为 0 的节点加入队列
for (int i = 0; i < num_nodes; i++) {
if (in_degree[i] == 0) {
enqueue(queue, &rear, i);
}
}
int count = 0; // 记录输出的节点数
while (front != rear) { // 队列非空
int node = dequeue(queue, &front); // 取出队首节点
printf("%d ", node);
count++;
// 将所有指向的节点的入度减 1,如果入度为 0,则加入队列
struct Node* temp = graph->adj_list[node];
while (temp != NULL) {
in_degree[temp->data]--;
if (in_degree[temp->data] == 0) {
enqueue(queue, &rear, temp->data);
}
temp = temp->next;
}
}
if (count != num_nodes) { // 输出的节点数小于节点总数,则说明存在环
printf("\n图中存在环\n");
}
}
int main() {
struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
graph->num_nodes = 6;
graph->adj_list = (struct Node**)malloc(graph->num_nodes * sizeof(struct Node*));
for (int i = 0; i < graph->num_nodes; i++) {
graph->adj_list[i] = NULL;
}
add_edge(graph, 0, 1);
add_edge(graph, 0, 2);
add_edge(graph, 1, 3);
add_edge(graph, 2, 3);
add_edge(graph, 2, 4);
add_edge(graph, 3, 5);
add_edge(graph, 4, 5);
printf("拓扑排序结果:");
topological_sort(graph);
return 0;
}
```
在上述代码中,我们定义了一个 `Graph` 结构体来表示有向图,其中包含节点数和邻接表。在 `add_edge` 函数中,我们使用链表来存储每个节点指向的节点。在 `topological_sort` 函数中,我们使用队列来记录入度为 0 的节点,并按照拓扑排序的规则输出节点。