请你写一段拓扑排序的c++代码
时间: 2023-03-09 20:41:48 浏览: 115
我们可以使用深度优先搜索(DFS)算法来解决拓扑排序问题。下面是一个C语言实现的拓扑排序的DFS算法的代码示例:#include <stdio.h>
#include <stdlib.h>// 最大的顶点个数
#define MAXV 1000// 用于表示边的结构
struct edge{
int y; // 边的终点
int weight; // 权重
struct edge *next; // 下一条边
};// 图的结构
struct graph{
struct edge *edges[MAXV + 1]; // 边表头指针
int degree[MAXV + 1]; // 各顶点的度
int nvertices; // 顶点数
int nedges; // 边数
};// 初始化一个有向图
void initialize_graph(struct graph *g, int directed){
int i;
g->nvertices = 0;
g->nedges = 0;
for (i = 1; i <= MAXV; i++) {
g->degree[i] = 0;
g->edges[i] = NULL;
}
}// 插入一条边
void insert_edge(struct graph *g, int x, int y, int directed){
struct edge *p; // 临时指针 p = malloc(sizeof(struct edge)); // 分配空间
p->weight = 0;
p->y = y;
p->next = g->edges[x]; g->edges[x] = p; // 插入到边表头
g->degree[x]++; if (directed == 0)
insert_edge(g,y,x,1);
else
g->nedges++;
}// 拓扑排序的DFS
void topological_sort(struct graph *g, int visited[], int *sorted, int n){
int i;
struct edge *p; for (i = 1; i <= g->nvertices; i++) {
if (visited[i] == 0) {
p = g->edges[i];
while (p != NULL) {
topological_sort(g, visited, sorted, p->y);
p = p->next;
}
visited[i] = 1;
sorted[n--] = i;
}
}
}int main(){
int i;
struct graph g;
int visited[MAXV + 1];
int sorted[MAXV + 1]; initialize_graph(&g, 0);
insert_edge(&g, 1, 2, 0);
insert_edge(&g, 1, 3, 0);
insert_edge(&g, 2, 4, 0);
insert_edge(&g, 2, 5, 0);
insert_edge(&g, 3, 6, 0);
insert_edge(&g, 3, 7, 0);
insert_edge(&g, 4, 8, 0);
insert_edge(&g, 5, 8, 0); for (i = 1; i <= MAXV; i++)
visited[i] = 0; topological_sort(&g, visited, sorted, g.nvertices); for (i = 1; i <= g.nvertices; i++)
printf("%d ", sorted[i]); printf("\n"); return 0;
}