在C中的BFS遍历过程中，节点中的子节点列表丢失

Question

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

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

我调用函数breadthFirstTraverse（constNode

我的主要问题是，深层节点的列表似乎为空，即使子节点已添加到其中。

节点：

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中去排队就像取ex（），还取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);
        }
    }

}

}