使用c中的链接列表排序

我看到这个实现有几个问题.一些与C相关,其他与算法有关,所以让我一次一个地浏览它们.

问题定义.
Topological sort确实被定义为有向图中元素的优先级.但是,仅这句话并没有完全定义问题.具体来说,拓扑排序是以指定源顶点开始的图元素的优先级.举个例子,假设您有以下有向图：

a -> b
b -> c
c -> a

如果从顶点a开始,拓扑排序应为{a,b,c}.如果从顶点c开始,则拓扑顺序应为{c,a,b}.因此,没有源顶点,问题定义就毫无意义.这种顶点的一个选择可能是图形的一些顶点,它没有指向它的边缘,即每个入射边缘都是一个输出边缘.

要记住的另一件事是图connectedness.并不总是可以从任何其他顶点到达任何顶点.所以在实现这样的算法时要记住这一点.

良好的数据结构是良好算法的关键.
如果要在有向图中对事物进行排序,最好的办法是创建有向图数据结构,该结构本身将涉及创建节点数据结构和边数据结构.我建议查找adjacency lists.一旦你有了这样的数据结构,就可以在图表上运行breadth first search了,你的拓扑优先性就是一个很好的结果.

实现邻接列表时,您仍需要将所有元素存储在一个位置.链表通常不是最好的方法,因为它需要一个时间来插入一个(假设对数据进行排序),需要线性时间来搜索一个.那是不理想的.正如@ David RF所建议的那样,Red-Black trees和AVL trees将是最佳选择.但是,我不会从这个优化开始.只要您拥有完善的工作算法,就可以随时改进存储数据结构.毕竟,链接列表和搜索树的界面是相同的.

考虑到您使用正确的算法,算法可以很快.
我没有在实践中处理拓扑问题,所以我不知道每一个错综复杂和每一个边缘情况.但！如果使用常规节点边缘数据结构进行广度优先搜索(请注意边缘可以在节点内隐式定义),则搜索本身应使用广度优先搜索来获取线性时间.

我已经阅读了你的算法,我不得不承认我并没有完全掌握你的大名单和小名单的概念.模棱两可的名字并没有真正帮助.也许它可以通过一个隐藏在某个地方的小小虫来完成工作,但它不太可读.也许其他人可以评论您当前的实施.