排序圖中的邊緣

Question

我有一個class調用Graph來表示連接的無向圖，我想實現快速排序基於邊上的權重排序邊緣。

class Graph: 
    def __init__(self, n): 
     self.vertices = range(n) 
     self.edges = set([(random.random(), i, j) for i in xrange(n) for j in xrange(n)]) 

    def qsort(self): 
     if len(self.edges) <= 1: 
      return self.edges 
     else: 
      return qsort([x for x in self.edges[1:] if x < self.edges[0]]) + [self.edges[0]] + qsort([x for x in self.edges[1:] if x >= self.edges[0]]) 

graph = Graph(10) 
graph.qsort() 

當我嘗試運行上述，我得到NameError: global name 'qsort' is not defined。

有人能告訴我我做錯了什麼嗎？

Answer 1

您的問題的文字回答是，您正在省略self關鍵字：return self.qsort(...) + [self.edges[0]] + self.qsort(...)。

它看起來像你試圖實現像this answer 3線qsort，也在Python Cookbook給出。你的實現是錯誤的，因爲它應該有兩個參數，self和你正在排序的數組。

不幸的是，沒有辦法避免在數組中傳遞，但有一種可能的解決方法。爲您的方法添加一個額外的關鍵字參數：qsort(self, arr = None)，然後檢查該數組是否爲None，並在該情況下使用self.edges。你的graph.qsort()整齊的語法不會有這種情況發生變化：

def qsort(self, arr = None): 
    if arr is None: arr = list(self.edges) 
    if len(arr) <= 1: return arr 
    else: 
     return self.qsort([x for x in arr[1:] if x < arr[0]]) + \ 
       [arr[0]] + \ 
       self.qsort([x for x in arr[1:] if x >= arr[0]]) 

注意，因爲self.edges是一組，快速排序的方法基本上是一個無操作，除非你做的輸出數組的東西。該集將不會被改變。