add spanning tree

[weilycoder]

加入生成树，返回格式为（父，子）元组的列表

默认是从 1 开始执行 DFS（BFS 风格），可以通过指定容器实现 BFS 生成树或最小生成树。

可以通过传入 from_weight 决定是否显示边权和如何显示，默认是 lambda w: None，即不显示。

import random
import heapq
import collections
from cyaron.graph import *

random.seed(0, 2)


class Queue:
    def __init__(self):
        self.queue = collections.deque()

    def append(self, _x):
        self.queue.append(_x)

    def pop(self):
        return self.queue.popleft()

    def __bool__(self):
        return bool(self.queue)


class Heap:
    def __init__(self):
        self.heap = []

    def append(self, _x):
        heapq.heappush(self.heap, _x)

    def pop(self):
        return heapq.heappop(self.heap)

    def __bool__(self):
        return bool(self.heap)


g = Graph.graph(6, 10, weight_limit=10)
print(g.to_str())
print(g.to_tree()) # DFS 生成树
print(g.to_tree(5)) # DFS 生成树, 以 5 为根
print(g.to_tree(container=Queue)) # BFS 生成树
print(g.to_tree(container=Heap)) # 最小生成树

应该输出：

1 2 10
1 6 6
2 5 5
2 3 2
3 5 8
3 4 8
3 5 4
3 5 10
4 4 1
4 5 2
[(1, 6), (1, 2), (2, 3), (3, 5), (5, 4)]
[(5, 4), (4, 3), (3, 2), (2, 1), (1, 6)]
[(1, 2), (1, 6), (2, 5), (2, 3), (5, 4)]
[(1, 6), (1, 2), (2, 3), (3, 5), (5, 4)]
[(1, 6, 6), (1, 2, 10), (2, 3, 2), (3, 5, 4), (5, 4, 2)]