我正在尝试为有根树构建一个欧拉路径,其中根可以有多个 child (即它不是二叉树)。为了跟踪每个已经遍历的 child ,我在 map 中维护了一个队列。当我遇到一个根时,我只需弹出它的一个子节点并将其设置为根。问题是,每当我弹出一个子节点并再次遍历其父节点时,弹出的节点再次出现。我猜我需要存储队列的引用,但无法理解它。任何帮助,将不胜感激。
vector<int> getEulerPath(Node* root) {
Node* node = root;
vector<int> path;
unordered_map<int, queue<Node*>> uvc;
while(node != NULL) {
path.push_back(node->data);
cout << "processing node " << node->data << endl;
if(uvc.find(node->data) != uvc.end()) {
cout << "found queue: " << node->data << endl;
uv = uvc.find(node->data)->second;
} else {
for(int i = 0; i < node->children.size(); i++) {
uv.push(node->children[i]);
}
cout << "adding queue: " << node->data << endl;
uvc.insert(pair<int, queue<Node*>>{node->data, uv});
}
if(!uv.empty()) {
cout << "queue size before popping: " << uv.size() << endl;
cout << "have some children left for : " << node->data << endl;
node = uv.front();
uv.pop();
cout << "queue size after popping: " << uv.size() << endl;
} else {
cout << "no children left reverting back to : " << node->parent->data << endl;
node = node->parent;
}
cout << "new node is: " << node->data << endl;
}
return path;
}
更新
以下是最小的可运行示例
#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
using namespace std;
class Node {
public:
vector<Node*> children;
Node* parent;
int data;
Node();
Node(int, Node*);
};
Node::Node() {
parent = NULL;
data = -1;
}
Node::Node(int d, Node* p) {
parent = p;
data = d;
}
Node* generateTree(vector<vector<int>> edges) {
unordered_map<int, Node*> nodes;
Node* root = new Node();
for(int i = 0; i < edges.size(); i++) {
vector<int> edge = edges[i];
Node* parent;
Node* child;
if(nodes.find(edge[0]) == nodes.end()) {
parent = new Node(edge[0], NULL);
nodes.insert(pair<int, Node*>{edge[0], parent});
} else {
parent = nodes.find(edge[0])->second;
}
if(nodes.find(edge[1]) == nodes.end()) {
child = new Node(edge[1], parent);
nodes.insert(pair<int, Node*>{edge[0], child});
} else {
child = nodes.find(edge[1])->second;
}
if(i == 0) root = parent;
parent->children.push_back(child);
}
return root;
}
vector<int> getEulerPath(Node* root) {
Node* node = root;
vector<int> path;
unordered_map<int, queue<Node*>> uvc;
while(node != NULL) {
path.push_back(node->data);
cout << "processing node " << node->data << endl;
queue<Node*> uv;
if(uvc.find(node->data) != uvc.end()) {
cout << "found queue: " << node->data << endl;
uv = uvc.find(node->data)->second;
} else {
for(int i = 0; i < node->children.size(); i++) {
uv.push(node->children[i]);
}
cout << "adding queue: " << node->data << endl;
uvc.insert(pair<int, queue<Node*>>{node->data, uv});
}
if(!uv.empty()) {
cout << "queue size before popping: " << uv.size() << endl;
cout << "have some children left for : " << node->data << endl;
node = uv.front();
uv.pop();
cout << "queue size after popping: " << uv.size() << endl;
} else {
cout << "no children left reverting back to : " << node->parent->data << endl;
node = node->parent;
}
cout << "new node is: " << node->data << endl;
}
return path;
}
int main() {
vector<vector<int>> edges;
edges.push_back(vector<int> {1, 2});
edges.push_back(vector<int> {1, 3});
edges.push_back(vector<int> {1, 4});
edges.push_back(vector<int> {3, 5});
edges.push_back(vector<int> {3, 6});
edges.push_back(vector<int> {3, 7});
Node* root = generateTree(edges);
vector<int> euler_path = getEulerPath(root);
for(int i = 0; i < euler_path.size(); i++) {
cout << euler_path[i] << " ";
}
cout << endl;
return 0;
}
最佳答案
您正在使用 uv = uvc.find(node->data)->second
复制 map 中的数据。表达。然后你修改那个拷贝。 map 中的数据永远不会改变。同样,当您将节点插入 map 时,您仍在修改拷贝。
您需要使用指向存储在 uvc
中的队列的指针。 .这些方面的东西:
queue<Node*> *uvc;
auto fit = uvc.find(node->data);
if(fit != uvc.end()) {
cout << "found queue: " << node->data << endl;
uv = &fit->second;
} else {
cout << "adding queue: " << node->data << endl;
uv = &uvc[node->data];
for(int i = 0; i < node->children.size(); i++) {
uv->push(node->children[i]);
}
}
通过保存 find
返回的迭代器,您可以避免重复查找它。而且,因为 []
unordered_map
上的运算符如果键不存在,将插入一个键/值对,您可以快速添加一个新节点并获取指向它的指针(或引用)。对
uv.
的其他引用在下面的代码中需要更新为 uv->
.
关于c++ - 如何在 std::unordered_map 中维护 std::队列而不丢失对队列所做的更改?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/59430481/