python - 如何对相互链接的元组列表进行排序？

Question

lst = [(u'course', u'session'), (u'instructor', u'session'), (u'session', u'trainee'), (u'person', u'trainee'), (u'person', u'instructor'), (u'course', u'instructor')]

我上面有元组列表，我需要按照以下逻辑对其进行排序....每个元组的第二个元素依赖于第一个元素，例如(course, session) -> session 依赖于类(class)等等..

我想要一个基于依赖优先级的排序列表，较少或独立的对象将排在第一位，因此输出应该如下所示，

lst = [course, person, instructor, session, trainee]

Answer 1

您正在寻找所谓的 topological sort .维基百科页面展示了经典的 Kahn 和深度优先搜索算法； Python 示例是 here (有点过时，但应该仍然可以正常运行)，在 pypi 上(稳定且可重用——您也可以在线阅读代码 here )和 here (Tarjan 的算法，这种算法也处理指定依赖项中的循环)，仅举几例。