Node的子节点列表在C ++中遍历BFS时丢失

Question

我正在编写一段C ++代码以执行有向图的广度优先遍历。

在主要功能中，我总共定义了7个节点并在它们之间建立连接。一个节点是一个结构，其中包含名称，值和所有子节点的列表。

我调用函数breadthFirstTraversal（const Node＆root），该函数使用队列来遍历所有节点，并在它们出队时打印它们。

我的主要问题是，即使将子节点添加到了较深的节点，列表也似乎为空。

一个节点：

struct Node_ {
    std::string nodeName = "";
    uint32_t taskCost = 0x0;
    uint64_t maxCost = 0x0;
    std::list<Node_> children;
    bool visited = false;
};
typedef struct Node_ Node;

节点：

main(){

    /* Node declaration here... */

    node1.children.push_back(node2);
    node1.children.push_back(node3);
    node2.children.push_back(node4);
    node3.children.push_back(node4);
    node4.children.push_back(node5);
    node4.children.push_back(node6);
    node5.children.push_back(node7);
    node6.children.push_back(node7);

    printNode(node1);
    printNode(node2);
    printNode(node3);
    printNode(node4);
    printNode(node5);
    printNode(node6);
    printNode(node7);

    breadthFirstTraversal(node1);

}

穿越功能：

void breadthFirstTraversal(const Node& root) {

std::cout << "\n\n\nBreadth first traversal!\n";

std::list<Node> q;

// Insert first elem
q.push_back(root);

while (!q.empty()) {

    std::cout << "new iteration\n";

    Node auxNode = q.front();
    std::cout << "pop " << auxNode.nodeName << "\n";
    printNode(auxNode);
    auxNode.visited = true;

    for (Node child : auxNode.children) {
        if (!child.visited) {
            std::cout << "push child " << child.nodeName << "\n";
            q.push_back(child);
        }
    }

    q.pop_front();

}

}

这里是输出。如您所见，即使将节点添加到这些列表中，node2和node3也没有子级。

Breadth first traversal!
new iteration
pop root
Node: {name= root, taskCost=0, maxCost=0, visited=0, children=[node2,node3,]}
push child node2
push child node3
new iteration
pop node2
Node: {name= node2, taskCost=6, maxCost=0, visited=0, children=[]}
new iteration
pop node3
Node: {name= node3, taskCost=9, maxCost=0, visited=0, children=[]}

Answer 1

在c ++中出队就像拿front()，也拿pop_front！实际上，您的pop_front()可能比该项目弹出子级。这是更新代码：

void breadthFirstTraversal(const Node& root) {

std::cout << "\n\n\nBreadth first traversal!\n";

std::list<Node> q;

// Insert first elem
q.push_back(root);

while (!q.empty()) {

    std::cout << "new iteration\n";

    Node auxNode = q.front();
    q.pop_front();
    std::cout << "pop " << auxNode.nodeName << "\n";
    printNode(auxNode);
    auxNode.visited = true;

    for (Node child : auxNode.children) {
        if (!child.visited) {
            std::cout << "push child " << child.nodeName << "\n";
            q.push_back(child);
        }
    }

}

}