今天在学习python的多重继承时,无意看到了拓扑排序,于是就想着学习并整理下来
什么是拓扑排序
在图论中,拓扑排序(Topological Sorting) 是一个 有向无环图(DAG,Directed Acyclic Graph) 的所有顶点的线性序列。且该序列必须满足下面两个条件:
1. 每个顶点出现且只出现一次。
2. 若存在一条从顶点A到顶点B的路径,那么在序列中顶点A出现在顶点B的前面。
那么如何写出一个DAG拓扑的顺序图呢?
1. 从DAG途中选择一个没有前驱(即入度为0)的顶点并输出
2. 从图中删除该顶点和所有以它为起点的有向边。
3. 重复1和2直到当前DAG图为空或当前途中不存在无前驱的顶点为止。后一种情况说明有向图中必然存在环。
举例说明
class A(object):
def f(self):
print('A')
class B(object):
def f(self):
print('B')
class C(A,B):
pass
class D(A,B):
pass
class E(C,D):
pass
s= E()
s.f()
这样子的一段代码为什么最后输出的结果是A
呢?那么首先我们根据继承关系构成一个张拓扑图
其中最上面的O代表object
1. 找到入度为0的点,只有一个E,把E拿出来,把E相关的边剪掉
2. 现在有两个入度为0的点(C,D),取最左原则,拿C,剪掉C相关的边,这时候的排序是{E,C}
3. 现在我们看,入度为0的点(D),拿D,剪掉D相关的边,这时候排序是{E,C,D}
4. 接着看,入度为0的点(A,B),取最左原则,拿A,剪掉A相关的边,这时候的排序是{E,C,D,A}
5. 继续,入度为0的点只有B,拿B,剪掉B相关的边,最后只剩下object
6. 所以最后的排序是{E,C,D,A,B,object}
这样就知道最后代码执行的顺序是E,C,D,A,B,Object
我们通过打印出最后的结果,发现顺序确实如此。
A
(<class '__main__.E'>, <class '__main__.C'>, <class '__main__.D'>, <class '__main__.A'>, <class '__main__.B'>, <class 'object'>)
这就是多重继承用到的C3算法啦,是基于深度优先搜索算法的。
版权声明:本文为原创文章,版权归 heroyf 所有。
本文链接: https://heroyf.club/2019/04/python_c3/
Comments | 2 条评论
写的这么通俗易懂(滑稽脸)

哦,原来如此,我已经懂了(完全没懂.jpg)