python 多重繼承之拓撲排序

python 多重繼承之拓撲排序 一、什麼是拓撲排序

在圖論中，拓撲排序(Topological Sorting) 是一個 有向無環圖(DAG,Directed Acyclic Graph) 的所有頂點的線性序列。且該序列必須滿足下面兩個條件：

  1. 每個頂點出現且只出現一次。
  2. 若存在一條從頂點A到頂點B的路徑，那麼在序列中頂點A出現在頂點B的前面。 例如，下面這個圖：

它是一個DAG圖，那麼如何寫出它的拓撲順序呢？這裡說一種比較常用的方法：

  • 從DAG途中選擇一個沒有前驅(即入度為0)的頂點並輸出
  • 從圖中刪除該頂點和所有以它為起點的有向邊。
  • 重複1和2直到當前DAG圖為空或當前途中不存在無前驅的頂點為止。後一種情況說明有向圖中必然存在環。

於是，得到拓撲排序後的結果是{1,2,4,3,5}

下面，我們看看拓撲排序在python多重繼承中的例子

二、python 多重繼承

 #!/usr/bin/env python3  # -*- coding: utf-8 -*-  class A(object):      def foo(self):          print('A foo')      def bar(self):          print('A bar')    class B(object):      def foo(self):          print('B foo')      def bar(self):          print('B bar')    class C1(A,B):      pass    class C2(A,B):      def bar(self):          print('C2-bar')    class D(C1,C2):      pass    if __name__ == '__main__':      print(D.__mro__)      d=D()      d.foo()      d.bar()

運行結果：

(<class '__main__.D'>, <class '__main__.C1'>, <class '__main__.C2'>, <class '__main__.A'>, <class '__main__.B'>, <class 'object'>)  A foo  C2-bar

首先，我們根據上面的繼承關係構成一張圖，如下

  • 找到入度為0的點，只有一個D，把D拿出來，把D相關的邊剪掉
  • 現在有兩個入度為0的點(C1,C2)，取最左原則，拿C1，剪掉C1相關的邊，這時候的排序是{D,C1}
  • 現在我們看，入度為0的點(C2),拿C2,剪掉C2相關的邊，這時候排序是{D,C1,C2}
  • 接著看，入度為0的點(A,B),取最左原則，拿A，剪掉A相關的邊，這時候的排序是{D,C1,C2,A}
  • 繼續，入度哦為0的點只有B，拿B，剪掉B相關的邊，最後只剩下object
  • 所以最後的排序是{D,C1,C2,A,B,object}

我們執行上面的程式碼，發現print(D.mro)的結果也正是這樣，而這也就是多重繼承所使用的C3演算法啦

為了進一步熟悉這個拓撲排序的方法，我們再來一張圖，試試看排序結果是怎樣的，它繼承的內容是否如你所想

#!/usr/bin/env python3  # -*- coding: utf-8 -*-  class A(object):      def foo(self):          print('A foo')      def bar(self):          print('A bar')    class B(object):      def foo(self):          print('B foo')      def bar(self):          print('B bar')    class C1(A):      pass    class C2(B):      def bar(self):          print('C2-bar')    class D(C1,C2):      pass    if __name__ == '__main__':      print(D.__mro__)      d=D()      d.foo()      d.bar()

運行結果：

(<class '__main__.D'>, <class '__main__.C1'>, <class '__main__.A'>, <class '__main__.C2'>, <class '__main__.B'>, <class 'object'>)  A foo  A bar

還是先根據繼承關係構一個繼承圖

  • 找到入度為0的頂點，只有一個D，拿D，剪掉D相關的邊
  • 得到兩個入度為0的頂點(C1,C2),根據最左原則，拿C1，剪掉C1相關的邊，這時候序列為{D,C1}
  • 接著看，入度為0的頂點有兩個(A,C1),根據最左原則，拿A，剪掉A相關的邊，這時候序列為{D,C1,A}
  • 接著看，入度為0的頂點為C2,拿C2，剪掉C2相關的邊，這時候序列為{D,C1,A,C2}
  • 繼續，入度為0的頂點為B，拿B，剪掉B相關的邊，最後還有一個object
  • 所以最後的序列為{D,C1,A,C2,B,object}

最後，我們執行上面的程式碼，發現print(D.mro)的結果正如上面所計算的結果

最後的最後，python繼承順序遵循C3演算法，只要在一個地方找到了所需的內容，就不再繼續查找

Tags:

VirMach 便宜 VPS