c队列拓扑排序算法的设计
时间: 2023-12-13 08:00:58 浏览: 35
C语言中队列拓扑排序算法的设计可以分为以下几个步骤:
1. 定义一个结构体来存储图中的每个顶点,包括顶点的编号、入度数和邻接表等信息。
```
typedef struct vertex {
int id; // 顶点编号
int in_degree; // 顶点入度
struct edge* next; // 邻接表
} Vertex;
```
2. 构建图并初始化每个顶点的入度数和邻接表。
```
Vertex graph[N]; // N 为顶点数
// 初始化每个顶点的入度数和邻接表
for (int i = 0; i < N; i++) {
graph[i].id = i;
graph[i].in_degree = 0;
graph[i].next = NULL;
}
// 构建图
for (int i = 0; i < M; i++) { // M 为边数
int from, to; // from -> to
scanf("%d%d", &from, &to);
// 添加一条从 from 到 to 的边
struct edge* new_edge = (struct edge*)malloc(sizeof(struct edge));
new_edge->to = to;
new_edge->next = graph[from].next;
graph[from].next = new_edge;
graph[to].in_degree++; // 更新 to 的入度数
}
```
3. 将所有入度为 0 的顶点入队。
```
queue<int> q;
for (int i = 0; i < N; i++) {
if (graph[i].in_degree == 0) {
q.push(i);
}
}
```
4. 依次从队列中取出顶点并输出,同时更新与该顶点相邻的顶点的入度数。
```
while (!q.empty()) {
int cur = q.front();
q.pop();
printf("%d ", cur); // 输出顶点编号
// 更新与该顶点相邻的顶点的入度数
struct edge* p = graph[cur].next;
while (p != NULL) {
int next = p->to;
graph[next].in_degree--;
if (graph[next].in_degree == 0) {
q.push(next);
}
p = p->next;
}
}
```
5. 如果最终输出的顶点数量少于总顶点数,则说明存在环,拓扑排序失败。
完整代码如下:
```
#include <stdio.h>
#include <stdlib.h>
#include <queue>
using namespace std;
const int N = 10010;
// 邻接表
typedef struct edge {
int to; // 目标顶点编号
struct edge* next; // 下一条边
} Edge;
// 图中每个顶点的信息
typedef struct vertex {
int id; // 顶点编号
int in_degree; // 顶点入度
Edge* next; // 邻接表
} Vertex;
Vertex graph[N]; // 图
int n, m; // 顶点数和边数
// 拓扑排序
bool topological_sort() {
queue<int> q;
// 将所有入度为 0 的顶点入队
for (int i = 1; i <= n; i++) {
if (graph[i].in_degree == 0) {
q.push(i);
}
}
// 依次从队列中取出顶点并输出,同时更新与该顶点相邻的顶点的入度数
int cnt = 0; // 记录已经输出的顶点数
while (!q.empty()) {
int cur = q.front();
q.pop();
cnt++;
// 输出顶点编号
if (cnt == n) {
printf("%d\n", cur);
} else {
printf("%d ", cur);
}
// 更新与该顶点相邻的顶点的入度数
Edge* p = graph[cur].next;
while (p != NULL) {
int next = p->to;
graph[next].in_degree--;
if (graph[next].in_degree == 0) {
q.push(next);
}
p = p->next;
}
}
// 如果最终输出的顶点数量少于总顶点数,则说明存在环,拓扑排序失败
return cnt == n;
}
int main() {
// 读入顶点数和边数
scanf("%d%d", &n, &m);
// 初始化每个顶点的入度数和邻接表
for (int i = 1; i <= n; i++) {
graph[i].id = i;
graph[i].in_degree = 0;
graph[i].next = NULL;
}
// 构建图
for (int i = 0; i < m; i++) {
int from, to;
scanf("%d%d", &from, &to);
// 添加一条从 from 到 to 的边
Edge* new_edge = (Edge*)malloc(sizeof(Edge));
new_edge->to = to;
new_edge->next = graph[from].next;
graph[from].next = new_edge;
graph[to].in_degree++; // 更新 to 的入度数
}
// 拓扑排序
if (!topological_sort()) {
printf("图中存在环\n");
}
return 0;
}
```