排序图中的边缘

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是一组，快速排序的方法基本上是一个无操作，除非你做的输出数组的东西。该集将不会被改变。