Список дочерних узлов в узле теряется при обходе BFS в C ++ - PullRequest
Новая
       30

Список дочерних узлов в узле теряется при обходе BFS в C ++

0 голосов
/ 29 октября 2019

Я пишу фрагмент кода 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();

}

}

Вот вывод. Как вы можете заметить, узлы2 и узлы3 не имеют дочерних элементов, хотя узлы были добавлены в эти списки. 

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=[]}

Ответы [ 2 ]

0 голосов
/ 29 октября 2019

"Как вы можете заметить, у узла 2 и узла 3 нет дочерних элементов, хотя узлы были добавлены в эти списки."

Нет, это не так. Следуйте и поймите все предстоящие операции выполнены по значению . Нет ссылок или указателей.

  1. Создайте все узлы.
  2. Вставьте node2 в children из node1. Это создает копию существующего состояния node2 (у которого еще нет дочерних элементов) и добавляет эту копию к children из node1.
  3. Нажмите node3 в children из node1. Как и выше, это создает копию node3 (у которой нет дочерних элементов) и добавляет эту копию к children из node1.
  4. Нажмите node4 в children из node2. Здесь . Который node2? Ответом является локальный node2, а не копия, которая сейчас находится в node1.children

Эта ошибка в (4) выше повторялась на протяжении оставшейся части ваших нажатий. Вы можете решить эту проблему любым количеством способов, но самый быстрый способ получить то, что вам нужно, - это построить ваше дерево назад . Т.е. сначала полностью заполняют нижние уровни, затем их родители используют этих детей, затем их дедушки используют эти родителей и т. Д., Пока вы не прибудете с последним набором узлов, вставляющим в node1.children.

Другими словами, сделайте это: 

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

Теперь, когда все эти копии сделаны, вы копируете заполненные дочерние узлы в родительские коллекции. Не эффективно, но это будет работать.

0 голосов
/ 29 октября 2019

Удаление очереди в 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);
        }
    }

}

}
...