Я пишу фрагмент кода C++ для выполнения обхода ориентированного графа в ширину.
В основной функции я определяю всего 7 узлов и устанавливаю связи между ними. Один узел — это структура, которая содержит имя, значение и список всех дочерних узлов.
Я вызываю функцию widthFirstTraversal(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=[]}
