基于BFS查找所有生成树的重复树判定及代码优化问题

我尝试用队列枚举所有生成树，确定采用边遍历的搜索方式是可行的。规则是如果当前树中没有这条新边，就把它加入树并将新树入队。我能判断树中是否存在边、是否有环，但无法识别重复树——也就是边的添加顺序不同但结构完全一致的树，没法剔除这些冗余结果。根据代码反馈我已经重构了代码，用了内置队列类，但目前对容器的使用还是有困难。

相关代码 #

#include <vector>
#include <queue>
#include <set>
#include <algorithm>

// 假设Edge结构体定义如下
struct Edge {
    int u, v;
    Edge(int u_, int v_) : u(u_), v(v_) {}
};

bool IsAcyclic(int v, const std::vector<std::vector<int>>& adj, std::vector<bool>& visited, int parent) {
    visited[v] = true;
    for (int u : adj[v]) {
        if (!visited[u]) {
            if (!IsAcyclic(u, adj, visited, v))
                return false;
        }
        else if (u != parent) {
            return false;
        }
    }
    return true;
}

void printSpanningTree(const std::vector<Edge>& tree) {
    // 假设此函数用于打印生成树
    for (const auto& e : tree) {
        printf("(%d, %d) ", e.u, e.v);
    }
    printf("\n");
}

void findAllSpanningTrees(int start, const std::vector<std::vector<int>>& adj, int V) {
    std::queue<std::vector<Edge>> q;
    std::vector<Edge> initial;
    q.push(initial);

    while (!q.empty()) {
        std::vector<Edge> currentTree = q.front();
        q.pop();

        if (currentTree.size() == V - 1) {
            std::vector<std::vector<int>> tempAdj(V);
            for (const Edge& edge : currentTree) {
                tempAdj[edge.u].push_back(edge.v);
                tempAdj[edge.v].push_back(edge.u);
            }
            std::vector<bool> visited(V, false);
            if (IsAcyclic(start, tempAdj, visited, -1))
                // 我知道可以不用递归，但其实更想知道能不能提前判断是否有环
                printSpanningTree(currentTree);
        
            continue;
        }

        std::set<std::pair<int, int>> usedEdges;
        for (const Edge& edge : currentTree) {
            // 因为边(1,2)和(2,1)是同一条，统一存为(1,2)的形式
            usedEdges.insert({ std::min(edge.u, edge.v), std::max(edge.u, edge.v) });
        }

        for (int u = 0; u < V; u++) {
            for (int v : adj[u]) {
                if (u < v && usedEdges.find({ u, v }) == usedEdges.end()) { // 避免树中出现重复边
                    std::vector<Edge> newTree = currentTree;
                    newTree.push_back(Edge(u, v));
                    q.push(newTree);
                }
            }
        }
    }
}

问题解决方案 #

1. 剔除重复树的核心思路

• 标准化树结构：将每个树的边转换为有序集合（所有边统一存为(min(u,v), max(u,v))的形式），用全局集合记录已处理过的标准化结构，遇到重复直接跳过，避免重复入队和处理。
• 约束边扩展顺序：规定每次添加的边必须比当前树中最后一条边的字典序更大（比如按u*V + v的值排序），让每个树只会以唯一的边顺序生成，从根源减少重复。

2. 容器使用优化

• 替换set为unordered_set提升效率：set的查找和插入是O(logn)，可以把边编码为整数（比如u*V + v，其中u < v），用unordered_set<int>存储已用边，将操作复杂度降到O(1)。
• 提前用并查集判断环：不用等树长到V-1条边再判环，添加新边前用并查集检查两个顶点是否连通，若连通则加边会形成环，直接跳过该边，减少队列无效元素。示例代码如下：

// 并查集实现
struct UnionFind {
    std::vector<int> parent;
    UnionFind(int n) : parent(n) {
        for (int i = 0; i < n; i++) parent[i] = i;
    }
    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    bool unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return false;
        parent[y] = x;
        return true;
    }
};

// 修改后的生成树枚举函数，加入并查集提前判环
void findAllSpanningTrees(int start, const std::vector<std::vector<int>>& adj, int V) {
    std::queue<std::pair<std::vector<Edge>, UnionFind>> q;
    std::vector<Edge> initial;
    q.push({initial, UnionFind(V)});

    std::set<std::set<std::pair<int, int>>> seenTrees;

    while (!q.empty()) {
        auto [currentTree, uf] = q.front();
        q.pop();

        if (currentTree.size() == V - 1) {
            printSpanningTree(currentTree);
            continue;
        }

        std::set<std::pair<int, int>> usedEdges;
        for (const Edge& edge : currentTree) {
            usedEdges.insert({ std::min(edge.u, edge.v), std::max(edge.u, edge.v) });
        }

        if (seenTrees.count(usedEdges)) continue;
        seenTrees.insert(usedEdges);

        for (int u = 0; u < V; u++) {
            for (int v : adj[u]) {
                if (u < v && usedEdges.find({u, v}) == usedEdges.end()) {
                    UnionFind newUf = uf;
                    if (newUf.unite(u, v)) { // 能合并说明无环，加入队列
                        std::vector<Edge> newTree = currentTree;
                        newTree.push_back(Edge(u, v));
                        q.push({newTree, newUf});
                    }
                }
            }
        }
    }
}

内容的提问来源于stack exchange，提问作者Potato