我正在尝试在 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
预期输出（来自我们的课堂活动）：
4 7 8 5 6 12 1 13 10 2 9 14 11 3 15 (Notice the difference!)
我的代码接受对输入并在应用拓扑排序后返回顺序。为简单起见，我假设该条目是拓扑排序的有效图。