雲計算開發實例:Python3 拓撲排序

2021-01-07 TechWeb

對一個有向無環圖(Directed Acyclic Graph簡稱DAG)G進行拓撲排序，是將G中所有頂點排成一個線性序列，使得圖中任意一對頂點u和v，若邊(u,v)∈E(G)，則u在線性序列中出現在v之前。通常，這樣的線性序列稱為滿足拓撲次序(Topological Order)的序列，簡稱拓撲序列。簡單的說，由某個集合上的一個偏序得到該集合上的一個全序，這個操作稱之為拓撲排序。

在圖論中，由一個有向無環圖的頂點組成的序列，若且唯若滿足下列條件時，稱為該圖的一個拓撲排序（英語：Topological sorting）：

每個頂點出現且只出現一次；

若A在序列中排在B的前面，則在圖中不存在從B到A的路徑。

實例

執行以上代碼輸出結果為：

相關焦點

  • 雲計算開發實例:Python3歸併排序
    歸併排序（英語：Merge sort，或mergesort），是創建在歸併操作上的一種有效的排序算法。該算法是採用分治法（Divide and Conquer）的一個非常典型的應用。
  • 雲計算開發實例:Python3快速排序
    快速排序使用分治法（Divide and conquer）策略來把一個序列（list）分為較小和較大的2個子序列，然後遞歸地排序兩個子序列。步驟為：挑選基準值：從數列中挑出一個元素，稱為"基準"（pivot）;分割：重新排序數列，所有比基準值小的元素擺放在基準前面，所有比基準值大的元素擺在基準後面（與基準值相等的數可以到任何一邊）。
  • python list 排序的兩種方法及實例講解
    用 list 的內建函數 list.sort 進行排序list.sort(func=None, key=None, reverse=False) Python實例：123456>>> L = [2,5,8,9,3]  >
  • 雲計算培訓學院,雲計算Python自動化運維開發實戰
    後來發現工作量大的時候shell開始變慢，實現某個功能使用shell感覺力不從心，聽人說python能實現shell能做的一切功能，而且開發效率高，速度快，慢慢的就認識了python,多多少少看點簡單的東西。
  • python給list排序的簡單方法
    其實會出現這種情況是由於計算機算法的排序，會根據關鍵詞關聯、搜索量等原因排序。那你知道在python中如何給列表排序嗎？今天，小編教教大家如何給列表排序。sort()方法會對list中元素按照大小進行排序list.sort(key=None,reverse=False)實例：In [57]: l=[27,47,3,42,19,9]In [58]: l.sort()In [59]: lOut[59]: [3, 9, 19,
  • 拓撲排序之Java詳解
    本文作者：skywang12345歡迎點擊下方閱讀原文拓撲排序介紹拓撲排序(Topological Order)是指，將一個有向無環圖(Directed Acyclic Graph簡稱DAG)進行排序進而得到一個有序的線性序列。
  • 拓撲排序的簡介及實現
    一、什麼是拓撲排序在圖論中，拓撲排序（Topological Sorting）是一個有向無環圖（DAG, Directed Acyclic Graph）的所有頂點的線性序列。且該序列必須滿足下面兩個條件：有向無環圖（DAG）才有拓撲排序，非DAG圖沒有拓撲排序一說。
  • 堆排序與拓撲排序(Java模板)
    (3) 什麼是拓撲序列？通常，這樣的線性序列稱為滿足拓撲次序的序列，簡稱拓撲序列。如下圖：拓撲序列為：1 2 3因為 1指向 2，所以1排在2之前，1指向3，所以1排在3之前，2指向3，所以2排在3之前。故拓撲序為1 2 3。
  • 雲計算開發學習實例:Python3 計算 n 個自然數的立方和
    225公式 : 13 + 23 + 33 + 43 + 53 = 225輸入 : n = 7輸入 : 784公式 : 13 + 23 + 33 + 43 + 53 + 63 + 73 = 784以上實例輸出結果為
  • 雲計算開發學習實例:Python3 平方根
    以下實例為通過用戶輸入一個數字，並計算這個數字的平方根：執行以上代碼輸出結果為：在該實例中，我們通過用戶輸入一個數字，並使用指數運算符 ** 來計算該數的平方根。該程序只適用於正數。負數和複數可以使用以下的方式：執行以上代碼輸出結果為：該實例中，我們使用了 cmath (complex math) 模塊的 sqrt() 方法。
  • 圖解:什麼是拓撲排序?
    今天景禹給你們談一談拓撲排序，乍一聽上去，感覺很高大上，但她的確很高大上，所以一起徵服她吧！在正式介紹拓撲排序之前，我們一起看一看必備基礎。拓撲排序基礎篇 總覺得書上的概念有點欠缺生動，但還是需要這些基礎的概念作為支撐。
  • 拓撲排序的原理及其實現
    那麼這個制定選修課程順序的過程，實際上就是一個拓撲排序的過程，每門課程相當於有向圖中的一個頂點，而連接頂點之間的有向邊就是課程學習的先後關係。只不過這個過程不是那麼複雜，從而很自然的在我們的大腦中完成了。將這個過程以算法的形式描述出來的結果，就是拓撲排序。那麼是不是所有的有向圖都能夠被拓撲排序呢？顯然不是。
  • Python新式類的方法解析順序MRO與Super
    新式類：廣度優先的C3算法實現（拓撲排序） BFS python2.3及以後python 用MRO的目的是什麼解決多重繼承的二義性的問題（二義性：父類存在同名函數的時候會產生二義性）為python調用一個類或者實例方法的時候提供查找順序經典類的方法解析順序深度優先算法：
  • 雲計算開發學習實例:Python3 字符串判斷
    執行以上代碼輸出結果為：以下代碼演示了Python字符串的判斷測試實例二：
  • 雲計算開發學習實例:Python3 list操作用法總結
    List是python中的基本數據結構之一，和Java中的ArrayList有些類似，支持動態的元素的增加。list還支持不同類型的元素在一個列表中，List is an Object。1.list 定義
  • 數據結構與算法之拓撲排序
    BFS和DFS總結的一些套路，忽然覺得不如直接拓撲排序講解一下，也是甚好，那麼今天就介紹一下拓撲排序吧。定義以下是拓撲排序在維基百科上的定義。拓撲排序（Topological sorting）在計算機科學領域，有向圖的拓撲排序是對其頂點的一種線性排序，使得對於從頂點u到頂點v的每個有向邊uv，u在排序中都在v之前。
  • 拓撲排序原理與解題套路
    點擊藍色「五分鐘學算法」關注我喲加個「星標」，一起學算法其實最開始學習算法，聽到拓撲排序這幾個字我也是懵逼的，後來學著學著才慢慢知道是怎麼一回事。拓撲排序解決的是依賴圖問題。依賴圖表示的是節點的關係是有依賴性的，比如你要做事件 A，前提是你已經做了事件 B。除了 「先有雞還是先有蛋」 這類問題，一般來說事件的依賴關係是單向的，因此我們都用有向無環圖來表示依賴關係。拓撲排序就是根據這些依賴來給出一個做事情，或者是事件的一個順序。
  • 雲計算開發學習筆記:Python的環境搭建
    來源：TechWeb.com.cn大家都知道學好Python是進入雲計算領域的基礎，那麼在學習之前我們先來了解下Python環境是如何搭建的。Python可應用於多種平臺，包括大家熟悉的Window，Linux 和 Mac OS X。
  • 揭開「拓撲排序」的神秘面紗
    anyway 這篇先來拓撲排序～Topological sort 又稱 Topological order，這個名字有點迷惑性，因為拓撲排序並不是一個純粹的排序算法，它只是針對某一類圖，找到一個可以執行的線性順序。
  • 雲計算開發學習實例:Python3 如何判斷閏年
    那麼在Python3中如何判斷閏年呢，以下實例可以判斷用戶輸入的年份是否為閏年：我們也可以使用內嵌 if 語句來實現：執行以上代碼輸出結果為：延伸其實 Python 的 calendar 庫中已經封裝好了一個方法