Найдите все связующие деревья, используя BFS ⇐ C++

[Anonymous]

Пытаясь найти все связующие деревья с помощью очереди, я пришел к выводу, что логично было бы искать ребра. Если в дереве нет нового ребра, я добавляю его в дерево и помещаю дерево в очередь. Я могу проверить, было ли в дереве ребро, могу определить, есть ли цикл, но не могу понять, как определить, какие деревья являются копиями (я мог бы рассматривать ребра в разном порядке, но сама древовидная структура останется прежним, и лишние деревья я не смогу выкинуть). К коду было несколько замечаний, поэтому я попытался его переработать. На этом этапе я использовал встроенный класс очереди. Однако на данном этапе использование контейнеров для меня является проблемой
bool IsAcyclic(int v, const vector& adj, vector& visited, int parent) {
visited[v] = true;
for (int u : adj[v]) {
if (!visited) {
if (!IsAcyclic(u, adj, visited, v))
return false;
}
else if (u != parent) {
return false;
}
}
return true;
}

void findAllSPanningTrees(int start, const vector& adj, int V) {
queue q;
vector initial;
q.push(initial);

while (!q.empty()) {
vectorcurrentTree = q.front();
q.pop();
if (currentTree.size() == V - 1) {
vector tempAdj(V);
for (const Edge& edge : currentTree) {
tempAdj[edge.u].push_back(edge.v);
tempAdj[edge.v].push_back(edge.u);
}
vector visited(V, false);
if (IsAcyclic(start, tempAdj, visited, -1))
//I think it was possible to avoid recursion, but I'm actually wondering if I can somehow check for cyclicity previously
printSpanningTree(currentTree);

continue;
}
setusedEdges;
for (const Edge& edge : currentTree) {
usedEdges.insert({ min(edge.u,edge.v),max(edge.u,edge.v) });//Since edge (1, 2) and (2, 1) are the same, I keep them as (1, 2)
}
for (int u = 0; u < V; u++) {
for (int v : adj) {
if (u < v && usedEdges.find({ u,v }) == usedEdges.end()) { //avoiding repeated edges in a tree
vector newTree = currentTree;
newTree.push_back(Edge(u, v));
q.push(newTree);
}
}
}

}
}


Подробнее здесь: https://stackoverflow.com/questions/790 ... -using-bfs