拓扑排序c++代码（拓扑排序算法及c语言实现）

拓扑排序是一种常用的图算法，它用于对有向无环图（DAG）进行排序。在拓扑排序中，所有的顶点会按照一定的顺序进行排序，使得图中的所有有向边都从低序顶点指向高序顶点。在实际应用中，拓扑排序可以用于解决任务调度、依赖关系管理和编译器优化等问题。

下面我们将给出一个使用C语言实现的拓扑排序代码，来帮助读者更好地理解该算法的实现过程。代码如下：

```c

#include

#define MAX_SIZE 100

// 邻接矩阵表示的有向图

int graph[MAX_SIZE][MAX_SIZE];

int visited[MAX_SIZE];

int res[MAX_SIZE];

int index = 0;

// 拓扑排序

void topologicalSort(int n) {

int i, j;

int flag;

// 遍历所有的顶点

for(i = 0; i < n; i++) {

// 如果顶点未访问过

if(!visited[i]) {

flag = 0;

// 遍历所有的邻接顶点

for(j = 0; j < n; j++) {

// 如果该邻接顶点存在有向边

if(graph[j][i]) {

flag = 1;

break;

}

}

// 如果不存在有向边，则进行访问

if(!flag) {

visited[i] = 1;

res[index++] = i;

// 移除顶点的所有出边

for(j = 0; j < n; j++) {

graph[i][j] = 0;

}

// 递归处理该顶点的邻接顶点

topologicalSort(n);

// 递归处理完之后，返回上一层

index--;

visited[i] = 0;

// 恢复顶点的所有出边

for(j = 0; j < n; j++) {

graph[i][j] = 1;

}

}

}

}

int main() {

int n, i, j;

// 输入顶点个数

printf("请输入顶点个数：");

scanf("%d", &n);

// 输入有向图的邻接矩阵

printf("请输入有向图的邻接矩阵：\n");

for(i = 0; i < n; i++) {

for(j = 0; j < n; j++) {

scanf("%d", &graph[i][j]);

}

}

// 执行拓扑排序

topologicalSort(n);

// 输出拓扑排序的结果

printf("拓扑排序的结果为：");

for(i = 0; i < n; i++) {

printf("%d ", res[i]);

}

return 0;

```

在这段代码中，我们首先定义了一个大小为100的二维数组`graph`，用来表示有向图的邻接矩阵。接下来，我们定义了一个一维数组`visited`，用来记录顶点的访问状态。另外，我们还定义了一个一维数组`res`，用来存储拓扑排序的结果，以及一个变量`index`，用来记录已经拓扑排序的元素个数。

在`topologicalSort`函数中，我们首先对所有的顶点进行遍历，如果顶点未访问过，则进行以下操作。我们通过遍历所有的邻接顶点，来判断该顶点是否存在有向边。如果不存在有向边，则进行访问，并将该顶点添加到结果数组`res`中。然后，我们移除该顶点的所有出边，并递归调用`topologicalSort`函数处理该顶点的邻接顶点。递归处理之后，我们需要返回上一层，并恢复顶点的所有出边。

在`main`函数中，我们首先输入顶点的个数和有向图的邻接矩阵。之后，我们调用`topologicalSort`函数执行拓扑排序，并输出排序结果。

这段代码实现了一个基本的拓扑排序算法，读者可以根据自己的需求进行二次开发和优化。希望本文能够对读者理解拓扑排序算法的实现过程有所帮助。