c++ - 在 C++ 中的 BFS 遍历期间，Node 中的子节点列表丢失

Question

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

在 main 函数中，我一共定义了 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=[]}

标签： c++treetraversalbreadth-first-search

Answer 1

c++ 中的出队就像拿front()and 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);
        }
    }

}

}