你如何在 C 中实现 Knuth 的 Toposort？
How do you implement Knuth's Toposort in C?
我正在尝试用 C 实现 Knuth 的拓扑排序算法。当我搜索在线资源时，我看到的都是 Kahn 算法的实现，这让我很困惑。它们是一样的吗？或者它们有什么不同？这是我根据研究得出的实现。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX 1000
void create_graph();
void add(int vertex);
int del();
int isEmpty();
int find_indegree_of_vertex(int vertex);
int total_vertices;
int adjacent_matrix[MAX][MAX];
int queue[MAX];
int front = -1;
int rear = -1;
int main()
{
int i, vertex, count, topological_sort[MAX], indegree[MAX];
create_graph();
for(i = 1; i <= total_vertices; i++)
{
indegree[i] = find_indegree_of_vertex(i);
if(indegree[i] == 0)
{
add(i);
}
}
count = 0;
while(!isEmpty() && count < total_vertices)
{
vertex = del();
topological_sort[++count] = vertex;
for(i = 1; i <= total_vertices; i++)
{
if(adjacent_matrix[vertex][i] == 1)
{
adjacent_matrix[vertex][i] = 0;
indegree[i] = indegree[i] - 1;
if(indegree[i] == 0)
{
add(i);
}
}
}
}
for(i = 1; i <= count; i++)
{
printf("%d ", topological_sort[i]);
}
printf("\n");
return 0;
}
void add(int vertex)
{
if(!(rear == MAX - 1))
{
if(front == -1)
{
front = 0;
}
rear = rear + 1;
queue[rear] = vertex ;
}
}
int isEmpty()
{
if(front == -1 || front > rear)
{
return 1;
}
else
{
return 0;
}
}
int del()
{
int element;
if(front == -1 || front > rear)
{
exit(1);
}
else
{
element = queue[front];
front = front + 1;
return element;
}
}
int find_indegree_of_vertex(int vertex)
{
int count, total_indegree = 0;
for(count = 0; count < total_vertices; count++)
{
if(adjacent_matrix[count][vertex] == 1)
{
total_indegree++;
}
}
return total_indegree;
}
void create_graph()
{
int count, maximum_edges, origin_vertex, destination_vertex;
char v1[1000], v2[1000];
char temp[10];
scanf("%d\n", &total_vertices);
maximum_edges = total_vertices * (total_vertices - 1);
for(count = 1; count <= maximum_edges; count++)
{
fgets(temp, sizeof(temp), stdin);;
char * splitter;
splitter = strtok(temp, " ");
strncpy(v1, splitter, strlen(splitter)+1);
splitter = strtok(NULL, " ");
strncpy(v2, splitter, strlen(splitter)+1);
origin_vertex = atoi(v1);
destination_vertex = atoi(v2);
if((origin_vertex == 0) && (destination_vertex == 0))
{
break;
}
else
adjacent_matrix[origin_vertex][destination_vertex] = 1;
}
}
示例输入：
15 (Number of vertices)
1 2
2 3
4 5
5 1
5 12
5 6
7 6
8 9
10 11
12 10
12 13
13 14
13 9
14 15
0 0 (End of entries, not a part of the adjacency matrix.)
输出：
4 7 8 5 1 6 12 2 10 13 3 11 9 14 15
预期输出（来自我们的 class activity）：
4 7 8 5 6 12 1 13 10 2 9 14 11 3 15 (Notice the difference!)
我的代码接受成对输入和 returns 应用拓扑排序后的顺序。为简单起见，我假设该条目是拓扑排序的有效图。
如果您阅读 Knuth 的 TAOCP（计算机编程艺术）第 1 卷第 3 版第 2.2.3 节，您会找到 Knuth 的“算法 T（拓扑排序）”以及评论：
A topological sorting technique similar to Algorithm T (but without the important feature of the queue links) was first published by A. B. Kahn, CACM 5 (1962), 558-562.
这表明Knuth的算法T与Kahn的算法不同。
可以这样实现：
#include <stdio.h>
#define MAX 200
int n,adj[MAX][MAX];
int front = -1,rear = -1,queue[MAX];
void main() {
int i,j = 0,k;
int topsort[MAX],indeg[MAX];
create_graph();
print("The adjacency matrix is:\n");
display();
for (i=1;i<+n;i++) {
indeg[i]=indegree(i);
if(indeg[i]==0)
insert_queue(i);
}
while(front<=rear) {
k=delete_queue();
topsort[j++]=k;
for (i=1;i<=n;i++) {
if(adj[k][i]==1) {
adj[k][i]=0;
indeg[i]=indeg[i]-1;
if(indeg[i]==0)
insert_queue(i);
}
}
}
printf("Nodes after topological sorting are:\n");
for (i=0;i<=n;i++)
{
printf("%d",topsort[i]);
printf("\n");
}
}
create_graph()
{
int i,max_edges,origin,destin;
printf("\n Enter number of vertices:");
scanf("%d",&n);
max_edges = n * (n - 1);
for (i = 1; i <= max_edges; i++)
{
printf("\n Enter edge %d (00 to quit):",i);
scanf("%d%d",&origin,&destin);
if ((origin == 0) && (destin == 0)) {
printf("Invalid edge!!\n");
i–;
}
else
adj[origin][destin] = 1;
}
return;
}
display()
{
int i,j;
for (i = 0;i <= n;i++) {
for (j = 1;jrear) {
printf("Queue Underflow");
return;
} else {
del_item = queue[front];
front = front + 1;
return del_item;
}
}
}
int indegree(int node) {
int i,in_deg = 0;
for (i = 1;i <= n;i++)
if(adj[i][node] == 1)
in_deg++;
return in_deg;
}
我认为问题在于 Knuth 的拓扑排序算法有多个版本。 1968 年发表的第一个与 Kahn 算法（1962 年发表）相同。
Donald Knuth 于 1964 年发表了一种为拓扑排序生成 all 可能解的算法（它使用双端队列 D，它
充当排序的计数器数组）。
http://www.cs.iit.edu/~cs560/fall_2012/Research_Paper_Topological_sorting/Topological%20sorting.pdf
TAOCP 提供了 Knuth 拓扑排序算法的 C 实现 https://github.com/theartofcomputerprogramming/programs/blob/main/vol_1_fundamental_algorithms_chap_2_information_structures/sec_2.2.3_linked_allocation/algorithm_t_topological_sort.c
C代码注释了2.2.3 TAOCP的链接分配算法T（拓扑排序）的每一步
Knuth 的算法非常快速和紧凑，因为队列链接将其与 Kahn 的算法区分开来。 C 代码包含对队列如何在文件顶部工作的解释。
值得注意的是，Knuth 很早就在 TAOCP 的第 1 卷中介绍了该算法，远早于后续卷中涵盖树或图。
该程序采用二进制输入并输出二进制数据，以与 TAOCP 的 MMIX 补充附录的 2.2.3 链接分配部分中的程序 T（拓扑排序）兼容。它可以被认为是 MMIX 实现的一个端口，可用于查看 Knuth 算法的预期输出。
data 子目录中有用于测试的示例二进制数据以及要检查的文本表示 - 我已将问题示例中的数据添加到 in.2.le.dat（来源 in.2.txt)
可以在 repo 中使用此工具生成二进制数据 - https://github.com/theartofcomputerprogramming/programs/blob/main/tools/texttobinary.sh
我用 gcc 11.2 和 vc++ 2022 版本 17.1
测试了程序
关于在 Windows 上构建的警告 - 使用外部构建目录，因为 repo 中的源路径很长并且打破了 cmake 路径限制 - cmake 配置可能会失败并出现关于 [=16 的神秘错误=] 和 No CMAKE_CXX_COMPILER could be found
以下是如何在 little-endian 系统（如 x64
）上 运行 程序
$ algorithm_t_topological_sort -h
usage: algorithm_t_topological_sort <in.dat >out.dat
Implements Algorithm T (Topological sort) from 2.2.3 Linked Allocation, The Art of Computer Programming Volume 1, Fundamental Algorithms by Donald Knuth
Input and output is binary compatible with Program T (Topological sort) from 2.2.3 Linked Allocation, The MMIX Supplement by Martin Ruckert
Reads sequence of pairs of binary uint32_t values on stdin
Each pair is a dependency relation between objects
First of each pair is predecessor, second is successor
First pair is special: first value is 0, second is objects count
Last pair is special: both values are 0
Output on stdout is binary uint32_t values in topologically sorted order
Examples:
algorithm_t_topological_sort <in.0.le.dat | od -An -td4 -w4 -v
$ cat in.2.le.dat | od -An -td4 -w4 -v | paste -d ' ' - - | tr -s ' ' | sed 's/ //'
0 15
1 2
2 3
4 5
5 1
5 12
5 6
7 6
8 9
10 11
12 10
12 13
13 14
13 9
14 15
0 0
结果的排序顺序与问题和评论中看到的排序顺序不同 - 注意 Linux 上的 tsort 也实现了 Knuth 的算法
$ algorithm_t_topological_sort <in.2.le.dat | od -An -td4 -w4 -v | tr -s '\n' ' ' | sed 's/ //'
8 7 4 5 6 12 1 13 10 2 9 14 11 3 15 0
我正在尝试用 C 实现 Knuth 的拓扑排序算法。当我搜索在线资源时，我看到的都是 Kahn 算法的实现，这让我很困惑。它们是一样的吗？或者它们有什么不同？这是我根据研究得出的实现。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX 1000
void create_graph();
void add(int vertex);
int del();
int isEmpty();
int find_indegree_of_vertex(int vertex);
int total_vertices;
int adjacent_matrix[MAX][MAX];
int queue[MAX];
int front = -1;
int rear = -1;
int main()
{
int i, vertex, count, topological_sort[MAX], indegree[MAX];
create_graph();
for(i = 1; i <= total_vertices; i++)
{
indegree[i] = find_indegree_of_vertex(i);
if(indegree[i] == 0)
{
add(i);
}
}
count = 0;
while(!isEmpty() && count < total_vertices)
{
vertex = del();
topological_sort[++count] = vertex;
for(i = 1; i <= total_vertices; i++)
{
if(adjacent_matrix[vertex][i] == 1)
{
adjacent_matrix[vertex][i] = 0;
indegree[i] = indegree[i] - 1;
if(indegree[i] == 0)
{
add(i);
}
}
}
}
for(i = 1; i <= count; i++)
{
printf("%d ", topological_sort[i]);
}
printf("\n");
return 0;
}
void add(int vertex)
{
if(!(rear == MAX - 1))
{
if(front == -1)
{
front = 0;
}
rear = rear + 1;
queue[rear] = vertex ;
}
}
int isEmpty()
{
if(front == -1 || front > rear)
{
return 1;
}
else
{
return 0;
}
}
int del()
{
int element;
if(front == -1 || front > rear)
{
exit(1);
}
else
{
element = queue[front];
front = front + 1;
return element;
}
}
int find_indegree_of_vertex(int vertex)
{
int count, total_indegree = 0;
for(count = 0; count < total_vertices; count++)
{
if(adjacent_matrix[count][vertex] == 1)
{
total_indegree++;
}
}
return total_indegree;
}
void create_graph()
{
int count, maximum_edges, origin_vertex, destination_vertex;
char v1[1000], v2[1000];
char temp[10];
scanf("%d\n", &total_vertices);
maximum_edges = total_vertices * (total_vertices - 1);
for(count = 1; count <= maximum_edges; count++)
{
fgets(temp, sizeof(temp), stdin);;
char * splitter;
splitter = strtok(temp, " ");
strncpy(v1, splitter, strlen(splitter)+1);
splitter = strtok(NULL, " ");
strncpy(v2, splitter, strlen(splitter)+1);
origin_vertex = atoi(v1);
destination_vertex = atoi(v2);
if((origin_vertex == 0) && (destination_vertex == 0))
{
break;
}
else
adjacent_matrix[origin_vertex][destination_vertex] = 1;
}
}
示例输入：
15 (Number of vertices)
1 2
2 3
4 5
5 1
5 12
5 6
7 6
8 9
10 11
12 10
12 13
13 14
13 9
14 15
0 0 (End of entries, not a part of the adjacency matrix.)
输出：
4 7 8 5 1 6 12 2 10 13 3 11 9 14 15
预期输出（来自我们的 class activity）：
4 7 8 5 6 12 1 13 10 2 9 14 11 3 15 (Notice the difference!)
我的代码接受成对输入和 returns 应用拓扑排序后的顺序。为简单起见，我假设该条目是拓扑排序的有效图。
如果您阅读 Knuth 的 TAOCP（计算机编程艺术）第 1 卷第 3 版第 2.2.3 节，您会找到 Knuth 的“算法 T（拓扑排序）”以及评论：
A topological sorting technique similar to Algorithm T (but without the important feature of the queue links) was first published by A. B. Kahn, CACM 5 (1962), 558-562.
这表明Knuth的算法T与Kahn的算法不同。
可以这样实现：
#include <stdio.h>
#define MAX 200
int n,adj[MAX][MAX];
int front = -1,rear = -1,queue[MAX];
void main() {
int i,j = 0,k;
int topsort[MAX],indeg[MAX];
create_graph();
print("The adjacency matrix is:\n");
display();
for (i=1;i<+n;i++) {
indeg[i]=indegree(i);
if(indeg[i]==0)
insert_queue(i);
}
while(front<=rear) {
k=delete_queue();
topsort[j++]=k;
for (i=1;i<=n;i++) {
if(adj[k][i]==1) {
adj[k][i]=0;
indeg[i]=indeg[i]-1;
if(indeg[i]==0)
insert_queue(i);
}
}
}
printf("Nodes after topological sorting are:\n");
for (i=0;i<=n;i++)
{
printf("%d",topsort[i]);
printf("\n");
}
}
create_graph()
{
int i,max_edges,origin,destin;
printf("\n Enter number of vertices:");
scanf("%d",&n);
max_edges = n * (n - 1);
for (i = 1; i <= max_edges; i++)
{
printf("\n Enter edge %d (00 to quit):",i);
scanf("%d%d",&origin,&destin);
if ((origin == 0) && (destin == 0)) {
printf("Invalid edge!!\n");
i–;
}
else
adj[origin][destin] = 1;
}
return;
}
display()
{
int i,j;
for (i = 0;i <= n;i++) {
for (j = 1;jrear) {
printf("Queue Underflow");
return;
} else {
del_item = queue[front];
front = front + 1;
return del_item;
}
}
}
int indegree(int node) {
int i,in_deg = 0;
for (i = 1;i <= n;i++)
if(adj[i][node] == 1)
in_deg++;
return in_deg;
}
我认为问题在于 Knuth 的拓扑排序算法有多个版本。 1968 年发表的第一个与 Kahn 算法（1962 年发表）相同。 Donald Knuth 于 1964 年发表了一种为拓扑排序生成 all 可能解的算法（它使用双端队列 D，它 充当排序的计数器数组）。
http://www.cs.iit.edu/~cs560/fall_2012/Research_Paper_Topological_sorting/Topological%20sorting.pdf
TAOCP 提供了 Knuth 拓扑排序算法的 C 实现 https://github.com/theartofcomputerprogramming/programs/blob/main/vol_1_fundamental_algorithms_chap_2_information_structures/sec_2.2.3_linked_allocation/algorithm_t_topological_sort.c
C代码注释了2.2.3 TAOCP的链接分配算法T（拓扑排序）的每一步
Knuth 的算法非常快速和紧凑，因为队列链接将其与 Kahn 的算法区分开来。 C 代码包含对队列如何在文件顶部工作的解释。
值得注意的是，Knuth 很早就在 TAOCP 的第 1 卷中介绍了该算法，远早于后续卷中涵盖树或图。
该程序采用二进制输入并输出二进制数据，以与 TAOCP 的 MMIX 补充附录的 2.2.3 链接分配部分中的程序 T（拓扑排序）兼容。它可以被认为是 MMIX 实现的一个端口，可用于查看 Knuth 算法的预期输出。
data 子目录中有用于测试的示例二进制数据以及要检查的文本表示 - 我已将问题示例中的数据添加到 in.2.le.dat（来源 in.2.txt)
可以在 repo 中使用此工具生成二进制数据 - https://github.com/theartofcomputerprogramming/programs/blob/main/tools/texttobinary.sh
我用 gcc 11.2 和 vc++ 2022 版本 17.1
测试了程序关于在 Windows 上构建的警告 - 使用外部构建目录，因为 repo 中的源路径很长并且打破了 cmake 路径限制 - cmake 配置可能会失败并出现关于 [=16 的神秘错误=] 和 No CMAKE_CXX_COMPILER could be found
以下是如何在 little-endian 系统（如 x64
）上 运行 程序$ algorithm_t_topological_sort -h
usage: algorithm_t_topological_sort <in.dat >out.dat
Implements Algorithm T (Topological sort) from 2.2.3 Linked Allocation, The Art of Computer Programming Volume 1, Fundamental Algorithms by Donald Knuth
Input and output is binary compatible with Program T (Topological sort) from 2.2.3 Linked Allocation, The MMIX Supplement by Martin Ruckert
Reads sequence of pairs of binary uint32_t values on stdin
Each pair is a dependency relation between objects
First of each pair is predecessor, second is successor
First pair is special: first value is 0, second is objects count
Last pair is special: both values are 0
Output on stdout is binary uint32_t values in topologically sorted order
Examples:
algorithm_t_topological_sort <in.0.le.dat | od -An -td4 -w4 -v
$ cat in.2.le.dat | od -An -td4 -w4 -v | paste -d ' ' - - | tr -s ' ' | sed 's/ //'
0 15
1 2
2 3
4 5
5 1
5 12
5 6
7 6
8 9
10 11
12 10
12 13
13 14
13 9
14 15
0 0
结果的排序顺序与问题和评论中看到的排序顺序不同 - 注意 Linux 上的 tsort 也实现了 Knuth 的算法
$ algorithm_t_topological_sort <in.2.le.dat | od -An -td4 -w4 -v | tr -s '\n' ' ' | sed 's/ //'
8 7 4 5 6 12 1 13 10 2 9 14 11 3 15 0