graph.py 文件源码

def prim(self):
        '''
        Returns Prim's minimum spanninng tree
        '''
        big_f = set([])
        costs = np.empty((self.n), dtype=object)
        costs[:] = np.max(self.costs) + 1
        big_e = np.empty((self.n), dtype=object)
        big_q = set(range(self.n))
        tree_edges = np.array([], dtype=object)
        while len(big_q) > 0:
            v = np.argmin(costs)
            big_q.remove(v)
            costs[v] = np.Infinity
            big_f.add(v)
            if big_e[v] is not None:
                tree_edges = np.append(tree_edges, None)
                tree_edges[-1] = (big_e[v], v)

            for i, w in zip(range(len(self.FSs[v])), self.FSs[v]):
                if w in big_q and self.FS_costs[v][i] < costs[w]:
                    costs[w] = self.FS_costs[v][i]
                    big_e[w] = v
        return tree_edges